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.
F(N) -- F(N-2) ...
|
F(N-1) -- F(N-3) ...
|
F(N-2) -- F(N-4) ...
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).
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.
int foo(int x) {
if (test(x)) return C;
return evaluate(x) + foo(adjust(x));
}
int foo(int x) {
int accum = C;
for ( ; !test(x); x = adjust(x)) {
accum += evaluate(x);
}
return accum;
}
int fib(int x) {
int accum = 1;
for (; x > 1; x -= 2) {
accum += fib(x - 1);
}
return accum;
}
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...