This week I’ll briefly talk about the custom memory allocators used in the 3D engine that I’m developing for Rival Fortress.

Minimizing system allocator usage

C and C++ don’t have built in garbage collection, so it’s up to the developer to decide how and when to allocate and free memory.

Relying only on the system allocator by using new or malloc for every allocation can cause performance issues, especially when trying to reduce cache misses and cache locality as allocations, even back-to-back allocations, are not guaranteed to be close in memory.

A secondary, but less common, side effect is heap fragmentation: an issue that arises when the system allocator has to periodically waste cycles defragmenting memory because many small allocations and frees have caused the heap to become fragmented.

Custom allocators

Custom allocators, on the other hand, allow for much finer grained control. They are usually built on top of the system allocator and work by allocating and partitioning larger memory blocks into smaller chunks requested by the application.

You can find out more about custom allocators in the excellent Game Engine Architecture by Jason Gregory.

I’m not a big fan of object oriented programming and many of the features C++ has to offer, so most of the allocators that I implemented for the game engine don’t use any C++ fanciness (a part from constructor/destructors used by the ScopeAllocator). You could certainly implement custom allocators by overloading the new operator and using placement new to partition out memory and sprinkling in some templating magic, but that’s not my cup of tea.

Allocators used in Rival Fortress

For Rival Fortress, I allocate a large chunk of memory on start up and partition it to the various subsystems using the following allocators:

• PushAllocator: A simple stack based allocator that, given a block of memory, partitions it out by incrementing a location in a similar manner to how the stack pointer works.
• SlidingAllocator: Works on top of a stack allocator and grows until the parent allocator has memory. The characteristic of this allocator is that it can rewind all allocations in order to reset the allocated memory. This is useful as a “one-frame-only” allocator for temporary operations that get wiped at the end of the frame.
• FreeableAllocator: This is one of the few allocators that can reclaim memory and repartition it. It has the capability of merging contiguous free blocks and reallocate existing pointers.
• ScopeAllocator: A temporary allocator that discards any allocations and rewinds the end of the scope.
• ArrayAllocator: Used for growing lists of lists.
• DoubleEndStackAllocator: Similar to the stack allocator, but can grow from both the head or the tail of the memory block.
• ObjectPool: A simple bounded pool of struct that can get recycled by last usage time. This is used in the engine to retire old rendering “chunks” and replace them with new ones without needing to allocate.
• StringPool: A string interner used for all strings used by the game and engine that allows fast lookups through hashes and string recycling.