Recursive fibonacci benchmark using top languages on GitHub

Re:Recursive fibonacci benchmark using top languages on GitHub by Jtsummers on Friday September 28, 2018 @04:13PM (#18096667)

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.

[ Parent | on HN ]

Re:Recursive fibonacci benchmark using top languages on GitHub by jcranmer on Friday September 28, 2018 @04:32PM (#18096804)

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...

[ Parent | on HN ]