The Double Headed Stack Allocator

tyushk

The single stack allocator seems to be an arena by other terms, but the double headed version is pretty neat. Is the final pattern described actually safe for multi-threaded use? Something like the stack has exactly 1 byte left, T1 allocates the dynamic end with 1 byte (dynamic object just happened to be 1 byte, say) and T2 allocates the fixed size end with 1 byte. Wouldn't they end up overlapping in that case?

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.

monocasa

This is pretty much the old school single threaded unix process model, where the heap grows up from the end of bss and the stack grows down from the top of the process.

HexDecOctBin

> You might ask “why not have two stack allocators instead of a double headed one?” The main benefit is when you are memory constrained and know that the size of one stack allocator is enough to serve two systems, but the proportion of memory that goes to one side vs the other is flexible. This doesn't make a lot of sense. Solving `x <= X, y <= Y` is much easier than solving `x + y <= Z`. If you put a limit on both the size of in-core level data (perhaps using a Cell based system) and on character data in the asset pipeline itself, that is much better than to ensure that all the various combinations of level sizes and character sizes are compatible and won't end up trampling over each other.

Woodi

One thing to mention is that stack structure or multiple stacks on the heap are very fast garbage collection, much faster than any search-mark-sweap can be. Also worth to mention that in stack fast "deallocation" memory (usually) is not zeroed or cleared so it is very internal architecture...

Panzerschrek

> Once again, these allocators work fine in multithreaded environments How? As I understand, for such double-headed allocator to be multithreaded one needs to update two counters atomically, which is tricky.

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.