Recursive Fibonacci Benchmark using top languages on Github

General Usage Performance
1

Dear all, this popped up in the hacker news. It uses julia 0.6.3 version.
https://github.com/drujensen/fib/blob/master/README.md

2

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
3

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
4 Likes
4

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

1 Like
5

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

1 Like
6

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

7

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.

8

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
9

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

10

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.

11

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.

12

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