[rust-dev] Tail call optimization

Graydon Hoare 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:

https://github.com/mozilla/rust/issues/217

as well as a wiki page and several mailing list threads:

https://github.com/mozilla/rust/wiki/Bikeshed-tailcall
https://mail.mozilla.org/pipermail/rust-dev/2011-August/000689.html
https://mail.mozilla.org/pipermail/rust-dev/2012-January/001280.html
...

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
     primary audience).

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.

-Graydon


* 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 mailing list