Object pools for efficient resource management

Question

How can I avoid using default new() to create each object?

My previous demo had very unpleasant framerate hiccups during dynamic memory allocations (usually, when arrays are resized), and creating lots of small objects which often contain one pointer to some DirectX resource seems like an awful lot of waste.

I'm thinking about:

1. Creating a master look-up table to refer to objects by handles (for safety & ease of serialization), much like EntityList in source engine

2. Creating a templated object pool, which will store items contiguously (more cache-friendly, fast iteration, etc.) and the stored elements will be accessed (by external systems) via the global lookup table.

The object pool will use the swap-with-last trick for fast removal (it will invoke the object's ~destructor first) and will update the corresponding indices in the global table accordingly (when growing/shrinking/moving elements). The elements will be copied via plain memcpy().

Is it a good idea? Will it be safe to store objects of non-POD types (e.g. pointers, vtable) in such containers?

Related post: Dynamic Memory Allocation and Memory Management

Answer 1

Memory pools or object pools are a very common practice in game programming. Another common practice in console games is to allocate everything in module-specific pools to "budget" memory and have precise control over when and where allocation occurs.

Some years ago I asked advice on which strategy to go with a game I was making: https://stackoverflow.com/questions/1964722/one-big-pool-or-several-type-specific-pools

The strategy to use is mostly dependant on your game but anyway, making sure no allocation/deallocation is being done while the game is running is a golden rule of thumb. It can be broken if the game state might vary depending on external informations, like when you work on MMO games. But then, having memory pools for several categories of size of objects (instead of pool of objects) might be a good idea to keep the memory as stable as possible.

Pooling should work for any kind of object, depending on the strategy. What's important is that the full type is known by the pool to allocate enough memory, then do whatever you want with the object. The other thing to not forget is to let the pool know when the object can be released to be used later (without deallocating it's memory).

Answer 2

The elements will be copied via plain memcpy().

And... when you come to apply this to your Text objects? Never, ever, use memcpy when you can use std::copy.

Your intended goal is laudable but your implementation details seem more than a little sketchy to me. Boost comes with a pre-built pool allocator you can use which likely put a lot more thought and time into this than you did, and works for any type.

Answer 3

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, but I wouldn't call them "object pools" since that term is often reserved for use cases where objects are deliberately kept reachable to avoid GC overhead.

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.

With That Said...

With all that being said, IMO when you feel the need to reach heavily for memory pools or object pools, I consider it a sign that your design is too granular. You'll never be able to find breathing room to optimize that much if your designs are very granular.

By granular, I mean like a system where everything in the system depends on a "pixel" object instead of an "image" object, or a "particle" object instead of a "particle emitter" object, or a "dog" object instead of a "dogs" object. To find sufficient breathing room to try all kinds of optimizations like eliminating vptr and virtual dispatch overhead for a boatload of teeny objects, using SoA reps, multithreading the homogeneous processing of many teeny things at a central level without rewriting the entire system, etc., you should be designing things at a coarser level: at the level of a collection of things, or sometimes even a collection of a collection of things.

That applies even for inheritance and OOP-based polymorphism. You don't have to make a Dog inherit from a Mammal. You can have Dogs inheriting from Mammals with a Mammals interface that contains operations that apply to multiple mammals at once. You can have abstract containers, just like abstract images instead of abstract pixels, and that will leave you so much more breathing room to optimize when you have so many fewer teeny object instances to deal with, and instead a handful of "container object" type instances.

Allocating each and every dog on a heap might be expensive. Allocating a container that could store a million dogs one time on the heap is not so expensive as that overhead is now reduced to 1/1,000,000. The easiest way to reduce the expense of allocating or freeing or accessing or modifying a boatload of teeny objects is to avoid designing a boatload of teeny object types in the first place, and instead design a handful of bigger, coarser types of collection objects.

It's a similar thing for data structures. If you find you need to allocate too often with a linked structure, maybe an unrolled structure would be better, like an unrolled linked list which is not storing one element per node, but many contiguous elements per node:

This is the same idea applied as above. We're amortizing the cost of a linked list by designing a data structure that requires only paying that cost once per entire "collection" of elements, not per element. We're linking collections of elements now, not each and every element individually.

Memory allocators are kinda like reaching under the guts of your data types and structures, and it's always at least a little bit ugly and will never quite get you as far in terms of, say, minimizing memory use and maximizing processing efficiency. I'd consider designing different data types and using different data structures first whenever possible.

If you have to drive an hour just to get a cup of coffee, then the solution isn't necessarily to look for a faster car. It might be a whole lot easier if you just stock up on a month's worth of coffee instead, unless there's like a pretty girl working at the counter that you want to see each time, at which point you might look into a faster car. Design at a coarse level for bulk processing. That's the easiest way to reduce these costs paid on a per-object basis for teeny little objects.

Answer 4

I'd consider "resizing" arrays to be an emergency solution, avoid it as far as possible.

If you truly need dynamic size tables you should build them in two layers. Make a small master table that only contain pointers to fixed size sub tables of the desired table content. When the last sub table is close to full you allocate a new one. You could for instance decide to make a master table of 1024 pointer slots, and have each sub table contain 1024 objects, thus the overhead will never be more than a little over a thousand objects and 1024 pointers, yet you have got room for 1048576 objects while only needing to do simple memory allocations at runtime.