The Absurdity Of Stacks

https://www.tfeb.org/fragments/2023/03/25/the-absurdity-of-stacks/

by optimalsolver • 3 years ago

54 71 3 years ago

jimbo_joe• 3 years ago

Stack is usually faster to use since it's always sequential in nature which is related to why it's considered finite while heap can theoretically take all of OS' available memory. This way the user doesn't have to consider maximum stack depth prior to running the app

quotemstr5• 3 years ago

Stack is usually faster to use since it's always sequential in nature

You can use an arena allocator to get linear allocation on the heap too. Arena allocation is underused IMHO.

Olreich3• 3 years ago

The reasons I avoid recursion don’t align with saving memory. I avoid recursion primarily to make it easier to read the code. Recursion requires you to keep track of the implicit stack, an explicit stack makes that easier for me.

Secondarily, I don’t want to deal the administrative work the author says I should do in a recursive situation, as allocating the stack size would happen far away from my algorithm, making it another thing to go hunt down when my memory usage grows, instead of a local memory allocation.

And thirdly, there can be a cost to calling functions that has been significant for me. I have a much better feel for how a loop will perform than a recursive call tree. Maybe the optimizer will do something with it, maybe it won’t. Maybe I’ll make a minor change and the optimizer will stop working and I’m getting a tenth the speed I should.

I will prototype algorithms recursively sometimes, but usually it’s very simple to convert them back into a loop with explicit stack, and many times that stack isn’t even needed. So I hardly leave it in.

zelphirkalt3• 3 years ago

The reasons I avoid recursion don’t align with saving memory. I avoid recursion primarily to make it easier to read the code. Recursion requires you to keep track of the implicit stack, an explicit stack makes that easier for me.

If you read for example "The Little Schemer", it will teach you to think about recursion in a way, that you do not actually keep track of the stack in your mind implicitly. To not think this way is actually key to understand some recursive programs. I think this has also been in one of the SICP lectures or talked about by one of the authors.

Secondarily, I don’t want to deal the administrative work the author says I should do in a recursive situation, as allocating the stack size would happen far away from my algorithm, making it another thing to go hunt down when my memory usage grows, instead of a local memory allocation.

This is a language specific concern. Look for example at the Racket docs: https://docs.racket-lang.org/guide/Lists__Iteration__and_Rec...:

At the same time, recursion does not lead to particularly bad performance in Racket, and there is no such thing as stack overflow; you can run out of memory if a computation involves too much context, but exhausting memory typically requires orders of magnitude deeper recursion than would trigger a stack overflow in other languages. These considerations, combined with the fact that tail-recursive programs automatically run the same as a loop, lead Racket programmers to embrace recursive forms rather than avoid them.

And about:

And thirdly, there can be a cost to calling functions that has been significant for me.

This is a compiler specific thing. A good compiler can turn a tail-recursive function to run the same as a loop, no additional cost for any function calls (also see the quoted Racket docs).

I will prototype algorithms recursively sometimes, but usually it’s very simple to convert them back into a loop with explicit stack, and many times that stack isn’t even needed. So I hardly leave it in.

Yes. It is mostly a simple conversion from a recursive definition to a loop definition. However, you would be surprised how many programmers do not know how to do this or have never done this, because languages they learned have merely taught them to fear recursion and so they never really wrote recursive functions much.

macintux• 3 years ago

I was on the fence wrt recursion until I met Erlang, which is recursion all the way down. The language you use makes a world of difference.

arp2422• 3 years ago

I read The Little Schemer, twice! It's a wonderful fun book that I recommend to anyone.

When I'm going through the book and playing around with Scheme I "get" recursion. Then I put the book down and go back to "real" programming and somehow this just gets lost.

Maybe it's just a matter of more practice, but it's never come naturally to me.

Dijkstra famously wrote that "it is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."

I started with BASIC. Maybe Dijkstra was right.

sanderjd2• 3 years ago

I'm very glad to have gone through the functional programming canon, it has certainly impacted my thinking on things for my whole career, but I still prefer it be explicit if I'm relying on a stack.

quotemstr5• 3 years ago

there can be a cost to calling functions that has been significant for me

Have you measured? Function call overhead is one of those things people usually feel is expensive, but in 99.9% of cases, isn't, especially when adjusting for whether optimizations from avoiding calls come from inlining instead of avoiding the actual call instructions, and especially when the function call is direct, not through a table/PLT/etc.. Worrying about function calls is up there with juggling thread priorities and replacing multiplies with shifts in the ranks of performance superstition and woo.

Olreich3• 3 years ago

I’ve hit the cliff once. That’s why it’s last on the list. It’s not very often, but it is possible to hit and with the other reasons and the ease of avoiding it make it easy to justify the very small (if any) amount of work to avoid recursion most of the time.

sanderjd2• 3 years ago

Yep, explicit vs. implicit stack is exactly my reasoning too. It's easier to instrument an explicit stack too, eg. writing a metric for max depth.

zelphirkalt3• 3 years ago

Deforming programs so they are ‘iterative’ in order that they do not run out of the stack we imagine to be so costly is ridiculous: if you have a program which is inherently recursive, let it be recursive.

Yes! Unless of course your language (or compiler, or interpreter of it) has disabilities and it is realistic, that you run into issues with recursion. Oh well ... sigh

[...] The ‘iterative’ versions just use an explicitly-maintained stack rather than the implicit stack provided by the language. That makes sense only if stack space is very small compared to the heap and must therefore be conserved. And, well, for many systems that’s true. But it is small only because we have administratively decided it should be small: the stack is just memory. If there is plenty of memory for the heap, there is plenty for the stack.

c00lio2• 3 years ago

Stack-Heap-Collisions are a thing. Many language runtimes do not check for stack collisions and break in interesting ways if one lets a recursion run too deep. Heap size and running out of heap is far easier to handle gracefully. And all of this isn't ancient history, it is still a problem nowadays, so advice like in the original article can be dangerous...

richardwhiuk2• 3 years ago

Don't stack heap collisions get caught by guard pages with native stacks? Surely green thread stacks are checked by the runtime?

c00lio2• 3 years ago

Sometimes. Guard pages are not always used, depending on your OS or C compiler for example, and on how large your address space might be. Especially 32bit applications are quite limited in that regard. Embedded always lags behind a few decades. Commercial applications are often used long beyond their due-by-date, and vendors never seem to care about that stuff anyways.

If there is only one or a few guard pages, you can sometimes still get your exploit to work by "jumping over" the guard page with a sufficiently large stack allocation that isn't used. But that is admittedly rare.

addaon6• 3 years ago

Guard pages catch /some/ stack overflows / heap collisions, but not all. In particular, anything equivalent to an alloca() of more than a few pages, followed by an access to the lowest-address element of the allocated range, can skip the guard pages undetectably.

The additional tool need is stack probes, which modify every allocation of a stack frame that may go past the guard pages (large function frames, alloca, etc) to also include a probe loop that reads from each page, guaranteeing a page fault on a guard page. The catch here is that stack allocations go from O(1) to O(size) time.

tlarkworthy• 3 years ago

V8 JS and Python (JVM too?) don't do tail call optimization, so the advice of not using the stack for high recursive algorithm is actually the right choice in the majority?

lightbendover• 3 years ago

Tail call optimization is “supported” by the JVM and is of course language dependent as it is performed at compile time. For instance, Scalia does support it. Would be great if the JVM itself supported it so it wasn’t dependent on compilers and I believe there is a proposal floating around for that.

laserbeam• 3 years ago

There are, or may be, arguments for why stacks needed to be small on ancient machines. The history is fascinating, but it is not relevant to today’s systems, other than tiny embedded ones.

If a stack doesn't very comfortably fit in L1 cache, then I'd wager you're paying a high price for it regardless of how new the system is.

DarkNova6• 3 years ago

Very often people regard the stack as a scarce, expensive resource, while the heap is plentiful and very cheap

Wait what, who says that? This has not been true for at least 10 years.

The Heap is great and extremely powerful, but with cache-misses becoming an ever larger issue, the locality of data in the Stack is a massive performance advantage.

One good example for this is Rust. Rust is fast and works almost exclusively via the Stack and copying data between contexts.

jmillikin• 3 years ago

The default stack size in most OSes is tiny, and when programming in a low-level language (including Rust) it's important to keep large allocations off of the stack. That's why Rust has Box/Vec and the various APIs in `alloc`, and why the cross-thread primitives take ownership of their values.

You can "transfer" a 1 GiB `Vec` between threads without having to actually copy it, which is not true of stack-allocated values.

The relative scarcity/cost of the stack vs heap only gets more extreme as the machines get bigger. My desktop has 128 GiB of RAM, and `ulimit -s` reports a default thread size of 8 MiB. A typical rack-mounted server is going to have 1 TiB or more of RAM, and almost certainly the same stack size.

Could I make the stack size bigger on my machine? Sure, yes, but what would that get me when the entire world writes software with the assumption that any allocation over a few dozen MiB needs to be on the heap?

zokier3• 3 years ago

Rust stacks are only 2MB by default. That is some 4-5 orders of magnitude less than typically available heap.

WJW• 3 years ago

if such a program is, in fact, iterative, then good compilers will eliminate the tail calls and it will not use stack

Well, there we go then. JS does not eliminate tail calls at all in the major browsers or in Node.js. Neither do Python, Ruby, Rust, Golang and many others.

zokier3• 3 years ago

The fact that two major attempts to do split/segmented stacks, Go and Rust, both ended up abandoning that approach to me indicates that there are fairly big problems trying to go beyond traditional stack model. Without even acknowledging the difficulty, nevermind proposing solutions, the blog post reads very much like "I want a pony"

quotemstr5• 3 years ago

Or the blog author wants something that isn't Unix. Part of the problem is that dealing with stack overflow on your typical POSIX system is practically impossible: the compilers don't do stack probing consistently, and even if they did, it'd be difficult to do anything in response to failed probes because the design of the signal handler installation mechanisms makes it hard for components within a process to share an exception like SIGSEGV. It's one of those situations in which nobody uses the feature because it's broken, and it stays broken because nobody uses the feature. Sad.

I've been trying to get this fixed for years: https://sourceware.org/legacy-ml/libc-alpha/2018-03/msg00214...

Windows has recover from stack overflow just fine with SEH. If we limited the maximum per frame stack size and probed properly, we could do split stacks no problem. We just choose not to solve this problem, like we've chosen not to solve many other problems in Unix, and things are in practice going to stay broken until the heat death of the universe or AGI just writes a PaperclipOS for itself.

mananaysiempre• 3 years ago

If we limited the maximum per frame stack size and probed properly, we could do split stacks no problem.

IIRC the initial Go implementation of split stacks also worked no problem (the benefits of owning the compiler and the ABI), and the reason it was ultimately abandoned was that it got very slow when you happened to repeatedly call a function when you had too little stack space left in the current segment (because you can’t grow the current segment, because you can’t move stack segments, because they may have pointers into them). If that is the problem, replacing a check in the function prologue with a page fault hitting the guard page looks unlikely to make this particular slow case faster.

throwaway8943453• 3 years ago

Go doesn’t have traditional stacks; it has growable stacks and they work out very well in practice. But yeah they aren’t segmented to my knowledge.

addaon6• 3 years ago

Go has auto-copied stacks [1]. This replaces a deterministic, statically-analyzable problem ("how much stack space does this need, worst case?") with unboundedly bad performance. Yay?

[1] https://blog.cloudflare.com/how-stacks-are-handled-in-go/

kayo_20211030• 3 years ago

Reading this, I did think "I want a pony". And also, "if my grandmother had wheels, she'd be a bicycle". The world we have is the world we've been given and stacks are a scarce resource simply because they actually run out. Wishing otherwise doesn't change anything.

bregma2• 3 years ago

Stack limits exist because of the halting problem. If we knew in advance which thread would need extra contiguous memory for deep recursion using variables of automatic storage duration we could allocates its stack at an address with enough space left.

We should just solve the halting problem. The we'd no longer need to implement automatic storage duration and call frames by using stacks. It's just that easy.

ndsipa_pomu3• 3 years ago

We should just solve the halting problem

That might be a little bit like "draw the rest of the damn owl" and besides, wouldn't that destroy our encryption schemes?

explaininjs6• 3 years ago

It’s a joke, it’s mathematically unsolvable. Though even if it were I don’t see the connection to encryption?

bregma2• 3 years ago

It's humour because the "halting problem" has a simple and elegant proof that it is impossible to solve in the general case. TFA's request for general computing to use unlimited stack operation for every thread of execution is equivalent to a call for the halting problem to be provably possible in O(1) time. It's the unexpected juxtaposition of these two oppositional ideas that provides the basis for humour.

Of course, if it has to be explained it loses its funny.

addaon6• 3 years ago

If we knew in advance which thread would need extra contiguous memory for deep recursion using variables of automatic storage duration we could allocates its stack at an address with enough space left.

And this is a real option. While determining the maximum stack size of an arbitrary program is halting-problem-equivalent (requires determining the maximum depth of the runtime call graph), we can trivially choose to write code where determining the maximum stack size is also trivial. This static analysis is commonly done on embedded systems, and essentially comes down to "don't write code that you can't guarantee the correctness of", which should be starting stakes anyhow.

Someone2• 3 years ago

There are, or may be, arguments for why stacks needed to be small on ancient machines. The history is fascinating, but it is not relevant to today’s systems, other than tiny embedded ones.

An argument against that is that processes on modern machines often use a single heap but many stacks (one for each thread), and that OSes typically have better facilities for growing the heap than for growing a stack.

Also, runtimes typically have better facilities to handle ‘out of heap memory’ than ‘out of stack memory’ conditions.

A workaround for that is to give each stack lots of room up-front, but that can be seen as wasteful, even if that’s only of virtual memory.

Growable stacks have their own problems (mostly, AFAIK, because of historical baggage), and requiring programmers to specify stack size isn’t ideal, either.

quotemstr5• 3 years ago

Having separate special parts of the address space for "heap" and "stack" is a weird anachronism anyway. We use mmap for stacks for anything but the main thread, and many heap implementations (e.g. jemalloc, OpenBSD malloc) just use mmap for the heap too.

If I had my way, we'd use mmap for literally all memory allocation in a process and get rid of sbrk() and the stack segment entirely. There's nothing intrinsic about these legacy affordances.

ec109685• 3 years ago

For the cost upfront of large stack sizes, are you referring to the fact that there isn’t generally a way to release back the stack’s memory if it is ever used by a thread?

Otherwise, large stack sizes seems like one of those scary things that doesn’t practically hurt you,

Someone2• 3 years ago

Let’s say you decide to give each thread a 1 terabyte stack, on the off chance it will run a recursive algorithm where (stack frame size × iteration depth) approximates that.

(Ignoring memory usage for administration, that is doable on 64-bit systems. 1 terabyte is 2⁴⁰ bytes, so you could have 2²⁴ ≈ 16 million such stacks in a 64-bit virtual address space)

Setting up the MMU to know about that will take time and memory, though. It also likely (details vary between systems) will introduce another layer of indirection in the tables used to translate virtual to physical addresses (https://en.wikipedia.org/wiki/Page_table) and thus slow them down.

Workaround would be to use huge page sizes, but that at is wasteful because that not only means large page sizes in virtual memory, which is plentiful, but also in physical memory, which is much scarcer (even if the hardware would support 64 address lines and had 2⁶⁴ bytes of RAM, that still would be shared between processes)

richardwhiuk2• 3 years ago

Recursive functions using stacks are more expensive in terms of memory than explicit recursion due to more careful state saving.

explaininjs6• 3 years ago

Could you explain what you mean by these two “types” of recursive functions here?

quotemstr5• 3 years ago

At a minimum, each frame of a recursively implemented algorithm in a typical AOT system without special allocations (say, milquetoast GCC 9) needs to save on each frame the return address in addition to whatever data the algorithm itself needs. Add on top of that a frame pointer, padding for stack alignment, and so on and you can end up with significant overhead you can avoid implementing the same algorithm with an explicit stack.

brokenkebaby• 3 years ago

The main statement of the linked story is that on modern machines stack doesn't need to be small therefore we can embrace on-stack recursion, and current general preference for iteration over recursion is just an old luggage. To me it seems to be true while we talking exclusively about amounts of memory. But there are caveats related to its management (compilers, OS, process/thread) so I don't think you are free to switch between the paradigms unless you work really close to bare-metal.

hamilyon2• 3 years ago

Never really thought about it that way. The thing is, the stack is deeply in the paradigm of C, machine code, compilers and silicon. Everything depend on the stack being really fast. If we add 1% overhead on stack operations, our programs become 0.5-1% slower, this is how critical stack speed is.

So, the tradeoff is that stack has 0 levels of indirection. It is not relocatable and not resizable as a consequence of speed requirement.

phkahler• 3 years ago

The stack mixes data and program flow. The later via return addresses. If you want to go all-in with the stack I'd say it's important to maintain 2, one for returns. Modern processors handle returns with special (caches?) hardware, which both eliminates the problem and demonstrates it.

kqr• 3 years ago

Wait, I always assumed small stacks wasn't about the number of stack frames, but the amount of data in them! It's expensive to copy data around and most stack frames are ephemeral so would imply copying data around.

(Of course, you could set a limit on the size of a stack frame instead of the entire stack, so maybe that's not a good explanation.)

User23• 3 years ago

I can’t find it, but somewhere, I think in the EWDs but maybe it was a book, I saw Dijkstra discussing the way the implicit stack makes “recursion”[1] as the term is usually used appear somehow privileged. When thinking about algorithms and data structures it’s better to be explicit about your use of a stack, queue, heap, or any other data structure. Also of course some algorithms are considerably more elegantly implemented with two explicit stacks rather than one explicit and one implicit.

[1] scare quotes because recursion is better thought of as a property of data structures than of algorithms and a stack is hardly the only available tool for working with recursive structures.

aenima4six2• 3 years ago

I tend to avoid stack based recursion when the application/routine could require unbound traversal depth (eg: depth is controlled by some non deterministic input, like user data). The last example that comes to mind was building an new enterprise financial rebalancer which needed to support dynamic asset model resolution. In a model, assets were dynamically associated via tagged characteristics. Models also supported including other models as children, so they were well represented with a stack like structure. This was a .NET based code base, which meant StackOverflow exceptions couldn't be caught (they immediately terminated the process unless some icky work arounds were used). For those reasons, we used heap based recursion to walk and resolve the final in memory model structure.

dreamcompiler4• 3 years ago

It's too bad more languages don't support tail call elimination. Tail recursion is even more difficult to grok than ordinary recursion, but once you grok it it's much easier to express many algorithms that way than with loops. Even though the assembler code generated from both may be identical.

As a Common Lisp programmer I think in mappings and tail recursion and I dislike using the loop construct. Sometimes loop is still the best solution but it's not as elegant.

Olreich3• 3 years ago

Can you provide a concrete example of an algorithm that’s easier to express with recursion?

dreamcompiler4• 3 years ago

"Easier" is in the eye of the beholder. To anyone trained entirely in imperative languages, recursion will always seem foreign and thus harder. But to someone familiar with functional programming, recursion is often easier to understand.

The canonical recursive example is factorial, but a better example for "easier" is quicksort. Quicksort is inherently recursive and it cannot be expressed without a stack, while factorial is not inherently recursive and is easy to express as a loop.

That's not to say you can only write Quicksort in a recursive language; I've seen Quicksort implemented in old versions of Fortran for example that had no notion of recursion. But since the algorithm is inherently recursive, if you write it in a non-recursive language you have to manually build a stack to keep track of your progress. This makes Quicksort in a non-recursive language require many more lines of code and be much harder to understand.

Having said all that, I'm not going to type a full implementation of Quicksort into an HN comment. Instead, here's factorial three ways in Common Lisp. I think rfact and trfact are clearer than lfact. You might disagree.

  (defun lfact (n)
    "Uses looping to compute n! No stack required."
    (let ((result 1))
      (loop for i from 2 to n
        do (setf result (* result i)))
      result))

  (defun rfact (n)
    "Uses ordinary recursion to compute n! Requires n stack frames,
     which is bad unless you know n will always be small."
    (declare (optimize (debug 3))) ;; tell the compiler not to optimize away the name, in case you want to trace rfact
    (if (< n 2)
        1
        (* n (rfact (- n 1)))))

  (defun trfact (n &optional (accum 1))
    "Uses tail recursion to compute n! No stack required."
    (declare (optimize (debug 1))) ; ensure tail call elimination
    (if (< n 2)
        accum
        (trfact (- n 1) (* accum n))))

The Absurdity Of Stacks

Related Stories