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::list which require a little more memory for size and capacity and so forth in exchange for proper reversal of side effects on
/// Creates a fixed allocator with the specified type and block size.
explicit FixedAllocator(int type_size, int block_size = 2048);
/// Destroys the allocator.
/// @return A pointer to a newly allocated chunk.
/// Frees the specified chunk.
void deallocate(void* mem);
// Allocated chunks serve as a singly-linked list node when free,
// client data when used.
// Blocks are linked together as singly-linked lists, pooling contiguous
// blocks of memory.
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;
// Free each block in the list, popping a block until the stack is empty.
Block* block = head;
head = head->next;
free_element = 0;
// Common case: just pop free element and return.
void* mem = free_element;
free_element = free_element->next_element;
// 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;
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.