/prog/

The C++ Arena

by Zardium | Dec 7, 2022

Arenas are a powerful tool for memory management; evaporating confusion and issues with lifetimes. Though some implementations exist, they're not used extensively in C++, which is unfortunate. The value that arenas provide to C++ programs and their architecture is immense and only continues growing along with the complexity of the program. Following are some ideas of note when implementing an arena that fits well into C++.

Required Reading

To start, you should read Ryan Fleury's excellent article on arenas. He covers in a very in-depth manner problems with traditional manual memory management, what arenas are, and how they solve those problems and simplify lifetimes.

I have to agree with Ryan's critiques of the current state and perception of memory management in C++. RAII1 containers and smart pointers do make memory management more automatic, but they serve to automate entirely the wrong problem. It essentially generates all the glue code that tightly couples lifetimes and memory allocations. There are ways to improve the performance characteristics of this; use a smarter malloc or overload the new/delete operators, but these are complex and do not solve the actual problem with lifetimes.

Using arenas by default simplifies lifetime management immensely: When does an object's lifetime end? When its containing arena kicks it out. This is simple, because it can only happen when popping from or clearing the arena, which also happens when the arena is destroyed.

But enough proselytization.

Basic Design

It's very easy to adapt the fundamental arena interface:

class Arena
{
public:
  // create or destroy a 'stack' - an "arena"
  static Arena* Create();
  static void Destroy(Arena* arena);

  // push some bytes onto the 'stack' - the way to allocate
  void* Push(u64 bytes, u64 alignment = 1);

  // get the # of bytes currently allocated.
  u64 GetUsage();
 
  // also some useful popping helpers:
  void PopUsageTo(u64 count);
  void Clear();
};

It's workable, but not particularly easy to use. It can be improved by introducing type information about what it is allocating by using templates:

template<typename T>
T* Place()
{
  void* mem = Push(sizeof(T), alignof(T));
  return static_cast<T*>(mem);
}

It is also useful to wrap a common pattern for allocating an array. This one chooses not to initialize anything, and notes that in the name. I find this to be a good thing to do, as it makes the user think about the fact the memory is uninitialized.

template<typename T>
T* PlaceArrayUninitialized(u64 count)
{
  return static_cast<T*>(Push(count * sizeof(T), alignof(T)));
}

When designing interfaces like this that use templates only for code ergonomics, I prefer to keep the amount of templatized code as small as possible and leave most of the details to the concrete implementation. This is one technique for preventing code bloat and long compile times from monomorphization.

C++isms

At the language level, C++ has a lot more to say about object lifetimes than C. Lifetimes must be properly "begun", and unexpected things will happen if destructors are not called before lifetimes end.2

Beginning lifetimes

Currently, Place does not properly handle beginning the lifetime of T, except in trivial cases where it is a plain struct. This can be fixed by beginning the lifetime of the object before returning it by using placement new.

return static_cast<T*>(new (mem) T{});

The lifetime is now properly begun and we are free of undefined behavior, but it can now only be used on types that are constructible with no arguments (default-constructible). The pattern used in STL containers that support emplace is to accept arguments of any type and pass them to the constructor. Place is essentially the same thing, so we will use the same technique.

template<typename T, typename... Args>
T* Place(Args&&... args)
{
  void* mem = Push(sizeof(T), alignof(T));
  return static_cast<T*>(new (mem) T{ std::forward<Args>(args)... });
}

Destructors

So far, the arena will work, but it behaves in a very unexpected way when ending the lifetimes of contained objects - the destructors are not called. Generally, container-like constructs in C++ are supposed to call the destructors of the objects they contain, but that's not happening yet.

First we need to be able to store destructors. In C++, it's not possible to take the address of a destructor (or of a constructor for that matter, though both have addresses.) Herb Sutter has a post that covers a nice solution. The gist of it is that we can use a captureless lambda inside a template to capture the type and call the destructor. This compiles directly to the address of the destructor, which is great. It looks like this:

struct Destructor
{
  template<typename T>
  static Destructor Create(T const* object)
  {
    return Destructor{
      .bound_object = object,
      .destroy = +[](void const* x) { static_cast<T const*>(x)->~T(); }
    };
  }

  void operator()() const
  {
    destroy(bound_object);
  }

  void const* bound_object;
  void(*destroy)(void const*);
};

Now whenever placing an object in the arena, we also will create a destructor object for it if it needs one.

void* mem = nullptr;
if constexpr (std::is_trivially_destructible_v<T>)
{
  mem = Push(sizeof(T), alignof(T));
}
else
{
  mem = PushWithDestructor(sizeof(T), alignof(T), Destructor::Create<T>(nullptr));
}

PushWithDestructor automatically fills in the address of the destructor, so it is passed as nullptr and the type explicitly specified. It also stores the destructor object in the arena's memory. In my arena, this is implemented by committing pages as needed from the back of the arena block's reservation and filling them with destructor objects as a downwards-growing stack. In the same way that traditionally the stack and heap segments of a process grew towards each other, so do the data section in the arena and the bookkeeping section filled with destructors grow towards each other.

The destructor objects are invoked and removed in the reverse order that objects were added to the arena, just like the built in stack. When popping from the arena, we can simply walk the destructors and check if each pointer is beyond the current end of the data section, and stop once it is not.

2026 note: This destructor class should be made to operate on arrays of objects instead of single objects. I've made this change in my own codebase but did not update this post. Also, some of this could be replaced with std::construct_at and std::destroy_at if one was so inclined.

More Sugar

In a codebase written to use arenas as the memory management strategy, types parameterized with arenas are very common. Placing such an object with our current setup looks like this:

CallExpression* call = arena->Place<CallExpression>(arena, callee, arguments);

It's awkward to need to pass arena twice in the same function call (recall that the left-hand instance becomes the this pointer.) Since the implementation of Place already has the arena as a parameter, it can pass it whenever possible.

if constexpr (std::is_constructible_v<T, Arena*, Args...>)
{
  return static_cast<T*>(new (mem) T(this, std::forward<Args>(args)...));
}
else
{
  return static_cast<T*>(new (mem) T{ std::forward<Args>(args)... });
}

This will automatically insert the arena as the first parameter if possible, making for seamless parameterization.

CallExpression* call = arena->Place<CallExpression>(callee, arguments);

As a bonus, it's still possible to call with the explicit arena parameter, since that will modify Args and reject the implicit self-insertion.

Closing

That's about it for some of the details and reasoning behind C++ arenas! They are a fantastically useful concept and I hope that you gained enough value from this to try using this memory management strategy in your own C++ projects.

This is the first post on /prog/, if you liked it you can subscribe through RSS.

Bye for now, and see you soon!
~Zardium

Footnotes