Recursive Fibonacci Benchmark using top languages on Github

Dear all, this popped up in the hacker news. It uses julia 0.6.3 version.

Being competitive with Go is pretty neat (benchmarks include compilation time, which may be the right choice in some contexts but is generally a somewhat curious choice).

1 Like

One reason for the C++ version being faster than Julia, is that the compiler is able to use a more efficient formula for Fibonacci. Instead of this:

function fib(n)
    if n <= 1 return 1 end
    return fib(n - 1) + fib(n - 2)
end

The C++ version generates this:

function fib2(n)
    n <= 1 && return 1
    sum = 0
    while n > 1
        sum += fib2(n-1)
        n -= 2
    end
    return sum + 1
end

That formula would be faster in Julia too:

julia> @time fib(46)
  9.383770 seconds (5 allocations: 176 bytes)
2971215073

julia> @time fib2(46)
  5.923350 seconds (5 allocations: 176 bytes)
2971215073
3 Likes

Do you mean that there’s a compiler optimization doing this transform? That’s impressive.

1 Like

Yes, the -O2 and -O3 compiler flags both result in this code.

1 Like

But Julia’s compiler doesn’t that, even with -O3? Do you know why not?

Not sure why Julia can’t do it. The optimization being done is a conversion of tail recursive calls with a loop. In gcc it is controlled by -foptimize-sibling-calls.

I think I once saw Keno say that it simply wasn’t implemented.
ChrisRackauckas also:

Yes, Julia doesn’t do tail call optimizations (TCO) which it could do with LLVM. Just not enabled yet. I find it funny when people try to say that Julia’s website benchmarks are cherrypicked to look good when the first example shows that it’s tracking an optimization which it’s missing…

1 Like

Interesting, that cuts down the number of recursive calls from OEIS A019274

ncalls_recursive(n) = n <= 1 ? 0 : 2 + ncalls_recursive(n-1) + ncalls_recursive(n-2)

to OEIS A000071

ncalls_unwound(n) = n <= 1 ? 0 : 1 + ncalls_unwound(n-1) + ncalls_unwound(n-2)

which is exactly half (5,942,430,144 vs 2,971,215,072 for n = 46).

My understanding is that developers want to concentrate on more fundamental features of the compiler. They admit that, in a sense, Julia is not yet an optimizing compiler. These optimizations will very likely be added later.

I have a hard time understanding this comment. The julia compiler is definitely an optimizing compiler, a lot of optimization happens in Julia itself and then LLVM adds a whole lot of future optimization.

Julia is an optimizing compiler: lots of optimization passes from LLVM are setup and applied. TCO isn’t. TCO only applies to very specific cases of recursion, and these cases can always be re-written as loop. While it would be cool to have, I would think that there’s usually a better way to spend one’s time than implementing it.

3 Likes