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 complete answer. More promising is his provoking statement about the performance of his library, which he proves 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’s 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 removes the first element of the free list and returns it. Deallocation pushes it at the back. That is relatively fast, but you can only use it for fixed-size pieces. 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 without issues. The current version is 0.x and, therefore, in the development phase.

Modernes C++ Mentoring

"Fundamentals for C++ Professionals" (open)

"Design Patterns and Architectural Patterns with C++" (open)

"C++20: Get the Details" (open)

"Concurrency with Modern C++" (open)

"Generic Programming (Templates) with C++": October 2024

"Embedded Programming with Modern C++": October 2024

"Clean Code: Best Practices for Modern C++": March 2025

Do you want to stay informed: Subscribe.

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 automatically gives you 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 big memory block’s release in the pool’s destructor will automatically release all nodes – even if there was no call deallocate_node().

But it is quite tedious to use the pool in such a way. Therefore, the concept of RawAllocator comes to our rescue. This is the critical 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 time, 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 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 interface parts are optional and must only 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 specialized by the memory_pool.

To use the RawAllocator in the STL containers, there is the adapter std_allocator which gets a RawAllocator and adjusts it to the interface of an Allocator. Allocator has to be copyable, but RawAllocatorsg is 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, a std::set<int> uses the pool through the std_allocator. The called constructor is the regular constructor of std::set. We use the fact that a RawAllocator can implicitly create the memory::std_allocator.

Now, the usage of the set is as always. Our pool does all allocation.

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 RawAllocator 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 helpful. For example, we want to have a std::vector that is located on the stack instead of the heap.
That is simple: We use a std::array or a C array.

But what 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 the static_allocator will use 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 internal allocator. Here we use memory::static_allocator. We construct the pool in (3). This time we also have to give the storage needed by the memory::static_allocator.

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

The internal allocator is 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 ensures you can give a RawAllocator, which automatically becomes a BlockAllocator.

Several pools

A memory_pool can only manage the memory of a specific 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 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 internal memory.

Please note that all pools share unused memory; 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 implemented by allocator_reference.

The library is designed so that you can 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. The next post will be about functional programming in C++.

Post Views: 10,514

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery,and Matt Godbolt.

Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

My special thanks to Embarcadero
My special thanks to PVS-Studio
My special thanks to Tipi.build
My special thanks to Take Up Code
My special thanks to SHAVEDYAKS