Memory pooling?

You can make allocation and deallocation O(1) easily. All you have to do is keep track of free blocks(linked list, stack, pick your favorite data structure that has a O(1) insert and remove) Setting up the pool will consume a bit of time as you build the data structure, but that should happen rarely.

before each slot in your memory pool, you should have 4 bytes for a next pointer. Initially, you go through and say first next = next, so the pointers are like..


1,2,3,4,5,6,7,8,9, NULL (last slot in pool points to NULL)

Your pool has a first_available pointer, pointing to 1. When you add an object to 1, your first_available points to 1's next = 2.

Now if you remove 1, just make 1's next = to first_available, and make the oldfirst available point to 1.

Write it out step by step if you dont understand that.

If you're creating a pool of pre-determined size, then you know how many slots there are. You can keep a queue of slots that are free, and dish them out in constant-time by grabbing the head slot. The queue itself doesn't need any allocations either since you know the maximum number of slots and can pre-allocate all the memory it needs, plus if you make it a circular buffer all operations on it can be done in constant-time. De-allocation is just the opposite, you push the slot back onto the queue. Given that the pool is contiguous¹ and each element is a known size, you can easily devise a mapping from pointer-to-slot (since memory is free'd based on the pointer, slots are only used inside the pool manager) that runs in constant-time as well.

So to answer your question, yes [smile]

¹My entire post assumes a contiguous pool of objects.

[EDIT - ninja'd repeatedly [smile]]

One technique, assuming your object is larger than the size of a pointer is to create a helper structure:

union helper_union;{    my_object o;    helper_union *next;};

Your pool managing class maintains a "head" pointer to this type.

When you first create your pool, you run though it, casting each my_object sized section to helper_union* then setting the next pointer to point to the next block in the pool.

So you end up with the head pointer pointing to a daisy chain of helper_unions running through the pool.

Now to allocate, you just take the address pointed to by the head, store it, set the head to its next value and return it. O(1).

Once you are up and running, there is no need to store these in the order they occur in the pool, so deallocation can just be - take node to deallocate, do the actual destruction of the contents, cast the node to helper_union, set its next to what head points at then point head at it. O(1) again.

Sorry if this explanation is a bit rubbish - I've only read about this method and never actually implemented it. The advantage is that in terms of storage, only one extra pointer in addition to the actual pool memory is required.

Just to note that boost seems to have a different notion of pool allocation. The idea is that objects can be allocated freely at any time, but that cleanup of the memory (/and maybe calling destructors) occurs at fixed points in program execution. The idea is that you can avoid the organisation (additional space and run complexity) required to manage a free list in cases where a unit of execution need to perform lots of allocations which are then never subsequently needed. Otherwise I dont see a lot of difference with std::allocator which is type specialized and may be instantiated once for multiple uses and which also supports deallocation at any time.

Quote:

Original post by EasilyConfused [EDIT - ninja'd repeatedly [smile]] One technique, assuming your object is larger than the size of a pointer is to create a helper structure: union helper_union;{ my_object o; helper_union *next;}; Your pool managing class maintains a "head" pointer to this type. When you first create your pool, you run though it, casting each my_object sized section to helper_union* then setting the next pointer to point to the next block in the pool. So you end up with the head pointer pointing to a daisy chain of helper_unions running through the pool. Now to allocate, you just take the address pointed to by the head, store it, set the head to its next value and return it. O(1). Once you are up and running, there is no need to store these in the order they occur in the pool, so deallocation can just be - take node to deallocate, do the actual destruction of the contents, cast the node to helper_union, set its next to what head points at then point head at it. O(1) again. Sorry if this explanation is a bit rubbish - I've only read about this method and never actually implemented it. The advantage is that in terms of storage, only one extra pointer in addition to the actual pool memory is required.

Union with a pointer to embed a freelist in the pool area, is exactly the trick I was going to suggest.
You've pretty much described exactly what I've sometimes used.

There is another variant of this approach though that's worth mentioning. By sacrificing a tiny amount in the speed of allocation, you can bring the initialisation of the pool down to constant time as well. Basically you introduce another pointer which points to the end of the used portion of the pool. Naturally you initialise this to point to the start, and the freelist-head to NULL. Whenever the freelist-head is NULL, then when you allocate you just allocate an item from where the end-of-used-pool-area pointer points to, and increment that pointer. That is of course if it hasn't already reached the actual end of the pool. Otherwise you allocate as per already described by EasilyConfused. Deallocation is unchanged fro mthe above.

This technique helps for when you want to empty the pool on every frame (in constant time, assuming you're items don't have destuctors), as you would if you were implementing say an S-Buffer. It also improves cache locality to throw away that potentially randomly ordered freelist when the pool is empty, and start afresh.

Thanks for all the replies. I ended up allocating a fixed size array the same size as the number of slots in the pool for memory management structure. I used relative addressing with short type in order to minimize the memory footprint. Thanks again :)