3 ms·

> Tail calls. I actually wanted them! I think they're great. And I got argued into not having them because the project in general got argued into the position o

> Tail calls. I actually wanted them! I think they're great. And I got argued into not having them because the project in general got argued into the position of "compete to win with C++ on performance" and so I wound up writing a sad post rejecting them I don't understand the subtleties here: Is tail calls an optimization the compiler can do irrespective of the language? Or is there something that prevents this and requires the compiler to use stack here? Is there any visible effect to the programmer from supporting tail call or not, other than performance and stack depth? How does not supporting them compete with C++ performance?

layer8 3y ago
It’s about stack size. Programs that rely on tail calls (in particular recursive ones) may cause the stack to overflow when the language implementation doesn’t actually support tail calls, for example when using tail calls to recursively process a list that is larger than (some constant fraction of) the stack. With an infinite stack, it would just be an optimization, but in practice the stack is finite (and significantly smaller than the heap), and thus doesn’t lend itself to such a programming style when the implementation doesn’t support tail call optimization.
- Aardwolf 3y ago
  What I actually meant to ask is: given what you said, is supporting it then even a language feature, and not a compiler optimization instead? If rust says they don't support it, does it mean they don't even allow the compiler to do it? Obviously the syntax of the language itself already supports calling the function itself, and whether tail call optimization is supported or not doesn't affect the visible result afaik (except in case of stack overflows / performance)
  - layer8 3y ago
    It’s a language feature in the sense that it determines which programs are viable in the language. This is similar to garbage collection. In principle, you never have to explicitly free memory. Given infinite memory, garbage collection would only be an optimization. But since memory is finite, it becomes a language feature. Without garbage collection, programs that don’t free their unused memory will typically run out of memory sooner or later, similarly to how a tail-calling program will run out of stack space if the language doesn’t support it.
  - Tyr42 3y ago
    I suppose a difference of speed turns into a difference of ability at some point. If you can't rely on tail calls, you will have to manually trampoline the calls, just in case the optimization didn't kick in and your program dies. Or like xmtp or mail or whatever, you generally write your client assuming you are going to talk to any spec compliment server, which can stop you from using some extensions if you aren't sure they will be supported. Possible is not the same as guaranteed.
  - bluGill 3y ago
    Its not that the compiler cannot do it, it is that you cannot be sure the compiler will. Some constructs cannot be optimized for tail recursion. Languages with tail calls have guidelines of how to must write your code to ensure the tail call happens - often a seemingly small code change is the difference between tail call optimization happening or blowing up the stack. Second, in at least some cases where the optimizer can apply tail calls you need to be guaranteed it will happen. Nothing stops a C++ optimizer from applying tail call optimization (I don't know if any do, but it is allowed in some cases), but the language doesn't require it, so even if your optimizer supports it you can never know that it happens - and more importantly you cannot be sure that after changing the code or upgrading your compiler you will still get it. Thus even if your optimizer supports tail code optimization you dare not do deep recursion. If your language doesn't have support for tail calls you cannot do deep recursion with confidence. If your language does, then you can do deep recursion so long as you follow the rules of the language. (whatever those are - I'm not up on the latest research here, so I don't know the state of modern tail recursive languages are.)
- tinco 3y ago
  I thought on 64 bit systems the stack could basically be infinite for all practical purposes. Is this only a problem on more limited (i.e. <64bit) systems or am I misremembering when I last learned about stacks 10+ years ago?
  - aardvark179 3y ago
    It is always a problem, in the same way that holding on to huge objects is always a problem. Let's think about this in terms of a memory map, so ignoring limits of physical memory. On 64bit systems we actually have 48bits of usable address space, so that's 256TB. Now, the OS is going to need some workspace, but I think we can ignore that for this argument. So if you're only going to run 4 threads then each one could have a huge stack of 32TB, but if we wanted to run a huge server with a thread per connection then maybe we can only have 256MB per thread. Now, 256MB is pretty huge, but we probably want way more memory kept for heap storage and similar things (because managing lifetimes purely on the stack will be hard and might require a lot of copying of data), so it will be less than that. Now, you may ask, "Why not start with small stacks and make them bigger as needed?" It's a good question, but since our stacks are contiguous areas of memory and we don't know what's in them, we still have to space them out in our memory map allowing for as much growth as is needed. We might solve some of these problems by introducing segmented stacks, but this is one of those problems that crosses so many language, runtime, and OS boundaries that it's been hard to do in the general case, and it feels like gently nudging people towards writing code that can be tail-optimised is easier, just as it's easier to push people to use async than it is to provide systems and APIs that would allow for blocking code and a huge number of threads.
    - tinco 3y ago
      Thanks, I didn't realise the usable address space was so "small", those numbers are well within reasonable usage so that's definitely too limiting to just say it's infinite and not worry about it.
      - layer8 3y ago
        Apart from address space, there’s also simply the question of wasted resources, because in tail-call-optimizable programs, that stack space is by definition not strictly needed (otherwise it couldn’t be optimized away), so you might unnecessarily be wasting many GBs of memory. Lastly, TCO can improve cache locality and thus potentially speed up the program.
- pmontra 3y ago
  That's why we write programs that rely on tail calls only for languages that have TCO in their specification. Where TCO is idiomatic (e.g. Elixir) implementations not supporting it are impossible because they will be able to run only the simplest programs. The problem is adding TCO to a language that was born without it. It won't break existing programs but you'll be able to run a program using TCO only with a specific compiler or interpreter from a given version. It could catch up if the main implementation of the language does it, but often we care about compatibility with the alternative implementations. Think about Ruby and Python, MRI and CPython and all the other implementations of the language. If I'm not wrong, MRI added TCO under a runtime configuration variable but JRuby doesn't support it.
JonChesterfield 3y ago
Tail call optimisation means no work can be done after the call and before the return. You can't deallocate stack, call destructors, convert types, rethrow exceptions. Therefore _yes_ the compiler can always do it, but it may involve patching the called function to do some work. Splicing code into it and/or changing the calling convention. That's difficult to do for unknown caller/caller pairs, e.g. function pointers or separate compilation to machine code without enough metadata to patch it later. It runs a bit close to "sufficiently smart" compiler which usually means doable in theory but unlikely in practice. If you pick global designs to make them easier - probably most notably having the callee clean up the stack frame from the caller - and that makes other things slower, then you've given the competition an edge. Clang now has tail call annotations for C++, which works mostly because the compiler can reject them in the cases where it hasn't implemented the lowering. Rust can probably have it in the same approximate circumstances as C++.
- phi-go 3y ago
  Interesting that tail calls are mentioned and implied to never come to Rust. I agree with your assessment and actually there is a RFC[1] in the works to support them. (Note that while I'm the author, this RFC is definitely a community effort.) [1] https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407
deleted 3y ago
[deleted]

layer8 3y ago

It’s about stack size. Programs that rely on tail calls (in particular recursive ones) may cause the stack to overflow when the language implementation doesn’t actually support tail calls, for example when using tail calls to recursively process a list that is larger than (some constant fraction of) the stack. With an infinite stack, it would just be an optimization, but in practice the stack is finite (and significantly smaller than the heap), and thus doesn’t lend itself to such a programming style when the implementation doesn’t support tail call optimization.

Aardwolf 3y ago
What I actually meant to ask is: given what you said, is supporting it then even a language feature, and not a compiler optimization instead? If rust says they don't support it, does it mean they don't even allow the compiler to do it? Obviously the syntax of the language itself already supports calling the function itself, and whether tail call optimization is supported or not doesn't affect the visible result afaik (except in case of stack overflows / performance)
- layer8 3y ago
  It’s a language feature in the sense that it determines which programs are viable in the language. This is similar to garbage collection. In principle, you never have to explicitly free memory. Given infinite memory, garbage collection would only be an optimization. But since memory is finite, it becomes a language feature. Without garbage collection, programs that don’t free their unused memory will typically run out of memory sooner or later, similarly to how a tail-calling program will run out of stack space if the language doesn’t support it.
- Tyr42 3y ago
  I suppose a difference of speed turns into a difference of ability at some point. If you can't rely on tail calls, you will have to manually trampoline the calls, just in case the optimization didn't kick in and your program dies. Or like xmtp or mail or whatever, you generally write your client assuming you are going to talk to any spec compliment server, which can stop you from using some extensions if you aren't sure they will be supported. Possible is not the same as guaranteed.
- bluGill 3y ago
  Its not that the compiler cannot do it, it is that you cannot be sure the compiler will. Some constructs cannot be optimized for tail recursion. Languages with tail calls have guidelines of how to must write your code to ensure the tail call happens - often a seemingly small code change is the difference between tail call optimization happening or blowing up the stack. Second, in at least some cases where the optimizer can apply tail calls you need to be guaranteed it will happen. Nothing stops a C++ optimizer from applying tail call optimization (I don't know if any do, but it is allowed in some cases), but the language doesn't require it, so even if your optimizer supports it you can never know that it happens - and more importantly you cannot be sure that after changing the code or upgrading your compiler you will still get it. Thus even if your optimizer supports tail code optimization you dare not do deep recursion. If your language doesn't have support for tail calls you cannot do deep recursion with confidence. If your language does, then you can do deep recursion so long as you follow the rules of the language. (whatever those are - I'm not up on the latest research here, so I don't know the state of modern tail recursive languages are.)
tinco 3y ago
I thought on 64 bit systems the stack could basically be infinite for all practical purposes. Is this only a problem on more limited (i.e. <64bit) systems or am I misremembering when I last learned about stacks 10+ years ago?
- aardvark179 3y ago
  It is always a problem, in the same way that holding on to huge objects is always a problem. Let's think about this in terms of a memory map, so ignoring limits of physical memory. On 64bit systems we actually have 48bits of usable address space, so that's 256TB. Now, the OS is going to need some workspace, but I think we can ignore that for this argument. So if you're only going to run 4 threads then each one could have a huge stack of 32TB, but if we wanted to run a huge server with a thread per connection then maybe we can only have 256MB per thread. Now, 256MB is pretty huge, but we probably want way more memory kept for heap storage and similar things (because managing lifetimes purely on the stack will be hard and might require a lot of copying of data), so it will be less than that. Now, you may ask, "Why not start with small stacks and make them bigger as needed?" It's a good question, but since our stacks are contiguous areas of memory and we don't know what's in them, we still have to space them out in our memory map allowing for as much growth as is needed. We might solve some of these problems by introducing segmented stacks, but this is one of those problems that crosses so many language, runtime, and OS boundaries that it's been hard to do in the general case, and it feels like gently nudging people towards writing code that can be tail-optimised is easier, just as it's easier to push people to use async than it is to provide systems and APIs that would allow for blocking code and a huge number of threads.
  - tinco 3y ago
    Thanks, I didn't realise the usable address space was so "small", those numbers are well within reasonable usage so that's definitely too limiting to just say it's infinite and not worry about it.
    - layer8 3y ago
      Apart from address space, there’s also simply the question of wasted resources, because in tail-call-optimizable programs, that stack space is by definition not strictly needed (otherwise it couldn’t be optimized away), so you might unnecessarily be wasting many GBs of memory. Lastly, TCO can improve cache locality and thus potentially speed up the program.
pmontra 3y ago
That's why we write programs that rely on tail calls only for languages that have TCO in their specification. Where TCO is idiomatic (e.g. Elixir) implementations not supporting it are impossible because they will be able to run only the simplest programs. The problem is adding TCO to a language that was born without it. It won't break existing programs but you'll be able to run a program using TCO only with a specific compiler or interpreter from a given version. It could catch up if the main implementation of the language does it, but often we care about compatibility with the alternative implementations. Think about Ruby and Python, MRI and CPython and all the other implementations of the language. If I'm not wrong, MRI added TCO under a runtime configuration variable but JRuby doesn't support it.

JonChesterfield 3y ago

Tail call optimisation means no work can be done after the call and before the return. You can't deallocate stack, call destructors, convert types, rethrow exceptions. Therefore _yes_ the compiler can always do it, but it may involve patching the called function to do some work. Splicing code into it and/or changing the calling convention. That's difficult to do for unknown caller/caller pairs, e.g. function pointers or separate compilation to machine code without enough metadata to patch it later. It runs a bit close to "sufficiently smart" compiler which usually means doable in theory but unlikely in practice. If you pick global designs to make them easier - probably most notably having the callee clean up the stack frame from the caller - and that makes other things slower, then you've given the competition an edge. Clang now has tail call annotations for C++, which works mostly because the compiler can reject them in the cases where it hasn't implemented the lowering. Rust can probably have it in the same approximate circumstances as C++.

phi-go 3y ago
Interesting that tail calls are mentioned and implied to never come to Rust. I agree with your assessment and actually there is a RFC[1] in the works to support them. (Note that while I'm the author, this RFC is definitely a community effort.) [1] https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407

deleted 3y ago

[deleted]