3 ms·

I didn't know that nodejs supports TCO under the flag (like on video), but unfortunately it was only for versions from 6 to 8. Curious why did they removed it

qsort 6y ago
In a practical working environment it creates more problems than it solves. It's an optimization that effectively turns non-working code into working code, in ways that aren't always obvious or predictable and possibly in different ways across different compilers/interpreters. I'd rather the code blow up in my face immediately than spend time wondering why it gets optimized on engine X and not on engine Y, or why seemingly trivial code changes cause the function to have drastically different runtime behavior. Clojure did this right. No TCO, loop/recur construct instead. As a side note at the cost of being snarky, it's also probably a good thing that developers who get overexcited about recursion are being encouraged to use proper functional idioms instead of abusing it.
- swiley 6y ago
  I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.
  - rbanffy 6y ago
    This is a magic vs. no-magic thing. TCO is a magical thing that implicitly changes the behavior of code with the same syntax. The code says the stack should blow up, but the compiler saves you from it. I'll side with the Python teaching that explicit is better than implicit. If the code says the stack will blow, then the compiler/runtime should not try to avoid that.
    - yvdriess 6y ago
      There's nothing magical about a language that says that a tail-call will reuse the same frame/record/instance. It's only magical and unreliable when it's not in the language spec.
      - leoc 6y ago
        And a well-defined TCO guarantee would probably not rank very high on the already long list of things that make it ... a bit tricky to discern the performance of a function from looking at the text of the function body.
    - dTal 6y ago
      It's not any more "magic" than garbage collection. The runtime figures out when memory is no longer required and frees it, through perfectly well-defined and easy-to-model rules. The code doesn't "say" the stack will blow because a finite stack isn't a language guarantee - it's simply an inconvenient fact of life.
  - qsort 6y ago
    Eh, kinda. They are obvious modulo a lot of things, such as what definition of tail call your compiler is using and what optimizations it performs. Your comment piqued my curiosity and I made a little experiment :) The following function: int rec(int n) { if (n < 1) return 0; return 1 + rec(n - 1); } will get TCOd by gcc but not by clang (!!) I don't know, probably I'm not smart enough for TCO, but I just don't want to work like that. It's a minefield.
    - yvdriess 6y ago
      That's not a tail recursive call.
      - qsort 6y ago
        That's precisely the point.
        yvdriess 6y ago
        I'm confused, how are you testing TCO by giving the compiler a non-tail call?
    - maverwa 6y ago
      Would you mind sharing the compiler versions and flags used? I tried to look at it in godbolt, but gcc 10.2 -O and clang 11.0 -O look pretty much the same. On the other hand, I know pretty little about C and its compilers ;)
      - qsort 6y ago
        clang 11.0, gcc 7.4, O2. I did that with whatever was already installed on my machines, YMMV.
    - CalChris 6y ago
      However, for -O3 on ARMv8, LLVM generates pretty good if slightly inscrutable code [1]: rec: // @rec bic w0, w0, w0, asr #31 ret That's taking the sign bit, replicating it to 32b and then using it as a not'd mask. negative numbers: w0, asr #31 => -1 bic w0, w0, -1 => and w0, w0, 0 => ret 0 positive numbers: w0, asr #31 => 0 bic w0, w0, 0 => and w0, w0, 0xffffffff => ret w0 gcc is also pretty good [2]: rec: cmp w0, 0 csel w0, w0, wzr, gt ret [1] https://godbolt.org/z/q9hM7z https://godbolt.org/z/q9hM7z [2] https://godbolt.org/z/6rbE5e https://godbolt.org/z/6rbE5e
- dan-robertson 6y ago
  I think I mostly agree. When TCE isn’t guaranteed, it seems pretty bad to have code that runs fine in one engine but blows up the stack in another. When it is guaranteed it’s still hard because modifications to code may break TCE and so as well as knowing what those things are (eg wrapping in a try block), you need to be careful about every change that breaks TCE to make sure that the code isn’t relying on TCE. Also I think JS might have extra problems due to eg arguments.caller. In languages which do have guaranteed TCE like scheme or ML variants, I think I would rather see some way to explicitly say “this is a tail call which should be eliminated” or “all recursive calls to this function should be tail calls” and then have the compiler complain if you have a call which should be eliminated but isn’t in tail position. I think the reason for clojure not doing TCE is that, in general[1], it is a global optimisation (not possible by simple syntax transformation) that the jvm doesn’t do. So clojure didn’t really have a choice in whether or not to have TCE. [1] it is more possible to transform recursive or mutually recursive code into iterative code, but the latter becomes hard in the face of a dynamic language where functions can be redefined and impossible to do locally for all tail calls.
- ollran 6y ago
  Clojure does not optimize tail calls because JVM does not support it.
  - bear8642 6y ago
    Thought there's extension enabling JVM tail optimization?
  - fulafel 6y ago
    Kind of. This comment summed it up well: https://news.ycombinator.com/item?id=26298891 https://news.ycombinator.com/item?id=26298891
MikeHolman 6y ago
Proper Tail Calls (PTC) were a problematic JS feature, and calling it "Optimization" is a huge misnomer. Only JavascriptCore (Safari) ever enabled it. In many cases PTC causes tail calls to be slower, and it messes up stack traces. This would happen even if a developer doesn't want/need tail calls. So it was a feature that would degrade performance and debuggability of existing websites to allow new code to use a more recursive style of programming. The main performance problem comes when you have tail calls that need to grow the stack. The engine will need to do work to adjust the stack frame. In languages like C++, the compiler chooses to do tail calls when it improves performance, but with tail calls as a language feature, engines have no choice in the matter and had to do it even when they would significantly increase call overhead. On top of this, there there were a number of implementation issues and corner cases. For example, most engines have some extra code layer for marshalling cross-site function calls that couldn't be removed. I also remember there being issues with Windows x64 ABI/stack frames. Tail calls from interpreter into JIT code were another implementation headache. All this added up to have JS engines basically boycott the feature.

qsort 6y ago

In a practical working environment it creates more problems than it solves. It's an optimization that effectively turns non-working code into working code, in ways that aren't always obvious or predictable and possibly in different ways across different compilers/interpreters. I'd rather the code blow up in my face immediately than spend time wondering why it gets optimized on engine X and not on engine Y, or why seemingly trivial code changes cause the function to have drastically different runtime behavior. Clojure did this right. No TCO, loop/recur construct instead. As a side note at the cost of being snarky, it's also probably a good thing that developers who get overexcited about recursion are being encouraged to use proper functional idioms instead of abusing it.

swiley 6y ago
I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.
- rbanffy 6y ago
  This is a magic vs. no-magic thing. TCO is a magical thing that implicitly changes the behavior of code with the same syntax. The code says the stack should blow up, but the compiler saves you from it. I'll side with the Python teaching that explicit is better than implicit. If the code says the stack will blow, then the compiler/runtime should not try to avoid that.
  - yvdriess 6y ago
    There's nothing magical about a language that says that a tail-call will reuse the same frame/record/instance. It's only magical and unreliable when it's not in the language spec.
    - leoc 6y ago
      And a well-defined TCO guarantee would probably not rank very high on the already long list of things that make it ... a bit tricky to discern the performance of a function from looking at the text of the function body.
  - dTal 6y ago
    It's not any more "magic" than garbage collection. The runtime figures out when memory is no longer required and frees it, through perfectly well-defined and easy-to-model rules. The code doesn't "say" the stack will blow because a finite stack isn't a language guarantee - it's simply an inconvenient fact of life.
- qsort 6y ago
  Eh, kinda. They are obvious modulo a lot of things, such as what definition of tail call your compiler is using and what optimizations it performs. Your comment piqued my curiosity and I made a little experiment :) The following function: int rec(int n) { if (n < 1) return 0; return 1 + rec(n - 1); } will get TCOd by gcc but not by clang (!!) I don't know, probably I'm not smart enough for TCO, but I just don't want to work like that. It's a minefield.
  - yvdriess 6y ago
    That's not a tail recursive call.
    - qsort 6y ago
      That's precisely the point.
      - yvdriess 6y ago
        I'm confused, how are you testing TCO by giving the compiler a non-tail call?
  - maverwa 6y ago
    Would you mind sharing the compiler versions and flags used? I tried to look at it in godbolt, but gcc 10.2 -O and clang 11.0 -O look pretty much the same. On the other hand, I know pretty little about C and its compilers ;)
    - qsort 6y ago
      clang 11.0, gcc 7.4, O2. I did that with whatever was already installed on my machines, YMMV.
  - CalChris 6y ago
    However, for -O3 on ARMv8, LLVM generates pretty good if slightly inscrutable code [1]: rec: // @rec bic w0, w0, w0, asr #31 ret That's taking the sign bit, replicating it to 32b and then using it as a not'd mask. negative numbers: w0, asr #31 => -1 bic w0, w0, -1 => and w0, w0, 0 => ret 0 positive numbers: w0, asr #31 => 0 bic w0, w0, 0 => and w0, w0, 0xffffffff => ret w0 gcc is also pretty good [2]: rec: cmp w0, 0 csel w0, w0, wzr, gt ret [1] https://godbolt.org/z/q9hM7z https://godbolt.org/z/q9hM7z [2] https://godbolt.org/z/6rbE5e https://godbolt.org/z/6rbE5e
dan-robertson 6y ago
I think I mostly agree. When TCE isn’t guaranteed, it seems pretty bad to have code that runs fine in one engine but blows up the stack in another. When it is guaranteed it’s still hard because modifications to code may break TCE and so as well as knowing what those things are (eg wrapping in a try block), you need to be careful about every change that breaks TCE to make sure that the code isn’t relying on TCE. Also I think JS might have extra problems due to eg arguments.caller. In languages which do have guaranteed TCE like scheme or ML variants, I think I would rather see some way to explicitly say “this is a tail call which should be eliminated” or “all recursive calls to this function should be tail calls” and then have the compiler complain if you have a call which should be eliminated but isn’t in tail position. I think the reason for clojure not doing TCE is that, in general[1], it is a global optimisation (not possible by simple syntax transformation) that the jvm doesn’t do. So clojure didn’t really have a choice in whether or not to have TCE. [1] it is more possible to transform recursive or mutually recursive code into iterative code, but the latter becomes hard in the face of a dynamic language where functions can be redefined and impossible to do locally for all tail calls.
ollran 6y ago
Clojure does not optimize tail calls because JVM does not support it.
- bear8642 6y ago
  Thought there's extension enabling JVM tail optimization?
- fulafel 6y ago
  Kind of. This comment summed it up well: https://news.ycombinator.com/item?id=26298891 https://news.ycombinator.com/item?id=26298891

MikeHolman 6y ago

Proper Tail Calls (PTC) were a problematic JS feature, and calling it "Optimization" is a huge misnomer. Only JavascriptCore (Safari) ever enabled it. In many cases PTC causes tail calls to be slower, and it messes up stack traces. This would happen even if a developer doesn't want/need tail calls. So it was a feature that would degrade performance and debuggability of existing websites to allow new code to use a more recursive style of programming. The main performance problem comes when you have tail calls that need to grow the stack. The engine will need to do work to adjust the stack frame. In languages like C++, the compiler chooses to do tail calls when it improves performance, but with tail calls as a language feature, engines have no choice in the matter and had to do it even when they would significantly increase call overhead. On top of this, there there were a number of implementation issues and corner cases. For example, most engines have some extra code layer for marshalling cross-site function calls that couldn't be removed. I also remember there being issues with Windows x64 ABI/stack frames. Tail calls from interpreter into JIT code were another implementation headache. All this added up to have JS engines basically boycott the feature.