Return to Revisions

For C++ an "object pool" makes little sense, since you have the ability to construct and destroy objects without allocating and freeing memory with placement new and manual invocations of a dtor. "Memory pools" make more sense *.

• Note that I distinguish "object pool" from certain types of "resource pools" like thread pools. Thread pools aren't intended to save the cost of allocating and destroying a thread handle's memory. They pool threads in order to avoid the operating-system level cost of repeatedly creating and destroying threads. Those types of resource pools make sense in any language.

Here your best bet is probably a simple free list for each type of object you allocate if you genuinely have heap allocation/deallocation-related hotspots (along with some additional page faults and cache misses). A free list exploits the fact that all the memory it pools is going to be pooled in the same-sized chunks which is going to be sufficient if you use a separate free list for each object type or subtype you'll be allocating and freeing. It's not a variable-sized allocator. It returns a fixed-size amount of memory for the client to use each time.

Here's a basic free list to get you started. I didn't bother to make it thread-safe and generally you'd probably want to use these locally for a given thread anyway if you're suffering allocation/freeing-related bottlenecks since this implementation, at least on my machine, is about 20 times faster than malloc/free but it slows down to being only twice as fast as malloc/free the moment you involve a completely uncontended spin lock. I also didn't bother with exception-safety if new fails in the code below, though I don't think it's worth bothering in a game context (but you can if you want with a little more work or if you don't mind paying for the overhead of using std::vector and std::list which require a little more memory for size and capacity and so forth in exchange for proper reversal of side effects on std::bad_alloc).

#ifndef FIXED_ALLOCATOR_HPP
#define FIXED_ALLOCATOR_HPP

class FixedAllocator
{
public:
    /// Creates a fixed allocator with the specified type and block size.
    explicit FixedAllocator(int type_size, int block_size = 2048);

    /// Destroys the allocator.
    ~FixedAllocator();

    /// @return A pointer to a newly allocated chunk.
    void* allocate();

    /// Frees the specified chunk.
    void deallocate(void* mem);

private:
    struct Block;
    struct FreeElement;

    FreeElement* free_element;
    Block* head;
    int type_size;
    int num_block_elements;
};

#endif

#include "FixedAllocator.hpp"
#include <cstdlib>

struct FixedAllocator::FreeElement
{
    // Allocated chunks serve as a singly-linked list node when free,
    // client data when used.
    FreeElement* next_element;
};

struct FixedAllocator::Block
{
    // Blocks are linked together as singly-linked lists, pooling contiguous
    // blocks of memory.
    Block* next;
    char* mem;
};

FixedAllocator::FixedAllocator(int itype_size, int block_size): free_element(0), head(0)
{
    // Initialize the free list.
    type_size = itype_size > sizeof(FreeElement) ? itype_size: sizeof(FreeElement);
    num_block_elements = block_size / type_size;
    if (num_block_elements == 0)
        num_block_elements = 1;
}

FixedAllocator::~FixedAllocator()
{
    // Free each block in the list, popping a block until the stack is empty.
    while (head)
    {
        Block* block = head;
        head = head->next;
        delete[] block->mem;
        delete block;
    }
    free_element = 0;
}

void* FixedAllocator::allocate()
{
    // Common case: just pop free element and return.
    if (free_element)
    {
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case when we're out of free elements.
    // Create new block.
    Block* new_block = new Block;
    new_block->mem = new char[type_size * num_block_elements];
    new_block->next = head;
    head = new_block;

    // Push all but one of the new block's elements to the free stack.
    char* mem = new_block->mem;
    for (int j=1; j < num_block_elements; ++j)
    {
        void* ptr = mem + j*type_size;
        FreeElement* element = static_cast<FreeElement*>(ptr);
        element->next_element = free_element;
        free_element = element;
    }
    return mem;
}

void FixedAllocator::deallocate(void* mem)
{
    // Just push a free element to the stack.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

As for your idea:

The object pool will use the swap-with-last trick for fast removal (it will invoke the object's ~destructor first)

If you use swap-with-last then you'll end up invalidating pointers to the last object (as well as any indices to it). For a memory allocator, it's similar to creating a data structure except you deal with a very firm requirement that you cannot invalidate pointers to memory that is not freed no matter what. With a free list like the above, you don't have to do that while keeping dirt cheap constant-time allocation and freeing.

Also the free list will give you nice spatial locality for memory chunks you allocate against it if you access the pointers in a sorted sequential fashion. However, if you start freeing and allocating a lot against it and the pointers becoming unsorted, then you could end up with lots of cache misses zig-zagging back and forth in memory. It helps to sort those pointers you get from the allocator periodically if you suffer cache misses (a radix sort can do that really fast). The free list, when combined with sorted pointers, does give you very cache-friendly access patterns, but you do have to keep those pointer reasonably sorted by address.