This post will discuss how to make a STL compliant allocator.
All of the standard containers support a 2nd (or 3rd) template parameter to specify the allocator that should be used. Each container allocates memory to store the objects it contains, and it uses the allocator to obtain the memory required for this storage. By using a custom allocator, you can remain in control of how memory is managed.
Custom allocators are useful for a variety of cases:
- Reducing system call overhead when requesting multiple small memory blocks
- Improving cache efficiency by keeping memory contiguous
- Using standard containers with memory-mapped io, or a memory-mapped file for persistent containers
- Maintaining 100% control of memory for embedded systems or game development
Wikipedia summarizes it well1:
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.
The allocators discussed in this post are meant to be used with C++03. C++11 adds more support for custom allocators, and makes them easier to implement. Furthermore, C++03 allocators are compatible with C++11, but not the other way around.
Creating a custom allocator may seem difficult, but the core concept is pretty simple. Here are the basic rules:
- Cannot have state (C++03 only)
- Must support certain typedefs and methods
- Must support type rebinding
- Allocators of the same type must compare equally
No state also means no virtual functions, as the vtable can be considered state. Normal inheritance is okay, however it is generally considered bad practice to derive from std::allocator. Instead, we will create our own allocator using policies and traits. The methods that need to be implemented can be separated into two categories: those that are related to the allocator, and those that are related to the object being allocated. This distinction defines the policy and traits we will implement.2
Policies and Traits3
Policies are classes (or class templates) to inject behavior into a parent class, typically through inheritance. By decomposing a parent interface into orthogonal (independent) dimensions, policy classes form the building blocks of more complex interfaces. Traits are class templates to extract properties from a generic type. Traits are often used in template-metaprogramming and SFINAE tricks to overload a function template based on a type condition.
The first thing to define is the object traits. This structure is responsible for creating and destroying objects, as well as returning the address of an object. Note that classes support overriding the “address-of” operator, so the object traits will need to be specialized for those classes. The object traits can also be specialized for a type to keep track of the number of instantiations using the allocator, much like the object counter works.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
Notice the special
rebind struct in the above code. This is a convention used by the STL to allow for chainging the type of the allocator. For example, when you make a
std::list<T>, internally the type is being rebound to
std::list<Node<T> >, because lists store nodes that contain a T, not the T itself. To support this, the allocator itself must support rebinding such that memory is allocated for the node, not just T.
The allocator policies require a certain set of typedefs to be present. In most cases, they can all be derived from the type of the allocator, so it makes sense to use a macro:
1 2 3 4 5 6 7 8 9
Next, the actual allocator policy needs to be defined. The allocator policy is responsible for allocating and deallocating memory. For this example, a simple heap allocator will work. The functionality will mimic that of the standard allocator:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
Now that we have all the pieces, it is time to bring them all together. The actual allocator class is nothing more than a wrapper to combine the above into one common place. The key to the allocator wrapper is that it inherits from the allocator policy and object traits, thus the combination satisfies all the requirements for a compliant allocator.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
Notice how the rebinding structure works here; the policy and traits classes are both rebound to the new type when the overall allocator is rebound.
The STL uses the equality operator to determine if memory allocated by one allocator can be deallocated with another. Normally, a heap allocator can be used interchangably between types, so the equality operator would return true. However, with this allocator framework, different policies can be plugged in, and some policies may not be interchangable. Therefore, the equality operator will default to false. Specializations of the equality operators can be made for specific policies to register equality, such as he heap policy:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Using the Allocator
Using the allocator is simple, just pass it into the 2nd (or 3rd) template parameter of a container. Remember that some containers (like
set) have a second template parameter that accepts a comparator.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
And that is how to make an allocator! A future blog post will discuss different policies that can be created.
What is the difference between a trait and a policy? – TemplateRex↩
C++ Standard Allocator, An Introduction and Implementation – Lai Shiaw San Kent↩