The Double-Headed Stack Allocator That Killed Memory Fragmentation
The Double Headed Stack Allocator
At Blizzard, James Anhalt introduced me to the double-headed stack allocator: two bump allocators growing toward each other from opposite ends of a single memory block. One side handles level geometry, the other character data, each resetting its own top-of-stack without leaving holes. When the two pointers cross, memory is exhausted. The technique eliminates fragmentation, works with atomic adds in multithreaded code, and can also store variable-sized objects with an offset table for random access.
This made it so when the level data needed to change, it could reset the level tos back to 0, and reallocate the memory it needed, without any fragmentation whatsoever.
- tom_
This works well with an ordinary allocator too. At a previous place i worked, we had an allocate high option for the ordinary memory manager, that would find the highest possible address rather than the lowest. Pretty good for situations where you needed to allocate some transient data while creating some persistent data, without introducing unnecessary fragmentation.
- Panzerschrek
> Imagine that you had a streaming world game where as the player ran around the world, old level geometry would deallocate, and new level geometry would allocate and stream in from disk.
In such case stack-like allocator isn't the best strategy. One can use some sort of cyclic allocator instead. As I know Quake did this for surfaces cache.
- kevin_thibedeau
Bipartite buffers are better for storing a sequence of variable sized objects. It works like a circular buffer and you don't get stuck with bump allocator memory exhaustion. This requires sequential iteration but you rarely need random access for such things.
- windenntw
And that's why AmigaOS allowed a MEMF_REVERSE option in the call to the memory allocator ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... )
Sometime in 95 or 96 recall making a very very simple OS patch that would force all allocations > X size ( 1KB or something like that ) to use MEMF_REVERSE and that made wonders to reduce memory fragmentation :)
- saagarjha
This kind of pattern is pretty common when dealing with pipelining of some kind. Another solution I’ve implemented before when dealing with streaming weights into a GPU is that you mirror map the region twice and hand out pointers in order from the first region but allowing it to wrap around to the front using virtual addressing. I’ve found this to be slightly more powerful as it allows for allocating multiple stages ahead, since you don’t run out of “sides” to allocate from. The double sided allocator unfortunately only really allows for 1 extra stage for your pipeline.