It's a stack overflow which means it's using recursion and for historical reasons that don't make sense any more, stacks are teeny tiny on 64-bit Linux - apparently only 8 MB on Linux! I'm not sure why they don't raise it to something reasonable like 4 GB. I guess because they want consistency with 32-bit? Maybe we can finally change it if/when they phase out support for 32-bit Linux. Apparently it might not be that far away:
8MB is the default per-thread stack size from glibc, also seems to be the default "ulimit" from pam or the kernel, I'm not sure. So for the main/default thread (or if not using threads) the process can use setrlimit() and for threads it can use pthread_attr_setstacksize() to get bigger stacks if it knows it may need them.
8MB is pretty huge though; musl libc is famous for defaulting to much smaller per-thread stack size of 128KB (to avoid over-committing lots of memory when there are many threads - the main dev is really principled/opinionated on this topic, but again there are a few ways for applications to explicitly size their stacks as large as they need). Linux kernel threads get a bit less than 16KB!
For what it's worth there's reasonably active [1] work on implementing opt-in guaranteed tail calls - but it's not particularly fast going. LLVM (the backend rust uses) needs better support for musttail (e.g. some architectures just don't support it [2]).
By-default guaranteed tail calls really isn't rust's style, because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it. If you want to guarantee that a call can't allocate a new stack frame you should have to say it.
I don't think that's related? The bug alluded to looks something like
function rm(node) {
for (const child of ls(node))
rm(child);
unlink(node);
}
and no amount of tail call optimization will save you here, because this isn't tail recursion. Of course you could rewrite it using an explicit stack + tail recursion, but then you might as well be using a while loop.
The point is that such bugs shouldn't exist in the first place.
Using recursion on unbounded inputs on a programming language that doesn't support that (which are most) is an extremely classical mistake that really should be known to all programmers, especially those of low level languages that care about safety.
Every time you call something recursively you should be thinking "how deep is this?".
By that logic, why even spend effort migrating from a known-working implementation to one which is known to have outstanding bugs that there isn't enough bandwidth to fix?
It's a stack overflow which means it's using recursion and for historical reasons that don't make sense any more, stacks are teeny tiny on 64-bit Linux - apparently only 8 MB on Linux! I'm not sure why they don't raise it to something reasonable like 4 GB. I guess because they want consistency with 32-bit? Maybe we can finally change it if/when they phase out support for 32-bit Linux. Apparently it might not be that far away:
https://lwn.net/Articles/1035727/
8MB is the default per-thread stack size from glibc, also seems to be the default "ulimit" from pam or the kernel, I'm not sure. So for the main/default thread (or if not using threads) the process can use setrlimit() and for threads it can use pthread_attr_setstacksize() to get bigger stacks if it knows it may need them.
8MB is pretty huge though; musl libc is famous for defaulting to much smaller per-thread stack size of 128KB (to avoid over-committing lots of memory when there are many threads - the main dev is really principled/opinionated on this topic, but again there are a few ways for applications to explicitly size their stacks as large as they need). Linux kernel threads get a bit less than 16KB!
OIC. Rust doesn't guarantee optimizing tail recursion. How unfortunate for a language that's getting widespread adoption.
For what it's worth there's reasonably active [1] work on implementing opt-in guaranteed tail calls - but it's not particularly fast going. LLVM (the backend rust uses) needs better support for musttail (e.g. some architectures just don't support it [2]).
[1] https://github.com/rust-lang/rust/issues/112788
[2] https://github.com/rust-lang/rust/issues/153827
By-default guaranteed tail calls really isn't rust's style, because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it. If you want to guarantee that a call can't allocate a new stack frame you should have to say it.
13 replies →
I don't think that's related? The bug alluded to looks something like
and no amount of tail call optimization will save you here, because this isn't tail recursion. Of course you could rewrite it using an explicit stack + tail recursion, but then you might as well be using a while loop.
Do any widely used languages guarantee tail call optimization? It's a pretty niche feature.
2 replies →
When triaging an issue you have to prioritise. Do you fix a problem that affects 2-3 people or one that may affect thousands?
The point is that such bugs shouldn't exist in the first place.
Using recursion on unbounded inputs on a programming language that doesn't support that (which are most) is an extremely classical mistake that really should be known to all programmers, especially those of low level languages that care about safety.
Every time you call something recursively you should be thinking "how deep is this?".
By that logic, why even spend effort migrating from a known-working implementation to one which is known to have outstanding bugs that there isn't enough bandwidth to fix?
Fashion.
Rust ? Because of ... memory safety. /s