{"id":5117,"date":"2017-01-09T21:41:19","date_gmt":"2017-01-09T21:41:19","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/memory-pool-allocators-with-jonathan-mueller\/"},"modified":"2023-09-18T17:23:22","modified_gmt":"2023-09-18T17:23:22","slug":"memory-pool-allocators-with-jonathan-mueller","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/memory-pool-allocators-with-jonathan-mueller\/","title":{"rendered":"Memory Pool Allocators by Jonathan M\u00fcller"},"content":{"rendered":"

After I have written a few posts about memory management <\/a>in C++, I’m very glad to present Jonathan M\u00fcller, which will write a guest post about his implementation of the memory<\/a> 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 <\/a>episodes, he presented his ideas to a worldwide audience.<\/p>\n

<\/p>\n

The motivation<\/h2>\n

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:<\/a><\/p>\n

“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<\/a>. This library is another. But instead of trying to change the STL, it works with the current implementation<\/em>.”<\/p>\n

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<\/a>: How I have beaten Boost.Pool.<\/strong> In particular, his explanations of the different optimization strategies for memory allocations provide deep insight and have a broader focus.
<\/strong><\/p>\n

But now, let’s start with Jonathan M\u00fcller’s post, translated from German to English by Rainer Grimm.<\/p>\n<\/p>\n

Memory pool allocator<\/h2>\n

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<\/strong>.  The allocation removes the first element of the <\/span>free list<\/span><\/strong> 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.<\/p>\n

Now, I will show how you can use the pool implementation of my memory library<\/a> for your own allocation.<\/p>\n

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.<\/p>\n

The memory pool<\/span><\/h3>\n

If you’ve installed<\/a> my library, the memory pool will be quite easy to use.<\/p>\n

#include <foonathan\/memory\/memory_pool.hpp><\/span>\r\n#include <foonathan\/memory\/namespace_alias.hpp> <\/span>\/\/ (1)<\/span>\r\n\r\nint<\/span> main()\r\n{\r\n    memory::memory_pool<> pool(16, 4096); \/\/ (2)<\/span>\r\n    void<\/span>* node = pool.allocate_node(); \/\/ (3)<\/span>\r\n    \/\/ ...<\/span>\r\n    pool.deallocate_node(node); \/\/ (4)<\/span>\r\n} \r\n<\/pre>\n
After you have included the necessary headers (1), you can use a memory pool (2).  The header namespace_alias.hpp<\/span> automatically gives you the alias<\/a> for the long namespace names foonathan::memory. <\/span>The constructor has two parameters. The first one is the size of each block in the free list,<\/strong> the so-called node<\/strong> size.<\/strong> The second one is the size of the big memory block, which will be divided into <\/span>4KiB parts.<\/p>\n
Now, you can request small memory blocks from the pool, so-called nodes<\/strong> (3), and release them (4). Each node<\/strong> 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<\/strong> – even if there was no call deallocate_node().<\/span><\/p>\n
But it is quite tedious to use the pool in such a way. Therefore, the concept of RawAllocator <\/span>comes to our rescue. This is the critical abstraction.<\/p>\n
The RawAllocator<\/span><\/h3>\n
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<\/a>, 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><\/p>\n
 A RawAllocator<\/span> has the following interface:<\/p>\n
struct<\/span> raw_allocator\r\n{\r\n    using<\/span> is_stateful = std::integral_constant<bool<\/span>, Value>; \/\/ optional, default is std::is_empty<\/span>\r\n\r\n    void<\/span>* allocate_node(std::size_t<\/span> size, std::size_t<\/span> alignment); \/\/ required, allocates memory<\/span>\r\n    void<\/span> deallocate_node(void<\/span> *node, std::size_t<\/span> size, std::size_t<\/span> alignment) noexcept; \/\/ required: releases memory<\/span>\r\n\r\n    void<\/span>* allocate_array(std::size_t<\/span> count, std::size_t<\/span> size, std::size_t<\/span> alignment); \/\/ optional: invokes by default allocate_node() <\/span>\r\n    void<\/span> deallocate_array(void<\/span> *ptr, std::size_t<\/span> count, std::size_t<\/span> size, std::size_t<\/span> alignment) noexcept; \/\/ optional: invokes by default deallocate_node()<\/span>\r\n\r\n    std::size_t<\/span> max_node_size() const<\/span>; \/\/ optional: returns by default the maximum value<\/span>\r\n    std::size_t<\/span> max_array_size() const<\/span>; \/\/ optional: returns by default max_node_size()<\/span>\r\n    std::size_t<\/span> max_alignment() const<\/span>; \/\/ optional: returns by default maximum alginment, e.g.: alignof(std::max_align_t)<\/span>\r\n}\r\n<\/pre>\n
The interface is quite similar to the new std::pmr::memory_resource<\/a> but is not implemented with inheritance. Therefore, the RawAllocator<\/span> is, by default, part of the type and can only optionally be <\/span>type erased <\/span><\/strong>by using the any_allocator_reference <\/span>class. <\/span><\/p>\n
Most interface parts are optional and must only be implemented for special use cases. Although the memory_pool<\/span> does not implement the interface, it is a RawAllocator.<\/span> This is possible because each access is via the memory::allocator_traits<\/span>, which are specialized by the memory_pool.<\/span><\/p>\n
To use the RawAllocator<\/span> in the STL containers, there is the adapter std_allocator<\/span> which gets a RawAllocator<\/span> and adjusts it to the interface of an Allocator.<\/span> Allocator<\/span> has to be copyable, but RawAllocator<\/span>sg is not. Therefore, it stores the RawAllocator<\/span> by reference.<\/p>\n
Because memory pools have issues with the requirements of an array, they are ideal candidates for node-based containers<\/span>. Here is an example:<\/span><\/p>\n
#include <set><\/span>\r\n\r\n#include <foonathan\/memory\/container.hpp><\/span>\r\n#include <foonathan\/memory\/memory_pool.hpp><\/span>\r\n#include <foonathan\/memory\/namespace_alias.hpp><\/span>\r\n\r\nint<\/span> main()\r\n{\r\n    memory::memory_pool<> pool(memory::set_node_size<int<\/span>>::value, 4096); \/\/ (1)<\/span>\r\n    memory::set<int<\/span>, decltype(pool)> set(pool); \/\/ (2)<\/span>\r\n    set.insert(3);\r\n    \/\/ ...<\/span>\r\n} \r\n<\/pre>\n
You can create – as previously – your pool (1). The given node size<\/strong> is exactly the size that a std::set<int><\/span> needs. Now I use this size for the set in (2). The type of container is memory::set.<\/span> This is not a new implementation of a std::set<\/span> but only a template alias. In this case a template alias<\/strong> for std::set<int, std::less<int>, memory::std_allocator<int, decltype(pool)>><\/span>. Therefore, a std::set<int> uses the pool through the std_allocator<\/span>. The called constructor is the regular constructor of std::set<\/span>. We use the fact that a RawAllocator can implicitly create the memory::std_allocator.<\/p>\n
Now, the usage of the set is as always. Our pool does all allocation.<\/p>\n
Internally adjustment of the pool allocation<\/h3>\n
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. <\/span>This RawAllocator <\/span>delegates its task to OS-specific functions such as HeapAlloc()<\/span> on Windows.<\/p>\n
But you can use template arguments to adjust the internal allocator.<\/p>\n
One combination of allocators is quite helpful. For example, we want to have a std::vector<\/span> that is located on the stack instead of the heap. <\/span>
 That is simple: We use a std::array<\/span> or a C array.<\/span><\/p>\n
But what does it look like if we want to have a std::set<\/span> on the stack?<\/p>\n
#include <set><\/span>\r\n\r\n#include <foonathan\/memory\/container.hpp><\/span>\r\n#include <foonathan\/memory\/memory_pool.hpp><\/span>\r\n#include <foonathan\/memory\/namespace_alias.hpp><\/span>\r\n#include <foonathan\/memory\/static_allocator.hpp><\/span>\r\n\r\nint<\/span> main()\r\n{\r\n    memory::static_allocator_storage<4096u> storage; \/\/ (1)<\/span>\r\n\r\n    using<\/span> static_pool = memory::memory_pool<memory::node_pool, memory::static_allocator>; \/\/ (2)<\/span>\r\n    static_pool pool(memory::set_node_size<int<\/span>>::value, 4096, storage); \/\/ (3)<\/span>\r\n\r\n    memory::set<int<\/span>, decltype(pool)> set(pool);\r\n    set.insert(3);\r\n    \/\/ ...<\/span>\r\n} \r\n\r\n<\/pre>\n
In this example, we combine the memory_pool<\/span> with the static_allocator<\/span> for the internal memory allocation. Like heap_allocator<\/span>, you can use static_allocator<\/span> as RawAllocator directly, but it makes more sense with a memory_pool<\/span>. The allocators of memory<\/strong> are quite easy to combine to implement various strategies.<\/p>\n
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<\/span> 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<\/span>. The second parameter is the type of internal allocator. Here we use memory::static_allocator<\/span>.  We construct the pool in (3). This time we also have to give the storage <\/span>needed by the memory::static_allocator.<\/span><\/span><\/p>\n
Now we can create our set<\/span> that is located on the stack.<\/p>\n
  The internal allocator is a BlockAllocator <\/span>and not a RawAllocator<\/span> 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.<\/p>\n
Several pools<\/h3>\n
A memory_pool can only manage the memory of a specific size.<\/span>
 If you need several sizes, you have to set the node size<\/strong> to its maximum and waste memory for smaller sizes, or you have to use several pools and choose the best fitting.<\/p>\n
The second alternative will be done in the memory::memory_pool_collection<\/span> 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<\/span>. The second one is the distribution policy. These can be memory::identity_buckets<\/span> – a pool of fixed size – or memory::log2_buckets<\/span> – a pool for each power of two. The third one is – like in the regular pool – the allocator, which is used for internal memory.<\/p>\n
Please note that all pools share unused memory; each pool takes its share as needed.<\/p>\n
 The usage is similar to the regular memory_pool<\/span>. Therefore, I skip the example.<\/p>\n
Please note that the node size<\/strong> in the constructor is the maximum<\/strong> size and that the allocate_node()<\/span> function needs a size.
 Thanks to the RawAllocator<\/span> is, the usage for STL containers, etc. identical.<\/p>\n
Conclusion<\/h3>\n
There are a lot of libraries implementing pools. memory<\/strong> 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<\/span> class for std::unique_ptr. <\/span>In addition, I didn’t mention the  allocator_storage<\/span> functionality implemented by allocator_reference<\/span>.<\/p>\n
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.<\/p>\n
If you want to know more about memory, watch my talk at Meeting C++.<\/a><\/p>\n
Of course, you can also follow me on Twitter or visit my blog.<\/a><\/p>\n
What’s next?<\/h2>\n
This is my last post about embedded programming with C++ and memory management. The next post<\/a> will be about functional programming in C++.<\/p>\n
 <\/p>\n
 <\/p>\n
<\/a> <\/p>\n
 <\/a><\/p>\n
<\/span><\/p>\n
 <\/div>\n
\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
After I have written a few posts about memory management in C++, I’m very glad to present Jonathan M\u00fcller, 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. […]<\/p>\n","protected":false},"author":21,"featured_media":8269,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[364],"tags":[556,498,493],"class_list":["post-5117","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-embedded","tag-allocator","tag-memory","tag-new-delete"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5117","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5117"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5117\/revisions"}],"predecessor-version":[{"id":6899,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5117\/revisions\/6899"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/8269"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}