Data structures for traversable memory pool

Question

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.

Answer 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.