"Zero-overhead" objects pool

Posted on
programming

Sometimes I just feel stupid. For the longest time, whenever I implemented an object pool, I always had some kind of variable length array to store my list of free objects in additional to the backing memory of the objects. This meant that I had additional memory allocations to store and potentially resize this list.

struct Pool
{
    Type            *   backing_memory;
    DynArray<Type *>    free_objects;
    // Some more housekeeping stuff
};

Today I just realized that, as long as the objects are larger than the size of a pointer (which is pretty much always the case), you can just store the pointer to the next free object in it and essentially build a linked list. That way you don’t have to allocate additional memory for the free list. Here is a pseudo implementation ignoring the cases where we run out of free objects:

struct Pool
{
    Type            *   backing_memory;
    void            **  next_free_object;
    // Some more housekeeping stuff
};

Type * Pool::alloc()
{
    Type * allocated = (Type *)next_free_object;
    next_free_object = (void**)*next_free_object;
    return allocated;
}

void Pool::release(Type * released)
{
    void ** released_ptr = (void **)released;
    *released_ptr = (void *)next_free_object;
    next_free_object = released_ptr;
}