Hacker News Reader

> would it really cost that much (as until the memory was touched it wouldn't really be allocated).

The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever.

There are some solutions like trying to mark the stack below you freeable but it is hard to do this in a way that doesn't cause huge performance concerns if you happen to be crossing whatever boundary is picked often. IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop.

> IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop.

They used to do segmented stacks. The bad overhead is not in allocation, but in switching between segments when stack pointer is oscillating around the boundary — but if you want to allocate really many stacks that could grow large, you don't have much choice: either this or tracking pointers that need to be updated on reallocation. Normal contiguously mapped stack, but with dynamic growing and shrinking of actually mapped pages, is an entirely different proposition.

In an implementation of a language that can't take the address of a local variable, you can move some stack frames to the new segment when you switch segments, 256 bytes or so. Then, to oscillate around the boundary, you need to return enough times to deallocate those 256 bytes. This will cost enough to swamp the cost of switching segments.

(If you can take the address of a local variable, but you have garbage collection and can handle memory allocation failures by exiting, you can heap-allocate whatever local variables have their address taken.)

Segmented stacks are a particularly efficient way to implement call/cc.

Ah, that makes more sense, since you could easily limit stack deallocation to once a second or whatever.

> So you effectively cache all of the space your program needs forever.

All the space your program uses at the largest stack size, you mean, which is different. Until you touch it, the huge stack is purely virtual. And it only lasts until you restart the program.

Yes, if you default to a 10 GB stack, then recursively tree-search over 9 GB of data, then close the data and spend the next week with 1 MB data that only touches the bottom of the stack, you'll have 8.999 GB swapped out, which does suck.

But that only happens if you run the program on that 9 GB of data. The alternative was to fault when you overflowed the smaller stack when that data was imported.

It does mean if there's an infinite recursion bug, instead of crashing quickly with a stack overflow, you have to wait while it pages out other programs and fills the whole 10 GB of stack...

Yes, that is basically what I mean. If you are going to use a very large amount of stack space you should consider alternatively allocating something on the heap and freeing it afterwards.

Yes, if most of your program is using roughly the same amout of stack space then it is great. However I think if you are worried about running out then you are likely using far more than the average part of your program.

So yes, it isn't intrinsically bad, but context important to evaluate the decision.

I assume you're describing a degenerate case where a tree structure is unbalanced. When operating at that scale, the overhead from all the function calls alone is going to be significant. It's likely going to be maddeningly slower than an iterative solution, like getting an answer in minutes vs. seconds.

If it's a balanced tree, then consuming 9GB of stack to do a search would imply that the data structure is what, on the order of 2^1000000 in size? Yikes :-)

Not every unbalanced tree is necessarily a degenerate situation. Syntax trees aren't necessarily balanced naturally, for example. (They typically are somewhat balanced, of course, but if you do have one that's unbalanced, there's no way of balancing it.) Search trees for NP-hard problems may be an even better example.

My statement was within the context of there somehow being 10GB of node metadata (which could mean different things, but I'm assuming it means 10GB of stack usage to recursively visit each node.)

If you're up to 10GB worth of nodes in a syntax tree, you're probably doing something elaborate enough that you'd want to squeeze out every ounce of performance, and you're possibly a domain expert. Maybe you're making a static analysis tool? On the other hand, a lot of static analysis tools are painfully slow, so maybe there's a lot of recursive searching on deep data structures going on!

Likewise, if you're trying to solve an NP-hard problem and you're recursing through 10GB of anything, you're probably already asking the computer to do something unreasonable by many orders of magnitude, and all a larger stack would do is delay an eventual out of memory error. Or, you're doing something clever and knowingly pushing the computer to its limits, and so you once again would want to squeeze out every ounce of performance and go with an iterative solution.

> The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever.

What do you mean? It will get freed once you pop that stack-frame won't it?

No. It was never allocated either.

It was virtual memory before it was used, but once you use it, it's mapped into physical memory and marked as dirty. So it may be swapped out or live there, those are the only two options.

It would take your OS being fully aware of your usage schema for it to be able to free the memory.

Zig appears to have a proposed solution to this similar to your option 1, move recursion to the heap.

https://github.com/ziglang/zig/issues/1639

They're also looking at static analysis of the maximum stack depth which might help in some cases.

Being able to make recursive functions use the heap would be great. I assume it would need to be opt-in since you'll change performance characteristics, but I almost always rearrange recursive algorithms to use a loop and a heap allocated stack structure instead. There's no reason the compiler couldn't help do that for me.

I'm highly skeptical that static analysis of maximum stack depth will work, because of higher-order functions.

In rust, unsafe operations can be marked such to silence the compiler when you know better; one could imagine something similar for a stack depth analyzer in zig. Or, for example, zig could use a finite stack depth when it can prove that's feasible, and emit code that will spill to the heap for cases it can't.

Any recursive tree traversal function is incorrect. You need to write the function in an iterative fashion. Hoping that a recursive function won't run out of stack space is like allocating 500 characters to an input field and hoping that the user never will enter longer inputs. Consider a degenerate tree consisting of a linked list of N nodes. If N is large (100m perhaps) you will inevitably run out of stack.

I agree where there isn't inherently a stack. Many of the introductory examples of recursion are trivially transformed to an iteration in constant space.

However, there are plenty of interesting cases where if you don't use recursion, you end up having to implement your own stack as a resizable vector.

The question "why should the busy work of hand-rolling your own stack be necessary?" is the kind of question that you don't want to waste too much time on as a working programmer, but unless some people think deeply about such questions, the field as a whole stops progressing.

As others point out in this discussion, with a 64-bit address space one could organize the stack(s) in such a way that recursion could use all of physical memory if necessary.

As much as I love recursive algorithms, I couldn't agree with you more. Why do the clever and pretty thing, when it is better to do the less elegant but reliable thing.

+1, though in general designing an iterative solution is more effort for problems that have intuitive recursive solution so OPs argument has some merit.

The initial/main thread stack size is dynamic, it grows until it runs into another allocation (and these days there are guard pages and such). You can already use 128MB on the initial/main stack, even with musl-libc / Alpine linux (it needs to be linearly probed it if it's unreasonably huge, so the OS isn't surprised by a random memory access out in the middle of nowhere, but the compiler should do that automatically these days).

You can also request whatever stack size you need for additional threads when you create them, this has always been a good idea.

It's only the default stack size for non-main threads, if you don't specify it, which may be considered reasonably limited.

> The initial/main thread stack size is dynamic That seems doubtful, AFAIK all OS have a static allocation for the main thread, just one that is commonly (though not necessarily) much larger than what they give off-threads, as https://ariadne.space/2021/06/25/understanding-thread-stack-... quotes Windows gives 1MB to all threads, while macOS or OpenBSD 4.6+ give 8MB to the main thread and 512k to off-threads.

The former would not merit consideration if it was automatically increased.

> it grows until it runs into another allocation

Which it won't because vmem.

> and these days there are guard pages and such

That just makes the access segfault if the stack allocation is not large enough to straight jump over the guard page.

I'm not so familiar with other operating systems, but on Linux and presumably other unixes, the only thing holding back the initial/main "process stack" is ulimit. Try "ulimit -s unlimited". (On macOS that increases it from 8MB to 64MB, but on linux it seems to really go unlimited)

Honestly, there is almost no difference between a purely recursive implementation on the stack and one that uses a passed-in stack structure (whether extensible or fixed) in terms of complexity. Though I can see why it would be nice if the languages supported some sugar for this.

A good tree will have something like log(n) depth so normal recursion should be fine.

Apart from recursive algorithms, stack size can be determined by static analysis.

Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?

> Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?

As already mentioned, perf can capture call stacks, but those are statistical samples, so not necessarily complete.

callgrind (https://www.valgrind.org/docs/manual/cl-manual.html) by contrast can capture all call-stacks.

kCacheGrind/qCacheGrind (https://kcachegrind.github.io/html/Home.html) can be used to view the output from either perf or callgrind. Sources for kcachegrind, including converters from perf, oprofile, etc., can be found at https://github.com/KDE/kcachegrind

> A good tree will have something like log(n) depth so normal recursion should be fine.

Yes, this is true for comparison/search/sort/bucketing algorithms. But in other applications (e.g. graph theory, networks, sparse matrices) a depth of n, for n elements, can be perfectly legitimate. Or it can even be an edge case, but one you don't want to handle by just segfaulting.

> Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?

Linux perf can collect the necessary data. Then for frontends, I am not sure. KDAB's "hotspot" ( https://www.kdab.com/tag/perf/ ) can do flamegraphs, but this may be more performance-oriented than what you're looking for.

Edit: perf can collect the data statistically. It will miss many calls, the ones that are the least time-consuming.

> A good tree will have something like log(n) depth so normal recursion should be fine.

But in many contexts you have to be robust against a bad tree.

> Apart from recursive algorithms, stack size can be determined by static analysis.

Not always, in the presence of dynamically sized arrays (or alloca and friends).

https://llvm.org/docs/Passes.html#dot-callgraph-print-call-g...

Yeah. You won't be able to fit the tree in memory long before you overflow the stack while recursing down the tree.

I recall that the Rust compiler uses the stacker crate [0] to grow the stack into the heap, and it's under the rust-lang organization on GitHub, so it's probably the closest you can get to an "in-language option" without it actually being in the standard library. However, it currently isn't supported for several platforms due to the lack of a suitable OS interface.

[0] https://docs.rs/stacker/0.1.14/stacker/

I did try to enlarge the default stack size on Linux and ran into problem that it caused maximum number of threads to decrease. Because each thread has its own stack so it's (virtual memory limit)/(stack size) iirc and if you set stack size to 1G you'll get very low threads limit.

> but feels like reimplementing for no reason

In C++, std::vector::emplace_back() and pop_back() are in the standard library for a decade now.

Well that's a stack, but it's not a call stack, which is the point.

it's even worse in the kernel. I think it's 16kb

yes, kilobytes.

Could also be solved if the compiler supported Tail calls optimization

I don't think tail call will help depth-first ("obvious recursive way") tree algos.

It doesn't help with breadth-first searches either. A non-degenerate tree of depth N will use O(N) space, and that space will be on the call-stack if you use a recursive algorithm to access it.

As long as you use less than 1 page per activation record though, most modern libc implementations behave safely under unbounded recursion as they will allocate a guard-page around each stack.

[edit]

It would also be useful if the compiler could warn about activation records larger than 1 page. Absent alloca (and deprecated c99 VLAs), that should be statically knowable.

A BFS is essentially a while loop with a queue datastructure. This is (relatively) easy to implement in TCO-recursive erlang/elixir, which is what I'm currently most proficient in. And, yeah, TCO would help.

What does a recursive breadth-first search look like? I think you'd have to contort yourself to write that, which is why people are specifically mentioning depth-first where recursion is easy and natural.

Ah you're right; the most natural BFS would be tail-recursive or iterative.

The main reason to use recursion is to use the stack variables, when tail call optimization is possible people usually just prefers loops.

TCO is an optimization. It's not always possible.

It's a misnomer. It's not just "an optimization"; in some cases, it alters program semantics.

Usually the only visible side-effect of TCO is stack trace compression and failure to exhaust the stack. You can call that semantics if you like, but I think most people wouldn't. It's absurd that Java doesn't do TCO because of the stack compression "issue" (as I understand, that's why Java doesn't TCO).

> You can call that semantics if you like, but I think most people wouldn't.

Tail Call Optimization (TCO) is an optimization, yes;

but if Tail Call Elimination is required in the implementation of a language as it is in Scheme, then programmers in the language can rely on it (along with lexical scope) to write iterative loops instead as recursive calls. That is a change in program language semantics.

see Guy Steele's "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO" http://dspace.mit.edu/handle/1721.1/5753

> but if Tail Call Elimination is required in the implementation of a language as it is in Scheme

This is also supported as a non-standard extension in C, C++, and Objective-C as of Clang 13: https://clang.llvm.org/docs/AttributeReference.html#musttail (I implemented this).

> see Guy Steele's "Debunking the 'Expensive Procedure Call' Myth

Yes! :) I cited this paper in my blog article describing how we are using musttail: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

My point is that adding TCO is not a breaking semantics change, as its only visibility will be through a) the fact that more code works with it than w/o it, b) elision of tail-calling frames in stack traces. In particular I don't consider (b) to be a problem. I'm aware (b) is a matter of opinion, but really, TCO is much too valuable to use (b) as an argument against TCO.

Termination instead of divergence definitely is a change in semantics.

No, failure to fail is not a change in semantics.

EDIT: "My program used to fail with a stack size exhaustion error, but now it works -- I'm so angry about this!" -no one ever.

But they'd complain about the opposite -- for example if the program were an external-event-driven state automaton.

TCO does not do the opposite. TCO helps avoid stack exhaustion without introducing new faults.

TCO might cause your program to avoid one stack exhaustion fault only to reveal a different fault (possibly a different stack exhaustion fault). This is not a semantics change. And it's not a bug either.

What do you mean by "reveal a different fault"? A program with an indefinite amount of tail calls does not have "a fault".

If you have a program that fails due to stack exhaustion, but fixing it by enabling TCO causes it to run longer and therefore run into some other problem...

But that's not a fault in the program. That's a fault in its execution environment revealed by the program.

C++ compilers are free to optimize infinite loops without side effects away and people are generally fine with that.

Well, I'm sure this is not the worst thing about C++ that C++ people are "generally fine with", so that really doesn't tell me a lot. Not quite sure if this applies to useful programs, though. Lack of tail call elimination can definitely break a class of useful programs even with side effects.