The Double Headed Stack Allocator

Panzerschrek an hour ago | parent | next [-]

> 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.

▲

HexDecOctBin an hour ago | parent | prev | next [-]

> 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.

▲

saagarjha 3 hours ago | parent | prev | next [-]

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 3 hours ago | parent | prev | next [-]

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.

▲

Woodi an hour ago | parent | prev | next [-]

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...

▲

tyushk 3 hours ago | parent | prev | next [-]

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?

▲

singron 2 hours ago | parent | next [-]

I think it's OK to increment/decrement the ends past each other as long as you detect that and fail the allocation for at least one end.

It's a little tricky with memory orders since you are synchronizing on two different locations. The simplest thing is to make all atomic accesses seqcst, but I think a single fence(seqcst) before checking overlap is sufficient in this case and will use fewer synchronizing instructions.

The overflow checks are also tricky. We want to make sure that if an allocation fails, subsequent allocations also fail (even on other threads), and overflow might allow them to think they succeeded by incrementing again back into a valid range. This means you generally can't use fetch_add in a thread-safe bump allocator and instead need to use a CAS loop where you detect overflow before writing.

Since you are doing a CAS loop anyway and always accessing both variables, it might actually be faster to combine both variables, especially if you typically allocate from both at the same time. E.g. if you pack two offsets into a 64-bit CAS word, you can still address 4GB, and you can get even more by aligning allocations. You also don't have to worry about seqcst.

	▲	moring 4 minutes ago \| parent [-]
		The full quote from the article is: > Just like the other stack allocators we talked about, this one can also work in a multi threaded environment. You might be tempted to make the two updates transactional – like with a compare and swap loop – but it isn’t needed. Unfortunately they don't explain HOW this is going to work...

▲

hnav 3 hours ago | parent | prev | next [-]

It could be if you packed both tos variables into a single atomic and the compare and swapped the combined value.

▲

saagarjha 3 hours ago | parent | prev [-]

You’d need synchronization in the allocator but typically this is pretty cheap (often these allocations come from one thread and may get handed out to multiple consumers who work on them in parallel).

▲

Panzerschrek an hour ago | parent | prev [-]

> 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.