Allocator (C++) - Custom Allocators

Custom Allocators

One of the main reasons for writing a custom allocator is performance. Utilizing a specialized custom allocator may substantially improve the performance or memory usage, or both, of the program. The default allocator uses operator new to allocate memory. This is often implemented as a thin layer around the C heap allocation functions, which are usually optimized for infrequent allocation of large memory blocks. This approach may work well with containers that mostly allocate large chunks of memory, like vector and deque. However, for containers that require frequent allocations of small objects, such as map and list, using the default allocator is generally slow. Other common problems with a malloc-based allocator include poor locality of reference, and excessive memory fragmentation.

A popular approach to improve performance is to create a memory pool-based allocator. Instead of allocating memory every time an item is inserted or removed from a container, a large block of memory (the memory pool) is allocated beforehand, possibly at the startup of the program. The custom allocator will serve individual allocation requests by simply returning a pointer to memory from the pool. Actual deallocation of memory can be deferred until the lifetime of the memory pool ends. An example of memory pool-based allocators can be found in the Boost C++ Libraries.

The subject of custom allocators has been treated by many C++ experts and authors, including Scott Meyers in Effective STL and Andrei Alexandrescu in Modern C++ Design. Meyers observes that the requirement for all instances of an allocator to be equivalent in effect forces portable allocators to not have state. Although the C++ Standard does encourage library implementors to support stateful allocators, Meyers calls the relevant paragraph "a lovely sentiment" that "offers you next to nothing", characterizing the restriction as "draconian".

In The C++ Programming Language, Bjarne Stroustrup, on the other hand, argues that the "apparently raconian restriction against per-object information in allocators is not particularly serious", pointing out that most allocators do not need state, and have better performance without it. He mentions three use cases for custom allocators, namely, memory pool allocators, shared memory allocators, and garbage collected memory allocators. He presents an allocator implementation that uses an internal memory pool for fast allocation and deallocation of small chunks of memory, but notes that such an optimization may already be performed by the allocator provided by the implementation.

Another viable use of custom allocators is for debugging memory-related errors. This could be achieved by writing an allocator that allocates extra memory in which it places debugging information. Such an allocator could be used to ensure that memory is allocated and deallocated by the same type of allocator, and also provide limited protection against overruns.