This chapter is from the book
This chapter is from the book
This chapter is from the book
12.7 Allocators
By default, standard-library containers allocate space using new. Operators new and delete provide a general free store (also called dynamic memory or heap) that can hold objects of arbitrary size and user-controlled lifetime. This implies time and space overheads that can be eliminated in many special cases. Therefore, the standard-library containers offer the opportunity to install allocators with specific semantics where needed. This has been used to address a wide variety of concerns related to performance (e.g., pool allocators), security (allocators that clean-up memory as part of deletion), per-thread allocation, and non-uniform memory architectures (allocating in specific memories with pointer types to match). This is not the place to discuss these important, but very specialized and often advanced techniques. However, I will give one example motivated by a real-world problem for which a pool allocator was the solution.
An important, long-running system used an event queue (see §18.4) using vectors as events that were passed as shared_ptrs. That way, the last user of an event implicitly deleted it:
struct Event {
vector<int> data = vector<int>(512);
};
list<shared_ptr<Event>> q;
void producer()
{
for (int n = 0; n!=LOTS; ++n) {
lock_guard lk {m}; // m is a mutex; see §18.3
q.push_back(make_shared<Event>());
cv.notify_one(); // cv is a condition_variable; see §18.4
}
}
From a logical point of view this worked nicely. It is logically simple, so the code is robust and maintainable. Unfortunately, this led to massive fragmentation. After 100,000 events had been passed among 16 producers and 4 consumers, more than 6GB of memory had been consumed.
The traditional solution to fragmentation problems is to rewrite the code to use a pool allocator. A pool allocator is an allocator that manages objects of a single fixed size and allocates space for many objects at a time, rather than using individual allocations. Fortunately, C++ offers direct support for that. The pool allocator is defined in the pmr (“polymorphic memory resource”) subnamespace of std:
pmr::synchronized_pool_resource pool; // make a pool
struct Event {
vector<int> data = vector<int>{512,&pool}; // let Events use the pool
};
list<shared_ptr<Event>> q {&pool}; // let q use the pool
void producer()
{
for (int n = 0; n!=LOTS; ++n) {
scoped_lock lk {m}; // m is a mutex (§18.3)
q.push_back(allocate_shared<Event,pmr::polymorphic_allocator<Event>>{&pool});
cv.notify_one();
}
}
Now, after 100,000 events had been passed among 16 producers and 4 consumers, less than 3MB of memory had been consumed. That’s about a 2000-fold improvement! Naturally, the amount of memory actually in use (as opposed to memory wasted to fragmentation) is unchanged. After eliminating fragmentation, memory use was stable over time so the system could run for months.
Techniques like this have been applied with good effects from the earliest days of C++, but generally they required code to be rewritten to use specialized containers. Now, the standard containers optionally take allocator arguments. The default is for the containers to use new and delete. Other polymorphic memory resources include
unsynchronized_polymorphic_resource; like polymorphic_resource but can only be used by one thread.
monotonic_polymorphic_resource; a fast allocator that releases its memory only upon its destruction and can only be used by one thread.
A polymorphic resource must be derived from memory_resource and define members allocate(), deallocate(), and is_equal(). The idea is for users to build their own resources to tune code.