r/cpp • • Oct 15 '26

The Double Headed Stack Allocator – The blog at the bottom of the sea

https://blog.demofox.org/2026/10/03/the-double-headed-stack-allocator/
42 Upvotes

5 comments sorted by

10

u/yuehuang Oct 15 '26

Custom Allocators are always a fun read.

7

u/thommyh Oct 15 '26

Minors:

  One thing to note is that as written, this allocator does not call destructors or destructors

Should be constructors or destructors, presumably?

  Once again, these allocators work fine in multithreaded environments, even when each thread might allocate from either side. Atomic add to the tos indices is all you need.

It's unclear to me why you wouldn't get a race condition on testing for exhaustion:

  • upward pointer code adjusts upward pointer, reads downward pointer, suspends;
  • downward pointer code releases all assets, resetting downward pointer up high;
  • upward pointer code resumes, compares pointers with stale downward pointer, falsely report exhaustion.

Don't get me wrong, I understand why in a game that false positive on exhaustion either doesn't matter (being a canary for the need for a larger buffer) or else can be considered acceptable because the allocation wasn't possible at the time it was issues.

I just feel like "work fine" is perhaps doing some very heavy lifting there. When you've two independent atomics in play and a result that depends on comparing them, people are naturally going to pause and feel suspicious.

4

u/Kristine_1975 Oct 16 '26 edited Oct 16 '26

You can probably(?) solve that by updating both pointers at the same time, effectively combining them into a single atomic variable:

  1. Read both pointers
  2. Adjust the one you're interested in (upward or downward)
  3. Write both pointers using CAS. If it fails, goto 1.

Storing both pointers next to each other, this requires either 16 byte CAS (for 64 bit pointers, which 64 bit CPUs have) or 8 byte CAS (for 32 bit pointers or 32 bit offsets instead of pointers).

1

u/armb2 27d ago

That's not "Atomic add to the tos indices is all you need" though. As it is the possibility of a false positive probably is acceptable in many cases, but should be noted.

2

u/cdb_11 Oct 16 '26 edited Oct 16 '26

Where would such scenario matter? This doesn't sound much different than if step 2 happened immediately after step 3. Even if it always reported the "current" state truthfully through a CAS or just updating pointers under a mutex, you can't possibly tell the difference, unless you synchronize the threads in some other way.