What are the usual im­ple­men­ta­tion de­tails be­hind mem­ory pools?

Question

I am try­ing to un­der­stand us­ing mem­ory pools for mem­ory man­age­ment, but I can't find much about it, even though it seems to be a very com­mon mech­a­nism.

All I know about this is that "Me­mory pools, also called fixed-size blocks al­lo­ca­tion" per Wiki­pedia, and I can use those chunks to al­lo­cate mem­ory for my ob­jects.

Is there any stan­dard spec­i­fi­ca­tions about mem­ory pools?

I would like to know how this works on the heap, how it can be im­ple­mented, and how this should be used?

From this ques­tion about C++11 mem­ory pool de­sign pat­terns, I've read:

In case you haven't al­ready, fa­mil­iar­ize your­self with Boost.Pool. From the Boost doc­u­men­ta­tion:

What is Pool?

Pool al­lo­ca­tion is a mem­ory al­lo­ca­tion scheme that is very fast, but lim­ited in its us­age. For more in­for­ma­tion on pool al­lo­ca­tion (also called sim­ple seg­re­gated stor­age, see con­cepts con­cepts and Sim­ple Se­gre­gated Stor­age.

I can un­der­stand what he meant, but that doesn't help me un­der­stand how to use them and how mem­ory pools can help my ap­pli­ca­tion, how to ac­tu­ally make use of them.

A sim­ple ex­am­ple that shows how to use mem­ory pools would be ap­pre­ci­ated.

Jewry

Have a look at boost::pool – Tarragona

Also see: #16378806 – Recess

Maybe this helps: Memory Management – Groundhog

Thanks for boost::pool, @Recess I already read that question, but it doesn't show the basic concepts of memory pools, thank's anyway – Jewry

The basic premise is to cache or not returned allocated memory back to the OS, also if you frequently request the same size of memory then it can be more efficient to allocate up front and then recycle this when the client requests and returns the memory, you can think of this general principle being applied to threads, handles, sockets etc basically any resource that is relatively expensive to allocate – Chilcote

Answer 1

Any kind of "pool" is really just resources you've acquired/initialized in advance so that they're already ready to go, not allocated on the fly with each client request. When clients finish using them, the resource returns to the pool instead of being destroyed.

Memory pools are basically just memory you've allocated in advance (and typically in big blocks). For example, you might allocate 4 kilobytes of memory in advance. When a client requests 64 bytes of memory, you just hand them a pointer to an unused space in that memory pool for them to read and write whatever they want. When the client is done, you can just mark that section of memory as being unused again.

As a basic example which doesn't bother with alignment, safety, or returning unused (freed) memory back to the pool:

class MemoryPool
{
public:
    MemoryPool(): ptr(mem) 
    {
    }

    void* allocate(int mem_size)
    {
        assert((ptr + mem_size) <= (mem + sizeof mem) && "Pool exhausted!");
        void* mem = ptr;
        ptr += mem_size;
        return mem;
    }

private:
    MemoryPool(const MemoryPool&);
    MemoryPool& operator=(const MemoryPool&);   
    char mem[4096];
    char* ptr;
};

...
{
    MemoryPool pool;

    // Allocate an instance of `Foo` into a chunk returned by the memory pool.
    Foo* foo = new(pool.allocate(sizeof(Foo))) Foo;
    ...
    // Invoke the dtor manually since we used placement new.
    foo->~Foo();
}

This is effectively just pooling memory from the stack. A more advanced implementation might chain blocks together and do some branching to see if a block is full to avoid running out of memory, deal with fixed-size chunks that are unions (list nodes when free, memory for the client when used), and it definitely needs to deal with alignment (easiest way is just max align the memory blocks and add padding to each chunk to align the subsequent one).

More fancy would be buddy allocators, slabs, ones applying fitting algorithms, etc. Implementing an allocator is not so different from a data structure, but you get knee deep in raw bits and bytes, have to think about things like alignment, and can't shuffle contents around (can't invalidate existing pointers to memory being used). Like data structures, there isn't really a golden standard that says, "thou shalt do this". There's a wide variety of them, each with their own strengths and weaknesses, but there are some especially popular algorithms for memory allocation.

Implementing allocators is something that I would actually recommend to many C and C++ developers just to kind of get in tune with the way that memory management works a bit better. It can make you a bit more conscious of how the memory being requested connects to data structures using them, and also opens up a whole new door of optimization opportunities without using any new data structures. It can also make data structures like linked lists which are normally not very efficient much more useful and reduce temptations to make opaque/abstract types less opaque to avoid the heap overhead. However, there can be an initial excitement which might want to make you shoehorn custom allocators for everything, only to later regret the additional burden (especially if, in your excitement, you forget about issues like thread safety and alignment). It's worth taking it easy there. As with any micro-optimization, it's generally best applied discretely, in hindsight, and with a profiler in hand.

Phenothiazine

Thank you, this is exactly the answer I was looking for !! – Jewry

Answer 2

The basic concept of a memory pool is to allocate a large portion of memory for your application, and, later on, instead of using plain new to request memory from the O/S, you return a chunk of the previously allocated memory instead.

In order to make this work, you need to manage memory usage yourself and cannot rely on the O/S; i.e., you'll need to implement your own versions of new and delete, and use the original versions only when allocating, freeing, or potentially resizing your own memory pool.

The first approach would be to define one's own Class that encapsules a memory pool and provides custom methods that implement the semantics of new and delete, but take memory from the pre-allocated pool. Remember, this pool is nothing more than an area of memory that had been allocated using new and has an arbitrary size. The pool's version of new/delete return resp. take pointers. The simplest version would probably look like C code:

void *MyPool::malloc(const size_t &size)
void MyPool::free(void *ptr)

You can pepper this with templates to automatically add conversion, e.g.

template <typename T>
T *MyClass::malloc();

template <typename T>
void MyClass::free(T *ptr);

Notice that, thanks to the template arguments, the size_t size argument can be omitted since the compiler allows you to call sizeof(T) in malloc().

Returning a simple pointer means that your pool can only grow when there's adjacent memory available, and only shrink if the pool memory at its "borders" is not taken. More specifically, you cannot relocate the pool because that would invalidate all pointers your malloc function returned.

A way to fix this limitation is to return pointers to pointers, i.e., return T** instead of simply T*. That allows you to change the underlying pointer while the user-facing part remains the same. Incidentially, that has been done for the NeXT O/S, where it was called a "handle". To access the handle's contents, one had to call (*handle)->method(), or (**handle).method(). Eventually, Maf Vosburg invented a pseudo-operator that exploited operator precedence to get rid of the (*handle)->method() syntax: handle[0]->method(); It was called the sprong operator.

The benefits of this operation are: First, you avoid the overhead of a typical call to new and delete, and second, your memory pool ensures that a contiguous segment of memory is used by your application, i.e., it avoids memory fragmentation and therefore increases CPU cache hits.

So, basically, a memory pool provides you with a speedup you gain with the downside of a potentially more complex application code. But then again, there are some implementations of memory pools that are proven and can simply be used, such as boost::pool.

Cormophyte

I don't think more complex code is really the main downside. If done properly, the allocator module should be more or less self-contained (as proved by boost::pool). I think the main downside is the memory usage penalty necessary to implement memory pools. – Barre

Do you have some code of a simple implementation of memory pools ? – Jewry

I haven't tested it, but this looks reasonable: github.com/cacay/MemoryPool/blob/master/C-11/MemoryPool.tcc – Cormophyte

@Cormophyte Thank's for the link – Jewry

From the Department of Unimportant Corrections: Maf Vosburg named the handle[0]->method trick "sprong" not "sproing". His page (from 1998) has suffered from bitrot, alas, all I can find is that Wayback Machine reference. – Deer

@RobertCalhoun Not unimportant at all --- honor where honor's due. I edited my answer, even if its just for the archive. :) – Cormophyte

Answer 3

Basically, memory pools allow you to avoid some of the expense of allocating memory in a program that allocates and frees memory frequently. What you do is allocate a big chunk of memory at the beginning of execution, and reuse the same memory for different allocations that do not overlap temporally. You have to have some mechanism for keeping track of what memory is available and use that memory for allocations. When you're done with the memory, instead of freeing it, mark it as available again.

In other words, instead of calls to new/malloc and delete/free, make a call to your self-defined allocator/deallocator functions.

Doing this allows you to only do one allocation (assuming you know approximately how much memory you'll need in total) in the course of execution. If your program is latency- rather than memory-bound, you can write an allocation function that performs faster than malloc at the expense of some memory usage.

Barre