The Absurdity Of Stacks
tfeb.org
tfeb.org
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.
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.
[1] https://blog.cloudflare.com/how-stacks-are-handled-in-go/
2. Most programs (especially Go programs) aren’t embedded, so this isn’t much of a criticism.
3. If you can statically analyze a C program and make sure it doesn’t overflow the stack, why can’t you statically analyze a Go program and make sure it doesn’t grow the stack beyond a certain size? I’m not arguing that Go is a good fit for embedded, but I don’t see why throwable stacks are a major problem.
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.
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.
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.
It's the "factorial in recursive style" type of stuff that trips me up. I can read imperative code like I would read a book: I just do (assuming I'm familiar with the language), but this sort of recursive stuff just trips me up, never mind actually writing it.
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.
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.
That might be a little bit like "draw the rest of the damn owl" and besides, wouldn't that destroy our encryption schemes?
It's currently unsolved, but I don't think that it's been proved to be unsolvable as surely that would prove P ≠ NP. The connection to encryption is that integer factorisation could then be solved in polynomial time which would break current systems, though in theory a much longer key length could be used to try to outpace computer power, especially if the polynomial algorithm is hugely inefficient.
Edit: I see that the halting problem has indeed been proved to be unsolvable and it doesn't imply P ≠ NP
Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics
There is a solution to the halting problem. It’s that it is undecidable.
Of course, if it has to be explained it loses its funny.
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.
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.
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.
Otherwise, large stack sizes seems like one of those scary things that doesn’t practically hurt you,
(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)
Except you don't need to set it up until the page faults happen. You allocate the top-of-stack page in the MMU, probably physically map it (since it will be used when the task first executes), make a note in your memory mapping structures that all the rest is unmapped but mappable for this purpose, and when the stack-overflow page fault occurs, go in and add the page to the mapping.
If you're okay with this level of overcommitment of memory (and I'm not!), the page table management side of it is in the noise for performance and resource use.
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.
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?
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.
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.
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.
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))))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.
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.
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.
[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.
So, the tradeoff is that stack has 0 levels of indirection. It is not relocatable and not resizable as a consequence of speed requirement.
(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.)
You can use an arena allocator to get linear allocation on the heap too. Arena allocation is underused IMHO.