[rust-dev] Tail call optimization
graydon at mozilla.com
Wed Apr 10 10:21:23 PDT 2013
On 10/04/2013 5:43 AM, Artella Coding wrote:
> Hi does rust do tail call optimization? The reason I am asking is that
> the following tail call recursive implementation results in a stack
> overflow. Thanks.
No, and it very likely won't. We have a longstanding bug on this:
as well as a wiki page and several mailing list threads:
The summary of all this is:
- We all know that tail calls are a virtuous language feature.
Further elaboration of their virtues is not required. Many of us
have lisp and ML backgrounds and would quite like them. Their
absence is heartache and sadness, not arrived-at lightly.
- Tail calls "play badly" with deterministic destruction. Including
deterministic drop of ~ boxes. Not to say that they're not
composable, but the options for composing them are UI-awkward,
performance-penalizing, semantics-complicating or all of the above.
- Tail calls also "play badly" with assumptions in C tools, including
platform ABIs and dynamic linking.
- Tail calls require a calling convention that is a performance hit
relative to the C convention.
- We find most cases of tail _recursion_ convert reasonably well to
loops, and most cases of non-recursive tail calls encode state
machines that convert reasonably well to loops wrapped around
enums. Neither of these are _quite_ as pretty as the
tail-call-using variants, but they do work and are "as fast"*,
as well as idiomatic for C and C++ programmers (who are our
I'm sorry to be saying all this, and it is with a heavy heart, but we
tried and did not find a way to make the tradeoffs associated with them
sum up to an argument for inclusion in rust.
* speed-wise, a switch-in-a-loop state machine is indirect dispatch so
will likely run slower than a state machine encoded by tail calls from
state to state; on the other hand if the way to get this performance
"back" is to turn on tail calls everywhere, we'd be trading one isolated
suboptimal-perf case for a cross-all-programs suboptimal-perf tax. We
don't find this trade acceptable.
More information about the Rust-dev