Double-headed stack allocators explained: fast, fragmentation-free memory from game dev

A stack allocator in one integer

A post on demofox.org, which reached the Hacker News front page on October 3, walks through stack allocators and their double-headed variant — a memory technique from shipped games that reduces allocation to an integer add and sidesteps fragmentation between two systems that recycle memory on independent schedules.

The author anchors the technique in real projects. Around 2010, while doing animation programming at Surreal Software (Midway Seattle) on the open-world title This is Vegas — a game cancelled when Midway went out of business — they faced a hot spot in the profiler. Animation ran as state machines driving sets of bones, with each state represented by a tree of blended animations and cross-fades between states to preserve continuity. Which characters got animated could change drastically frame to frame, depending on what fell inside the camera frustum, so the blending code performed large numbers of dynamic allocations every single frame, all of them transient.

The fix was a stack allocator, also called a bump allocator — not to be confused with alloca, which draws from the actual program stack. You reserve one block sized for the worst case, say 1MB, and track a single integer: the top of the stack. Allocating means returning the memory at the current top and adding the requested byte count to that integer. Freeing everything means a single assignment that resets the counter to zero. According to the post, allocation disappeared from the profiler after the change; the counter was reset each frame once blend results had been copied into the buffers bound for the vertex shader for skinning.

A real implementation also needs the block size so it can detect the counter running past the end, whether by returning null or asserting. The post flags the main limitation: nothing is destructed automatically. Placement new can run constructors cheaply, but destructors would have to be invoked manually, which is error prone, so these allocators suit simpler types. Two further properties stand out: if the counter uses an atomic add, multiple threads can allocate from the same allocator, useful for fork/join workloads on the CPU or complex algorithms on the GPU; and partial deallocation is possible by recording the counter at, say, the start of each recursion level and restoring it when that level finishes.

The fragmentation problem

The post's second half comes from the author's time at Blizzard on the StarCraft 2 team, where their manager James Anhalt described the double-headed form as a fix for fragmentation. The motivating scenario: a streaming world game where old level geometry is deallocated and new geometry streams in from disk as the player moves, while a shape-shifting character similarly deallocates and reloads data on form changes.

The failure mode is straightforward. With 100MB shared between level data and character data, allocations interleave: the level takes 20MB, the character takes 30MB, the level takes another 20MB, the character takes the final 30MB. Free the level's 40MB and you have 40MB available — but split into two 20MB holes, so a new 30MB level allocation fails despite sufficient total free memory.

Two stacks in one block

The double-headed design puts both systems in a single memory region. Level data keeps a top-of-stack growing upward from zero; character data keeps one growing downward from the end of memory. You are out of memory precisely when the two counters cross. When either system finishes, it resets its own counter back to its origin — zero for the level, the end of memory for the character — and reallocates from a contiguous region, untouched by the other side's allocations. No fragmentation.

The approach stays multithread-friendly: atomic adds on each counter are all that is needed, even if a given thread allocates from either side. The post also addresses the obvious question of why not simply use two separate stack allocators: the benefit appears when memory is constrained and one block can serve both systems while the split between them stays flexible — some levels may need more memory, with the character getting by on less.

The post closes with a related variation for storing a variable number of variable-sized objects in a fixed region with random access by index — for example, packing network commands into fixed-size packets — though the syndicated excerpt cuts off before those details.

Why it matters

General-purpose allocators carry real costs in bookkeeping and, over time, fragmentation. For resource-constrained and real-time software, the double-headed stack allocator is a compact answer to both: allocation becomes arithmetic, whole-system frees become one assignment, and two components with different lifetimes can share a single budget without carving it into unusably small holes. The idea requires no dependencies beyond an integer and a byte range, extends naturally to multithreading, and applies well beyond games — per-frame or per-request transient work in servers, parsing buffers, and GPU command generation are all natural fits.