The Double Headed Stack Allocator | Hacker News Reader

The Double Headed Stack Allocator

blog.demofox.org

95 pointsg0xA52A2A36 comments

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

Interestingly, Quake 3 did use a double sided stack allocator as the article describes. The engine made one big allocation at startup called the "hunk." The "low hunk" allocated long-lived data and the "high hunk" temporary data. Search for "hunk" in this source file to see the implementation [1].

[1] https://github.com/id-Software/Quake-III-Arena/blob/master/c...

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.

The so-called "magic ring buffer": https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

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 :)

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.

Why not a seperate stack allocator for each type of object? Here you use two object types so you can use a double-headed stack allocator, but what if you have three type of objects?

The system in TFA can only handle 2 "categories". Note that there could be many distinct types in each category; the important thing about categories is that everything in the same category should share an allocation/deallocation timeline. If this holds separately for each category, there will be no fragmentation.

For this 2-category case, the double-headed stack is strictly better than maintaining 2 separate half-size stacks, since it permits every sequence of allocations and deallocations that the latter permits, while there are sequences that it permits that the latter does not permit (namely, any sequence in which more than half the memory is temporarily needed by one of the categories, and the other category is temporarily not using it).

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?

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

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

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.

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

I'd argue that incremental GC isn't actually that bad. The lifetime of an object can be more confounding that it might seem at first glance. It is really easy for a game design decision to alter these lifetimes arbitrarily. Even if you know something is going to live for one frame only, it's not like you are surrendering the entire kingdom if you fail to exploit the optimization opportunity.

There are a lot of other problems to worry about in game dev. Manual memory management is a luxury mostly exclusive to larger studios. Solo developers won't make to the actual runway if they try to fight these kinds of technical battles on principled terms. You often need a lot of samples (paying customers / large QA team) to prove these custom schemes are viable. For better or worse, the cranky old GC might be the lowest risk option. A few late frames is a hell of a lot less disruptive to the gamer than a crash.

It depends a lot on the person I guess. But I'd gladly trade, let's say hourly crashes, for great frametimes.

GC generally only results in the occasional missed frame, it doesn't negatively impact overall frametimes in a meaningful way if it's implemented correctly. GC malloc() and free() are both fast.

I think the average player would not appreciate hourly crashes, especially in games without aggressive autosave - that potentially means having to replay 10+ minutes worth of gameplay on a regular basis because your timing was bad, when you consider how a typical game is built. You could compensate for this in some game types I guess, like in a competitive FPS you'd restart the client software between matches and hope a match never lasts long enough to crash. But that's no substitute for real robustness, IMO.

Inconsistent frame times tend to feel worse than just lower frametimes, on the whole. There's a reason a lot of benchmarking has started highlighting the 1% lows.

I certainly would not appreciate hourly crashes, don't get me wrong. But inconstant frame pacing makes me queasy. It's not low frametimes that is the issue, it's the inconsistency.

Hitches are much less an issue with modern GC.

The real drawback to GC is the inability to estimate your peak memory consumption

Many usecases cannot afford allocations that move

You're probably right, in practice it would be just fine.

That said if you look at a lot of the basic GC approaches you end up either moving all the allocated and live objects, or running through a mark & sweep dance which gives you holes in your allocation region - and causes problems with fragmentation.

Choosing the right kind of GC, knowing your constraints, could probably sidestep these problems, but there seems to be nothing obvious with the simple two-headed bump-allocator decribed in the post, so long as the lifecycles don't change over time - ruining the simplicity of the arena-based approach.

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

The idea here is that x <= X, y <= Y, but x' + y' <= Z where x' and y' may be (individually) greater than x or y

Dynamic stacks with linked granular chunks? It consumes even less memory.

Not contiguous

Obviously chunk size is larger than class of objects to allocate.

This is not always possible

Then fixed stack also is not possible for such cases.

Sure it is? Stacks are contiguous

If you can't limit stuck chunks you can't limit fixed stack. And vice versa. It's quite simple.

Sure, but how do you prove that you won't end up with `x' + y' > Z` for some value of x' and y'? In practice, it's always easier to prove `x < X, y < Y`.

Generally the idea is that all of these are (more or less) easy to prove but the other policy allows for x' and y' to be independent

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.

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

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.

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

Reply on news.ycombinator.com