Memory Pool Allocators by Jonathan Müller

After I have written a few posts about memory management in C++, I'm very glad to present Jonathan Müller, which will write a guest post about his implementation of the memory library. He will explain to us his concepts about his design. Jonathan is known as an expert in memory management in the C++ community. In the  59 episodes, he presented his ideas to a worldwide audience.

The motivation

At first, there is the question. Why did Jonathan write a library in C++ for memory management? Of course, he answered the question himself on his github project memory:

"The C++ STL allocator model has various flaws. For example, they are fixed to a certain type, because they are almost necessarily required to be templates. So you can't easily share a single allocator for multiple types. In addition, you can only get a copy from the containers and not the original allocator object. At least with C++11 they are allowed to be stateful and so can be made object not instance based. But still, the model has many flaws. Over the course of the years, many solutions have been proposed. for example EASTL. This library is another. But instead of trying to change the STL, it works with the current implementation."

But that is not the full answer. More promising is his provoking statement to the performance of his library, which he proofs in four very readable posts: How I have beaten Boost.Pool. In particular, his explanations of the different optimization strategies for memory allocations provide deep insight and have a broader focus.

But now, let's start with Jonathan Müller post, translated from German to English by Rainer Grimm.

Memory pool allocator

A memory pool allocator is a generally usable and fast allocator. It allocates only big memory blocks and divides them into equally sized pieces. All free pieces are stored in a so-called free list.  The allocation simply removes the first element of the free list and returns it. Deallocation pushes it at the back. That is quite fast but you can only use it for pieces of a fixed size. If not you have fragmentation issues and therefore need a long time for finding the fitting piece.

Now, I will show how you can use the pool implementation of my memory library for your own allocation.

memory is a library that provides different allocators and their infrastructure to use without any issues. The current version is 0.x and therefore in the development phase.

The memory pool

If you've installed my library, the memory pool will be quite easy to use.

#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp> // (1)

int main()
{
    memory::memory_pool<> pool(16, 4096); // (2)
    void* node = pool.allocate_node(); // (3)
    // ...
    pool.deallocate_node(node); // (4)
} 

After you have included the necessary headers (1) you can use a memory pool (2).  The header namespace_alias.hpp gives you automatically the alias for the long namespace names foonathan::memory. The constructor has two parameters. The first one is the size of each block in the free list, the so-called node size. The second one is the size of the big memory block, which will be divided into 4KiB parts.

Now, you can request small memory blocks from the pool, so-called nodes (3) and release them (4). Each node is as big as specified in the constructor. In this example 16 Bytes. Of course, the release of the big memory block in the destructor of the pool will automatically release all nodes - even if there was no call deallocate_node().

But it is quite tedious to use the pool in such away. Therefore, the concept of RawAllocator come to our rescue. This is the key abstraction.

The RawAllocator

In a previous chapter, the concept of the Allocator was presented. With it, you can adjust the memory requirements of the STL containers. The allocator concepts are not so easy to get and it combines the creation of the object with the allocation of the memory. That is usually not necessary. Most of the times you only want to adjust how the memory is managed. This is the use case for RawAllocator.

A RawAllocator has the following interface:

struct raw_allocator
{
    using is_stateful = std::integral_constant<bool, Value>; // optional, default is std::is_empty

    void* allocate_node(std::size_t size, std::size_t alignment); // required, allocates memory
    void deallocate_node(void *node, std::size_t size, std::size_t alignment) noexcept; // required: releases memory

    void* allocate_array(std::size_t count, std::size_t size, std::size_t alignment); // optional: invokes by default allocate_node() 
    void deallocate_array(void *ptr, std::size_t count, std::size_t size, std::size_t alignment) noexcept; // optional: invokes by default deallocate_node()

    std::size_t max_node_size() const; // optional: returns by default the maximum value
    std::size_t max_array_size() const; // optional: returns by default max_node_size()
    std::size_t max_alignment() const; // optional: returns by default maximum alginment, e.g.: alignof(std::max_align_t)
}

The interface is quite similar to the new std::pmr::memory_resource, but it is not implemented with inheritance. Therefore, the RawAllocator is by default part of the type and can only optionally be type erased by using the any_allocator_reference class.

Most parts of the interface are optional and only needs to be implemented for special use cases. Although the memory_pool does not implement the interface, it is a RawAllocator. This is possible because each access is via the memory::allocator_traits, which are specialised by the memory_pool.

To use the RawAllocator in the STL containers there is the adapter std_allocator which gets an RawAllocator and adjust it to the interface of an Allocator. Allocator has to be copyable, but RawAllocatorsg not, therefore it stores the RawAllocator by reference.

Because memory pools have issues with the requirements of an array, they are ideal candidates for node based containers. Here is an example:

#include <set>

#include <foonathan/memory/container.hpp>
#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp>

int main()
{
    memory::memory_pool<> pool(memory::set_node_size<int>::value, 4096); // (1)
    memory::set<int, decltype(pool)> set(pool); // (2)
    set.insert(3);
    // ...
} 

You can create - as previously - your pool (1). The given node size is exactly the size that a std::set<int> needs. Now I use this size for the set in (2). The type of container is memory::set. This is not a new implementation of a std::set but only a template alias. In this case a template alias for std::set<int, std::less<int>, memory::std_allocator<int, decltype(pool)>>. Therefore, it is a std::set<int> that uses the pool through the std_allocator. The called constructor is the regular constructor of std::set. We use the fact that the memory::std_allocator can implicitly be created by a RawAllocator.

Now, the usage of the set is as always. All allocation is done by our pool.

Internally adjustment of the pool allocation

As I previously mentioned a pool request a big memory block and divides it into small pieces. By default, it uses memory::heap_allocator for that. This is a RawAllocator that delegates its task to OS-specific functions such as HeapAlloc() on Windows.

But you can use template arguments to adjust the internal allocator.

One combination of allocators is quite useful. For example, we want to have a std::vector that is totally located on the stack instead of the heap.
That is simple: We use a std::array or a C array.

But how does it look like if we want to have a std::set on the stack?

#include <set>

#include <foonathan/memory/container.hpp>
#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp>
#include <foonathan/memory/static_allocator.hpp>

int main()
{
    memory::static_allocator_storage<4096u> storage; // (1)

    using static_pool = memory::memory_pool<memory::node_pool, memory::static_allocator>; // (2)
    static_pool pool(memory::set_node_size<int>::value, 4096, storage); // (3)

    memory::set<int, decltype(pool)> set(pool);
    set.insert(3);
    // ...
} 

In this example, we combine the memory_pool with the static_allocator for the internal memory allocation. Like heap_allocator you can use static_allocator as RawAllocator directly but it makes more sense with a memory_pool. The allocators of memory are quite easy to combine to implement various strategies.

At first, we create the memory which will be used by the static_allocator for its memory requests in (1). The alias in (2) defines our new pool type. memory::memory_pool has two template parameters. The first one is the type of pool, which you can adjust for different requirements. The default is memory::node_pool. The second parameter is the type of the internal allocator. Here we use memory::static_allocator.  We construct the pool in (3). This time we also have to give the storage which is needed by the memory::static_allocator.

Now we can create our set that is located on the stack.

 The internal allocator is exactly speaking a BlockAllocator and not a RawAllocator because you can directly control how big the blocks will become if the first block is out of memory. Template magic makes sure that you can give a RawAllocator, which becomes a BlockAllocator automatically.

Several pools

A memory_pool can only manage the memory of a certain size.
If you need several sizes, you have to set the node size to its maximum and waste memory for smaller sizes or you have to use several pools and choose the best fitting.

The second alternative will be done in the memory::memory_pool_collection automatically.  The class uses several pools and chooses the right one. It's a template with three parameters. The first one is the type of pool, which is most of the time's memory::node_pool. The second one is the distribution policy. These can be memory::identity_buckets - a pool of fixed size - or memory::log2_buckets - a pool for each power of two. The third one is - like in the regular pool - the allocator, which is used for the internal memory.

Please note that all pools share the already unused memory and each pool takes its share as needed.

The usage is similar to the regular memory_pool, therefore I skip the example.

Please note, that the node size in the constructor is the maximum size and that the allocate_node() function needs a size.
Thanks to the RawAllocator is the usage for STL containers etc. identical.

Conclusion

There are a lot of libraries implementing pools. memory is the only one having all allocators for your needs. I did not present the whole functionality in this post. There are a lot more allocators and adapters. For example a Deleter class for std::unique_ptr. In addition, I didn't mention the  allocator_storage functionality that is implemented by allocator_reference.

The library is designed in such a way that you can simply put the allocator you need where you need it. But you can also fine-tune each detail if that's required.

If you want to know more about memory, watch my talk at Meeting C++.

Of course, you can also follow me on Twitter or visit my blog.

What's next?

This is my last post about embedded programming with C++ and memory management in particular. The next post will be about functional programming in C++.