1

I am implementing a memory pool in C++, with the following constraints:

  • The allocated elements should be traversable in linear time in order of their memory address, to promote cache reuse.
  • It needs to be possible to deallocate elements (memory blocks) and return them to the memory pool.

Allocation and deallocation would happen frequently during the runtime of a real-time program, so needs to happen as fast as possible.

I have so far implemented this memory pool using two linked lists as stubs, one for the free and one for the allocated elements. This works, but is of course terribly slow, since every time an element is either freed or allocated, the element needs to be removed from one list and added to the other, which is linear. I would like this to be faster.

What data structures could I use to make (de)allocation as efficient as possible? I was thinking about using a red-black tree (or similar balancing BST) to store the allocated elements, and a priority queue for the free elements. This would make allocation and deallocation both O(log n).

Any advice on how I could improve this design? Other data structures I could use? Is it even possible to make a memory pool (with the above constraints) with constant time operations?

Edit: I should probably clarify that these data structures are meant only for storing and accessing the memory addresses, the memory blocks themselves are already allocated and contiguous.

Improve this question
10
  • A memory pool usually deals with fixed size memory blocks. Is that the case for you too ? If so, constant time operations are definitely possible. Commented Apr 28, 2014 at 16:26
  • Yes, the memory blocks are fixed size :) Can you elaborate on the constant time operations, given the constraints (traversable and deallocatable)? Commented Apr 28, 2014 at 16:34
  • Geez; it seems hard to believe that traversing a linked list is noticably slow. How big is it? You've said that the lists only contain pointers and that the memory is simply available or not so I'm not sure exactly what you would be deallocating. I'm assuming that all memory blocks were allocated at startup and so when you remove an address from one list you are simply indicating whether it is being used or whether it is free. Why not have a single list of addresses with a free indicator of some sort so that you aren't moving addresses back and forth between two lists? Commented Apr 28, 2014 at 16:49
  • The traversal becomes noticeable if it is done every (de)alloc, quite quickly surpassing the cost of a regular memory allocation/free, on a pool larger than 100 elements. The single list with free addresses is what is usually used. The problem is that I want to be able to traverse the used (non-free) items. Since it is often the case that only a very small percentage of the memory pool is used, a full traversal of the pool seems wasteful. Deallocation in this case is used for calling the destructor of the object in the memory block, and excluding the block from traversal from the outside. Commented Apr 28, 2014 at 16:59
  • algorithms such as lower_bound can be used on any forward iterator so if the addresses are kept sorted then that could save a little bit of time. Even better would be to just have one list of structures where each has the address and a free indicator. Then write a predicate to find the first free. Commented Apr 28, 2014 at 16:59

1 Answer 1

Reset to default
1

Since we're dealing with a memory pool with fixed size memory blocks, constant time operations can be achieved as follows eg. :

  • identify each memory block by its index into the pool (the address of the memory block can be easily derived from this index by block_address = base_address + index * block_size, and vice versa).
  • have a data structure for the metadata (to keep track of allocated and free blocks). One that works with the requirements, is a fixed size array with an item corresponding to each memory block (identified by the same index). Embedded in that array are two (doubly) linked lists (one for the allocated and one for the free blocks). Since these linked lists don't overlap, they can use the same prev and next pointers.

How does this fit the requirements :

  • linear time traversal : the memory blocks can be traversed either by their index (a free/allocated flag as part of the metadata is probably useful in that case), or by either of the two linked lists, depending on the requirements. Iterating over arrays and linked lists is done in linear time.
  • constant time allocation : allocating a memory block means getting the first item from the free list, and moving it into the allocated list (at the end eg.). Removing the first item of a linked list, and appending an item to the end of a linked list are both constant time operations (assuming a pointer to the start and/or end of the linked list is kept - making the lists circular can help). The index/address of the block is then returned.
  • constant time deallocation : deallocating a memory block means identifying the corresponding metadata item by its index, and moving it from the allocated list into the free list (at the end eg.). Getting an item by its index from an array, removing a given item from a (doubly) linked list, and appending an item to the end of a linked list, are all constant time operations.
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for your answer, very clear explanation :) I think this works pretty good, but it breaks the constraint of traversal of the blocks in order of their memory addresses when using the linked list for traversal. Simply traversing the complete array has some pretty bad worst-cases (still linear, but relative to the number of allocated blocks) when the allocated blocks get spread out over the array. Ideally, I would keep both linked lists sorted, but the methods I can think of for that are too expensive. Hence my idea of maybe using a red-black tree and priority queue to store the metadata.
@KillerSponge : as soon as you bring a sorted data structure in the mix, you're gonna deal with logarithmic time complexity for allocation and de-allocation. Having to go over an array linearly, skipping blocks based on an allocated flag, is a bit unfortunate indeed, but it's the lowest price to pay that I can come up with to meet your requirements. Fortunately, the metadata array will probably be kept cached, making the price mostly negligible.
@KillerSponge : additionally, an important part of a good memory pool, is to size it properly for your application's needs. If you're constantly having a large percentage of the blocks free, then maybe the pool should be smaller. If you're dealing with high peaks and long valleys of pool usage, maybe a small-ish base pool (just large enough for the valleys), and a (larger?) overflow pool (for the peaks) is what you need.
I was afraid of the logarithmic lower bound... The overflow pool idea is interesting, I'm going to look into that and do some comparisons. Thanks! :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.