# Recursive Fibonacci Benchmark using top languages on Github

**URL:** <https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602>\
**Category:** Performance\
**Tags:** recursion\
**Created:** [September 28, 2018, 10:06am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602 "2018-09-28T10:06:34Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tero\_Frondelius](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tero_frondelius/32/7629_2.png) [@Tero\_Frondelius](https://discourse.julialang.org/u/Tero_Frondelius)\
**Post date:** [September 28, 2018, 10:06am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/1 "2018-09-28T10:06:34Z")

</div>

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](https://github.com/drujensen/fib/blob/master/README.md)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 28, 2018, 10:48am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/2 "2018-09-28T10:48:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [September 28, 2018, 2:07pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/3 "2018-09-28T14:07:57Z")

</div>

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:

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

```

The C++ version generates this:

```julia
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
julia> @time fib(46)
  9.383770 seconds (5 allocations: 176 bytes)
2971215073

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

```

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [September 28, 2018, 2:14pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/4 "2018-09-28T14:14:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [September 28, 2018, 2:19pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/5 "2018-09-28T14:19:32Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2018, 3:27pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/6 "2018-09-28T15:27:28Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [September 28, 2018, 9:38pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/7 "2018-09-28T21:38:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [September 28, 2018, 10:09pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/8 "2018-09-28T22:09:25Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![simonbyrne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simonbyrne/32/19_2.png) [@simonbyrne](https://discourse.julialang.org/u/simonbyrne)\
**Post date:** [September 28, 2018, 10:58pm UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/9 "2018-09-28T22:58:20Z")

</div>

Interesting, that cuts down the number of recursive calls from [OEIS A019274](https://oeis.org/A019274)

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

```

to [OEIS A000071](https://oeis.org/A000071)

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

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [September 29, 2018, 12:44am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/10 "2018-09-29T00:44:47Z")

</div>

> [@DNF](#):
>
> But Julia’s compiler doesn’t that, even with `-O3` ? Do you know why not?

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.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [September 29, 2018, 1:12am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/11 "2018-09-29T01:12:23Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [September 29, 2018, 1:38am UTC](https://discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602/12 "2018-09-29T01:38:15Z")

</div>

> [@jlapeyre](#):
>
> 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.

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.