Memory Pool Allocators from Jonathan Müller

Contents[Show]

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 us his concepts about his design. Jonathan is known as an expert of memory management in the C++ community. In the  59 episode he presented his ideas to a world wide audiance.

The motivation

At first, there is the question. Why did Jonathan wrote 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 postsHow I have beaten Boost.Pool. In particular, his explanations to the different optimization strategies for memory allocations provide deep insight and have a broader focus.

But now, lets 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 in equally sized pieces. All free pieces are stored in a so called free list.  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 them 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 in 4KiB parts.

Now, you can request small memory blocks from the pool, so called nodes (3) and realase 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 relase 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 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 is 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 implemened 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 is 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 have 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 the 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> which 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 in 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 which 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 the 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 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 your 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 the 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 regularly 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 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 at twitter or visit my blog.

What's next?

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



 

 

 

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

Comments   

0 #1 bridal makeup mehndi 2017-02-03 22:21
Hey there! I've been following your website for slme time now
and finally got the courage to go ahead and give you a shout
out from Austin Texas! Just wanted to tell you keep up the fantastic work!
Quote

Add comment


My Newest E-Books

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 1276

All 512622

Currently are 155 guests and no members online