Comment by jcranmer | Hacker News Reader

Comment by jcranmer | Hacker News Reader

Parent Full thread

> It's probably a reasonably good measure of function call overhead in different languages

It's actually not. Fibonacci has a near-tail call in it that can convert some of the recursion into a loop. Furthermore, the runtime is dominated by useless recomputation that can be handled by memoization. So the distinction between languages is going to be dominated by their ability to do some moderately complex optimizations rather than by any intrinsic performance characteristics of their implementation.

Moreover, because the code is so small, there is likely to be major side effects as a result of effectively random differences--consider the effects of the code placement that cause a spurious difference between C and C++ kernels of about 20%. The JS version is going to get hit with a deoptimization at the very end (it might not impact performance) because the final result does not fit in an int32_t, and suddenly fib is no longer a well-typed function.

Microbenchmarking is _hard_, and it is all too easy for the microbenchmark to cease measuring the things that you want to measure.

Fibonacci (as implemented here) shouldn't be aided by any TCO. The execution trace will be something like:

  F(N) -- F(N-2) ...
   |
  F(N-1) -- F(N-3) ...
   |
  F(N-2) -- F(N-4) ...

But each has to return to the original caller because a summation still has to happen. The actual tail call is to the +/2 function.

F(N) can't complete until F(N-1) and F(N-2) have completed so it can sum up the values. If you pass the earlier computation, F(N-1), down to F(N-2) as a second parameter, you could get a tail call on the last part.

  fib(0, Val) -> Val + 1;
  fib(1, Val) -> Val + 1;
  fib(N, Val) ->
    T = fib(N-1,Val),
    fib(N-2,T).

(I think I wrote that correctly, can't test here.)

But that's a non-obvious tranformation. I really would like to see the compiler that recognized that this was a valid (computational) equivalent to the original.

But it is aided by tail-call optimization. Suppose you have a function as follows:

   int foo(int x) {
     if (test(x)) return C;
     return evaluate(x) + foo(adjust(x));
   }

I can turn that function into:

   int foo(int x) {
     int accum = C;
     for ( ; !test(x); x = adjust(x)) {
       accum += evaluate(x);
     }
     return accum;
   }

In the case of fibonacci, that equates to:

   int fib(int x) {
     int accum = 1;
     for (; x > 1; x -= 2) {
       accum += fib(x - 1);
     }
     return accum;
   }

We still turned the recursive call (or one of them, at least), into a while loop.

And this idiom is recognized by both gcc and llvm. In fact. llvm has a test that specifically makes sure fib is transformed as thus: https://github.com/llvm-mirror/llvm/blob/30fa583f8430bfc7935...

Reply on news.ycombinator.com