Date: 2014-07-16

Thomas Köppe <tkoeppe@google.com>

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.

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