Date: 2014-07-16

Allocator example: A simple arena allocator

Part of the Visitor’s Guide to C++ Allocators

An arena

We will develop a simple, yet non-trivial, stateful allocator which fetches memory from an existing arena, i.e. a pre-allocated chunk of memory. For this example, our arena will simply dole out memory monotonically until it is exhausted, at which point it will throw an exception.

Before we dive into allocators, let us design the arena. For the sake of illustration we include chatty messages that comment on the arena’s operation. The arena class will be unmovable and unassignable.

#include <cstddef> #include <iostream> #include <stdexcept> class Arena { unsigned char * const data; std::size_t const size; std::size_t offset; public: explicit Arena(std::size_t s) : data(static_cast<unsigned char *>(::operator new(s))) , size(s) , offset(0) { std::cout << "arena[" << this << "] of size " << size << " created.\n"; } Arena(Arena const &) = delete; Arena & operator=(Arena const &) = delete; ~Arena() { std::cout << "arena[" << this << "] destroyed; final fill level was: " << offset << "\n"; ::operator delete(data); } void * allocate(std::size_t n, std::size_t a) { offset = (offset + a - 1) / a * a; std::cout << "arena[" << this << "] allocating " << n << " bytes at offset " << offset << ".\n"; if (offset + n > size) { throw std::bad_alloc(); } void * result = data + offset; offset += n; return result; } void deallocate(void *, std::size_t n) { std::cout << "arena[" << this << "] may deallocate " << n << " bytes.\n"; } };

A few words on the details. The memory is obtained from the global allocation function ::operator new. This is guaranteed to be maximally aligned. The arena doles out memory of size n and alignment a in the allocate function. The running offset is rounded up to the desired alignment and the address at that offset is returned to the user; the offset is further incremented by the size of the allocation. There is no meaningful deallocation. Had we made the allocation simpler and always rounded up to the fixed maximal alignment (i.e. alignof(std::max_align_t)), we could conceivably have supported shrinking the arena from the back, but this is not important. The allocate function throws an exception if there is no more space.

The allocator

We now design a stateful allocator that obtains its memory from an arena. Thanks to the defaults provided by std::allocator_traits, we only need to fill in a minimal set of information.

#include <type_traits> template <typename T> struct ArenaAllocator { template <typename U> friend struct ArenaAllocator; using value_type = T; using pointer = T *; using propagate_on_container_copy_assignment = std::true_type; using propagate_on_container_move_assignment = std::true_type; using propagate_on_container_swap = std::true_type; explicit ArenaAllocator(Arena * a) : arena(a) {} template <typename U> ArenaAllocator(ArenaAllocator<U> const & rhs) : arena(rhs.arena) {} pointer allocate(std::size_t n) { return static_cast<pointer>(arena->allocate(n * sizeof(T), alignof(T))); } void deallocate(pointer p, std::size_t n) { arena->deallocate(p, n * sizeof(T)); } template <typename U> bool operator==(ArenaAllocator<U> const & rhs) const { return arena == rhs.arena; } template <typename U> bool operator!=(ArenaAllocator<U> const & rhs) const { return arena != rhs.arena; } private: Arena * arena; };

The allocator’s identity is the value of its arena member. The identity is preserved by rebound-copies and verified with the equality and inequality operators. The only non-trivial operation of this allocator is to forward allocation calls to the arena (computing the desired type’s alignment in the process).

Using the allocator

First, let us make a few arenas and some prototype allocators.

Arena arena1(1024); Arena arena2(400); ArenaAllocator<void> a1(&arena1); ArenaAllocator<void> a2(&arena2);

Now we will not actually be using the allocator directly, but always wrap it in a scoped adaptor. A type alias is handy.

#include <scoped_allocator> template <typename T> using SA = std::scoped_allocator_adaptor<ArenaAllocator<T>>;

Now we are ready to allocate an actual data structure from our arena. As an example (which is fairly plausible in real applications), we consider a map with string keys. Both the map itself and the keys should be allocated from the same arena.

This example will make use of library features introduced in C++14, for subtle reasons which we will point out below. This does not constrain the general validity of the example, though, which is otherwise compliant with C++11.

The first step when making containers of elements which themselves use allocators is to give each nested type the same scoped allocator type. We define several type aliases for this purpose.

#include <map> #include <string> #include <utility> using astring = std::basic_string<char, std::char_traits<char>, SA<char>>; using amap = std::map<astring, int, std::less<>, SA<std::pair<astring const, int>>>;

Both the map type itself and the contained string type are using the scoped allocator SA that we defined above. Spelling out the map’s value type is tedious, but it draws attention to an interesting point we will making shortly.

Note the comparator type std::less<>. This is a feature from C++14, called a transparent comparator. The call operator of the default std::less<astring> expects two actual astring arguments, so we could only ever search for keys that are arena-allocated strings. (Every map search would deplete our arena!) By contrast, the call operator of a transparent comparator is a template which accepts any type and forwards it to the comparison operator. To take advantage of this mechanism, the map’s find and erase members must themselves be templates, which was added in C++14. We will see shortly how to take advantage of the transparent comparator.

Finally we can create, populate and explore our strings and maps.

int main() { astring s1("Short string", a); astring s2("Very looooooooooooooong string", a); amap m(a); m[{"foo", a}] = 10; m[{"fooooooooooooooooooooooooooooo", a}] = 20; m[s1] = 30; m[astring(std::move(s2), b)] = 40; m[{"baaaaaaaaaaaaaaaaaaaaaaaaaaaaar", b}] = 50; auto it = m.find("foo"); if (it != m.end()) { it->second *= 10; } for (auto const & p : m) std::cout << p.first << " => " << p.second << "\n"; }

This code highlights several interesting aspects of allocator-aware code.

Short and long strings may have different allocation behaviour when libraries implement short-string optimisations, which store the entire string in the class header (which is typically three pointers or one pointer and two size_types long). We are using long strings to ensure that our allocator is actually being used.
Every object construction requires mention of the allocator object. The allocator type is not default-constructible, and a prototype of the actual allocator must be passed around (and rebound-copied) everywhere.
When the map is given a string, even by rvalue, that is allocated by a different allocator, it will construct a new string with its own allocator. This point is worth spelling out. Consider the statement that inserts the value 50. The key argument is a string rvalue that uses allocator b. The map’s internal allocator will use the construct() function of the allocator traits, forwarding the string rvalue. But the scoped allocator will mangle this construction call and insert its held allocator argument, because the string satisfies the uses_allocator trait, so that the actual string constructor that is being called is basic_string(basic_string && rhs, Alloc const & a). That constructor must check whether the allocator of rhs and a are equal. If not, then the two allocators cannot free each other&rsquo's memory, and the constructor has to actually copy the string data rather than only copying the pointers.
In the previous point we glossed over a final subtlety: The map’s allocator constructs elements of the map’s value_type, which is a pair, and pairs do not take allocators. However, scoped_allocator_adaptor::construct actually contains a special provision for pair arguments which will apply the uses-allocator construction to each pair element individually. By contrast, there is no such special provision for std::tuple, but instead, uses_allocator is specialised for tuples to be true, and std::tuple contains a set of allocator-extended constructors, so that the same design can be applied to containers of tuples.
The find call uses the transparent comparator. Rather than searching for an allocated astring, the char const * argument is forwarded directly to the comparison expression, which in turn allows overload resolution to find the operator< for basic_string that compares a string instance with a null-terminated character array. No second string is ever constructed. This design works well enough for our example, but note that we cannot compare std::basic_strings with different allocator types, since basic_string does not contain overloaded comparison operator templates parametrised on the allocator. However, it is perfectly feasible to write a custom, transparent comparator (parametrised only on the character traits) that compares a larger set of string-like objects (basic_strings, string views, character arrays).

Finally, here is the annotated and slightly edited output of a typical run (on a 64-bit system with short-string optimisation).

arena[0x11111111] of size 1024 created. // arena1 constructed arena[0x22222222] of size 400 created. // arena2 constructed arena[0x11111111] allocating 32 bytes. // allocation for s2 arena[0x11111111] allocating 72 bytes. // value_type for 10 (key is short) arena[0x11111111] allocating 32 bytes. // key_type temporary for 20 (moved into map) arena[0x11111111] allocating 72 bytes. // value_type for 20 arena[0x11111111] allocating 72 bytes. // value_type for 30 (key is short) arena[0x22222222] allocating 32 bytes. // temporary for 40 (copied into map) arena[0x11111111] allocating 72 bytes. // value_type for 40 arena[0x11111111] allocating 32 bytes. // key_type for 40 arena[0x22222222] may deallocate 32 bytes. // destroy temporary arena[0x22222222] allocating 32 bytes. // temporary for 50 (copied into map) arena[0x11111111] allocating 72 bytes. // value_type for 50 arena[0x11111111] allocating 32 bytes. // key_type for 50 arena[0x22222222] may deallocate 32 bytes. // destroy temporary Short string => 30 Very looooooooooooooong string => 40 baaaaaaaaaaaaaaaaaaaaaaaaaaaaar => 50 foo => 100 fooooooooooooooooooooooooooooo => 20 arena[0x11111111] may deallocate 72 bytes. // map destruction: arena[0x11111111] may deallocate 32 bytes. // 5 value_types (72 bytes each) arena[0x11111111] may deallocate 72 bytes. // 3 long string keys arena[0x11111111] may deallocate 32 bytes. arena[0x11111111] may deallocate 72 bytes. arena[0x11111111] may deallocate 32 bytes. arena[0x11111111] may deallocate 72 bytes. arena[0x11111111] may deallocate 72 bytes. arena[0x11111111] may deallocate 32 bytes. // destroy s2 (was never moved from) arena[0x22222222] destroyed; final fill level was: 64 // arena2 destroyed arena[0x11111111] destroyed; final fill level was: 488 // arena1 destroyed