Are there any good custom allocators for C++ that maximize locality of reference?

Question

I am running a simulation with a lot if bunch of initial memory allocations per object. The simulation has to run as quickly as possible, but the speed of allocation is not important. I am not concerned with deallocation.

Ideally, the allocator will place everything in a contiguous block of memory. (I think this is sometimes called an arena?)

I am not able to use a flattened vector because the allocated objects are polymorphic.

What are my options?

Answer 1

Just make your own.

See an old question of mine to see how you can start:

Improvements for this C++ stack allocator?

Answer 2

Since you don't care about de-allocation you can use a linear allocator. Allocate a huge amount of memory up front and store a pointer to the start. malloc(x) moves the allocation pointer forward by x bytes and returns the old value of the pointer, delete(x) is stubbed out. As mentioned here, another poster already has an implimentation

Allocations are packed as closely as possible, allocations are incredibly fast and memory is returned in the order allocated. When your simulation is done, you just reset the allocator's pointer to the start of memory and clear any pointers you have from outside the allocator to objects inside of it.

Pool allocators are a great choice if you want to delete objects, faster than a heap but won't pack your data into memory as close and aren't quite as fast. Use boost:pool for those. This is a great choice for games if you have x bytes to store say - a level - and you are willing to throw the whole lot away at the same time.

As an aside, if you are interested in memory performance, see What Every Programmer Should Know About Memory-PDF. It covers things like locality of reference and its effect on performance. Specifically, you might want to create a pool for each type of object that is used together, or declare your objects as a struct of arrays rather than a array of structs