The Double Headed Stack Allocator

The Double Headed Stack Allocator is a memory management technique used to efficiently allocate and deallocate memory in high-performance applications, such as video games. It is a variation of the traditional stack allocator, also known as a bump allocator.

In a typical stack allocator, memory is allocated from the top of a stack, and deallocation is simply a matter of resetting an integer variable. The Double Headed Stack Allocator takes this concept a step further by using two separate stacks for different types of memory. One stack grows upwards from zero for level data, while the other grows downwards from the end of the memory for character data.

This design helps prevent memory fragmentation, which can occur when memory is allocated and deallocated in a non-sequential manner, as in the case of a streaming world game with a player character that changes forms. By using separate stacks for level and character data, the allocator can reset the level stack to zero when the level data is deallocated, and reallocate memory without causing fragmentation.

The Double Headed Stack Allocator is particularly useful in multi-threaded environments, as the top-of-stack integer can be protected with atomic operations to allow multiple threads to allocate memory from the same stack. It is also applicable to simpler types of memory, as the allocator does not call destructors during deallocation. This makes it an ideal solution for memory-intensive applications like video games.