That is an interesting idea. Mind expanding on how that would look from an user API perspective?[1]
You could use stacker — Rust implementation // Lib.rs until that happens though, and rustc does so.
Not from a competitive angle, but from an actual reliable production angle, which is what I care about. Competitions don't interest me in the slightest: making something useful and long lasting is much more rewarding. ↩︎
Are you thinking more green threads or just bumping the stack reservation? In 64-bit we should be able to use eg. gigabyte sized stack regions without trouble.
I suspect the only reason we don't is that generally you're far more to hit a stack overflow with infinite recursion than actually using all that space, and trying to unwind a gigabyte sized stack would be a disaster.
I was thinking of that: have a large virtual memory stack reservation in 64-bit for the main thread. For other threads it's already configurable. It seems like it could easily be like 1 TB for the main thread, couldn't it?
I am not sure how well operating systems support this, you don't want this to count towards memory commitment for the process until the stack actually grows that large.
The common advice to turn recursive algorithms into iterative algorithms to save stack space seems like creating a pointless artificial problem. Why should I be saving stack space like it's some precious resource? Why should I be essentially re-implementing the concept of stack frames and return addresses manually when the compiler can already do this automatically?
A disaster how? What exactly is the problem?
This is true, but don't forget that function prologs and epilogs can easily become a dominating factor too for many cases.
If nothing else, 1GB of 32-byte frames is ~31 million frames to print. You might be waiting a day for it to finish printing as it looks up the function name over and over again, or even run out of memory depending on how it's implemented; I rather doubt it's a use case that's been considered much when the normal depths is more like ~100. Even if that was very efficiently implemented, it would be so large it would blow completely past any terminal scrollback and make most editor setups fall over.
I think you would want to just capture the first and last hundred frames or something? It might still take a while to chew through that many frames, though....
Yeah it might not be the optimal way to solve a problem, but seems like it should be allowed. Sometimes non-optimal is good enough. You can also do all kinds of optimizations to deal with function call overhead with some sort of grouping or batching.
OK so you're talking about printing stack backtraces, not about stack unwinding.
There are all kinds of ways a buggy process can end up printing a huge amount of text to stderr other than backtraces. For instance, you could have a Debug impl for a recursive data structure on the heap print a huge amount of data. Or you can have a simple infinite loop print something. It's not a big deal, you can always kill the process. And yeah, it can be easily solved by limiting the size of printed backtraces. It doesn't seem like a good rationale for preventing deep recursion.
Not necessarily printing it, just capturing might have issues with that deep a stack, but yeah it would be solved let quick if it was popular. I think it's just a case of too many small reasons for devs not to, and no really big reasons to do so, for that to be the case.
You can reserve a stupid big stack perfectly fine already, it doesn't commit pages until they're actually reached even, but as a library you generally don't have a good enough reason to start another thread or ask the app to do so for you, and it's generally easy enough to just remove the recursion.
You mean by launching a new thread? It seems like it actually all immediately counts towards limits of virtual memory for a process. I tried allocating a 4 GB stack for a new thread and it failed on playground.
I don't think so. You have to re-express the control logic in your recursive function as an explicit state machine rather than using normal control flow of the language.
Hmm. Even a 4TB stack worked fine for me on Windows, but gave WouldBlock on WSL, which isn't the error I'd expect. Anything up to 16GB worked without showing up in usage at all, so I assume there's just some heuristic for "implausible values", possibly the amount of physical memory? I couldn't find anything with a search though...
Edit: the error code seems to be `thread::Builder::spawn` returns WouldBlock for EAGAIN · Issue #46345 · rust-lang/rust · GitHub and is probably EAGAIN.
From that thread, sounds like that happens if it just can't find address space, which is... implausible in x64. man for pthread_create (I'm guessing) says:
EAGAIN The system lacked the necessary resources to create another thread, or the system-imposed limit on the total number of threads in a process {PTHREAD_THREADS_MAX} would be exceeded.
which doesn't help much.
Aa a long time programmer of small embedded system where memory is limited and virtual memory non-existent I find this talk of infinite stacks becoming an expected part of Rust very disturbing.
The stack can't shrink once it has grown. You would need a way to tell the OS "I don't need these pages of stack any longer". On Unix madvise could probably be used for this, but you also need langusgr/compiler support for doing so on the stack. And you definitely don't want to do so after every call frame, that would be expensive. So that seems non-trivial.
Once if my hobby projects at the moment is a Gameboy emulator, where the target game stacks tend to top out about 10 bytes, so yeah, I get the feeling 
Moderator note: Will rust be good for competitive programming? - #21 split here
Also, don't some platforms not have the ability to detect stack overflows? I think the implementation only guarantees you get a segfault.