undefined | Better HN

0 pointsduped1y ago0 comments

A fixed capacity stack isn't growable, and while the capacity is pretty big by default on desktop/server OSes is pretty big, so are stack frames so the recursion depth limit is not that big. And if user input can overflow the stack it's still a DOS.

The problem to me is that recursive functions should be a special case in the ABI, where a compiler can insert a prelude to the callsite to grow/segment the stack if needed. This is a hard problem once you have references to things on the stack, so I can understand why most ecosystems don't do it - but that doesn't mean it can't be done.

What I'm saying is that stack allocation is still dynamic memory management and in systems where its critical to avoid OOM conditions because of unbounded dynamic memory management you need code with O(1) memory complexity, and that includes the stack. A common mistake I've seen people make is assume that pushing onto the stack isn't memory allocation. It's just cheap memory allocation that can sometimes be assumed to be free, in this case and many others that's a bad assumption.

0 comments

ajross1y ago

Fair enough, but that's getting pretty far into "research language runtimes" and not practical solutions. The tricks most people play when faced with these problems are (1) let the OS protection do it job or (2) just disallow recursion if you really can't manage that.

There's no realistic technology stack out there that does what you want.

dupedOP1y ago

Go does this, as do most runtimes with stackful coroutines. Async Rust (kinda) does this where the async call stack is naturally segmented (although this doesn't get away from stack overflows in some cases because the polling call stack is not growable).

Growable stacks have been around for decades, it's far away from research language territory.

The real benefit is not to handle the worst case/OOM condition that a big enough callstack gives you. It's to make the default stack size much, much smaller for the common case where you don't need it at all (or want to shrink it later). Growable stacks use less memory on average than your typical embedded device because they can start in the dozens of bytes, instead of requiring kilo/mega bytes of stack space (allocated, not just reserved). It's kinda the only way you can make a runtime scale to millions of concurrent call stacks.

steveklabnik1y ago

Both Go and Rust removed segmented stacks, for the same reasons: they can really kill performance.

Go now copies stacks, and Rust only has segments if you deliberately box up a recursive call.

1 more reply

j / k navigate · click thread line to collapse