Hacker News Reader

Comment by nmilo | Hacker News Reader

The 2 stacks is really cool. Seems like it solves a lot of problems dynamic allocation + RAII solves. Is there more written about this?

View on HN

You don't need explicit language support to do this -- it's a fairly common practice in videogame development, but we usually usually call it an arena/scratch buffer. Ryan Fleury has a wonderful article where goes at length about different memory management strategies [1].

It's just a static buffer that you can use for temporary allocations, e.g. to return an array of 50 int32's to a parent stack frame you can just allocate `50*sizeof(int32)` bytes on that buffer and return a pointer to the beginning, instead of a heap-allocated `std::vector<int32>`. Every allocation advances the head of the buffer, so you can have multiple allocations alive at the same time.

Every once in a while you need to free the buffer, which just means resetting its head back to the start - in the case of games the beginning of a new frame is a convenient point to do that.

This doesn't solve dynamic memory in general, as it can't be used for long-lived allocations, it just saves you a bunch of temporary heap allocations. It doesn't solve all problems that RAII does either, as RAII is often used for resources other than memory - files, sockets, locks, ...

[1] https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...

Explicit language support is very nice as the compiler can and do a lot of optimizations and free the space as early as possible on all control paths and ensure full memory safety.

For example, when a function returns a thing on the second stack the compiler can arrange that, before returning, the thing is moved to the second stack position that was at the start of the function. This releases the memory that was used for other things by the callee. Then the caller knows the second stack depth after the call and can release its second stack usage just as well.

Doing frees/moves/copies on the second stack makes it harder to track the lifetime of allocations, and restricts what you can use it for - to free a block on the stack you necessarily have to free everything after it.

Most programs have a point where you know nothing on it is used and it's convenient (and very performant) to free the entire thing, and that makes it way easier to reason about - when you alloc from it you know your block of memory it's valid until a <RESET> point:

  - For a video game you can <RESET> at the start of every frame
  - For a web server you can alloc a new stack for every incoming request and <RESET> after the request is over
  - For a short-lived program you may not even need to <RESET> at all

The <reset> point is indeed what you need to look for but why does it need to be a stack ? I guess it's just a naming thing. I've always looked at it as a scratchpad (that was heap allocated)

You can just pop the second stack at each function return, though that does limit its use to only really scratch-space for dynamically sized objects. Like this: https://nullprogram.com/blog/2023/09/27/. “Arenas” are passed by value so their end pointer will auto reset when the function returns.

Ada has the concept of Pools, the heap is one of the pools, you can define your own.

Technically one does not need the second stack to implement this. One can use the main stack to place all dynamically sized things. The trick is then on the return copy the dynamically sized thing to insert it before the caller return address stored on the stack. The caller will see it then as if the new thing was allocated on its stack after the call.

But using the second stack is just simpler, avoids the extra copies and more compatible with the mainstream ABI.

Not really much other than tangential mentions. I did write an addendum to the OP going over the secondary stack as well as where you still use normal dynamic allocation in Ada: https://nytpu.com/gemlog/2024-12-27-2

All my knowledge on it comes from some documentation on configuring the secondary stack for embedded targets and from comments+diagrams in the GCC GNAT source code (and maybe I saw a conversation on it on the comp.lang.ada Usenet group at some point…): https://docs.adacore.com/gnat_ugx-docs/html/gnat_ugx/gnat_ug... https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/ada/libgnat/...

Forth is another language with separate control flow and data stacks, for similar reasons, although at a much lower level - the stacks are a part of the language spec that is fully exposed to you, not just an implementation detail.

Reply on news.ycombinator.com