# Simple recursive Fibonaci example. How to make it faster?

**URL:** <https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369>\
**Category:** Performance\
**Created:** [December 17, 2019, 2:59am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369 "2019-12-17T02:59:46Z")\
**Posts on this page:** 20\
**Page:** 2

<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:** [December 17, 2019, 10:13pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/21 "2019-12-17T22:13:06Z")

</div>

You may be familiar with writing functions like this to be generic:

```julia
function mysume(v::AbstractVector)
    s = zero(eltype(V))
    @simd for x in v
        s += x
    end
    s
end

```

This function should be type stable for all reasonable definitions of `+`. Eg:

```julia
xf = rand(100);
@code_warntype mysume(xf)
xi = rand(1:100, 100);
@code_warntype mysume(xi)
using StaticArrays
xm = [@SMatrix randn(2,2) for _ in 1:100];
@code_warntype mysume(xm)

```

You can also write the function like this:

```julia
function mysumw(v::AbstractVector{T}) where {T}
    s = zero(T)
    @simd for x in v
        s += x
    end
    s
end

```

and you’ll get the same result: it uses `T`, the element type parameter, to make a zero of the appropriate type.

Julia compiles a specialized version for each element type, one for `T === Float64`, another for `T === Int`, and another for `T === SMatrix{2,2,Float64,4}`.

What if instead of using a type parameter `T` to give us an element type and let us make a zero of the correct type, we used an actual value as a type parameter?

`AbstractArray`s sort of all do this, giving us their number of dimensions. Check this out:

```julia
julia> twice_ndim(x) = 2length(size(x))
twice_ndim (generic function with 1 method)

julia> @code_typed twice_ndim(rand(3))
CodeInfo(
1 ─ Base.arraysize(x, 1)::Int64
└── return 2
) => Int64

julia> @code_typed twice_ndim(rand(3,3))
CodeInfo(
1 ─ Base.arraysize(x, 1)::Int64
│ Base.arraysize(x, 2)::Int64
└── return 4
) => Int64

julia> @code_typed twice_ndim(rand(3,3,3))
CodeInfo(
1 ─ Base.arraysize(x, 1)::Int64
│ Base.arraysize(x, 2)::Int64
│ Base.arraysize(x, 3)::Int64
└── return 6
) => Int64

```

The code for `twice_ndim` doesn’t calculate anything (no `2*`): it just returns the answer!

Tamas\_Papp was taking advantage of this, by using a Val type. You can make your own via:

```julia
struct MyVal{T} end

```

the trick is instead of using `T` to describe the struct, like how an `Array{Float64,2}`'s type parameters say it (a) holds `Float64` elements and (b) has `2` dimensions, `MyVal`’s `T` can be anything.

But, just like the `Array{T,N}`'s `N` let the `twice_ndim` function compile into simply spitting out the answer:

```julia
julia> @code_typed fibval(Val(46)) 
CodeInfo(
1 ─ goto #3 if not false
2 ─ nothing::Nothing
3 ┄ return 2971215073
) => Int64

julia> @btime fibval(Val(46)) 
  0.001 ns (0 allocations: 0 bytes)
2971215073

```

`fibval` here isn’t doing anything except returning the answer.

The first run that compiled was also very fast. `fib` is slow, because normally `fib(N)` requires `O(2^N)` work. However, with Tamas\_Papp’s trick – which is equivalent to memoization – requires just `O(N)` work, because each `fib(::Val{N})` only gets calculated once, and the result saved into a specialized method.

Compiling takes vastly longer than simple arithmetic. Dynamic dispatches, if the types of everything couldn’t be found at compile time, also take much longer (although a dynamic dispatch takes much less time than compilation).  
It will normally be better to let the compiler create a function optimized to do arithmetic on values quickly, than compile a version of the function specific to those values. The exceptions are things like `StaticArrays`, where some of the values – eg, the size of the arrays – can be used to help the compiler compute on the values of the array more quickly. Other types would include things like special matrix properties, eg, is a matrix positive definite, or maybe lower triangular?

When it comes to values like data (eg, contents of the arrays), it would almost certainly be better to NOT use these values as type parameters. Just write a normal function and assign the results to a variable, or maybe use a memoization library.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [December 18, 2019, 12:20am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/22 "2019-12-18T00:20:54Z")

</div>

> [@StefanKarpinski](#):
>
> Using function calls to express finite automata.

This is a natural generalization of the function barrier + mutate-or-widen approach used in functions like `collect`. So, I think it might be natural to have it in Julia: [Tail-call optimization and function-barrier -based accumulation in loops - #8 by tkf](https://discourse.julialang.org/t/tail-call-optimization-and-function-barrier-based-accumulation-in-loops/25831/8)

---

<div class="post-metadata">

**Author:** ![cshen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cshen/32/217287_2.png) [@cshen](https://discourse.julialang.org/u/cshen)\
**Post date:** [December 18, 2019, 12:38am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/23 "2019-12-18T00:38:44Z")

</div>

Going back to the multi-threaded version of the algorithm that Mason posted, i’ve been playing with it a bit. I noticed that if running `@code_warntype` on `fib` shows that `fetch(t)` introduces `::Any` type into the calculations.

I tried to skim the docs looking for information regarding it but could not find anything notable. Maybe making it type stable would improve the performance a bit (Is it even possible?).  
Although I’m not sure how to introduce type stability on fetch, `Task` type is not convertible to `::Int`.

---

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [December 18, 2019, 12:58am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/24 "2019-12-18T00:58:12Z")

</div>

I have also tried a simpler version, without splitting for n\>23.

```julia
function fib(n::Int64)
  if n <= 1 return 1 end
      t = Threads.@spawn fib(n - 2)
  return return fib(n - 1) + fetch(t)
end

```

And when you try

> fib(46)

it consumes all my computer memory and finally crashes.

---

<div class="post-metadata">

**Author:** ![cshen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cshen/32/217287_2.png) [@cshen](https://discourse.julialang.org/u/cshen)\
**Post date:** [December 18, 2019, 1:11am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/25 "2019-12-18T01:11:42Z")

</div>

The splitting at 23, is to avoid spending more time setting up the `@spawn` overhead (multi-threading is not for free) than doing the calculations directly (if you check out Mason stack overflow answer, he goes into much more detail).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 18, 2019, 1:33pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/26 "2019-12-18T13:33:50Z")

</div>

If you work out how many tasks you spawned, that makes sense.

---

<div class="post-metadata">

**Author:** ![mwolff](https://avatars.discourse-cdn.com/v4/letter/m/c2a13f/32.png) [@mwolff](https://discourse.julialang.org/u/mwolff)\
**Post date:** [January 12, 2020, 12:43pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/27 "2020-01-12T12:43:43Z")

</div>

Hello,

what could I do to get the program up and running? I only get error messages like this.

 ![Bildschirmfoto vom 2020-01-11 21-36-08](https://global.discourse-cdn.com/julialang/original/3X/9/5/95d4a7754efff10eb65020236f4b813fa6eac912.png)

 ![Bildschirmfoto vom 2020-01-12 12-59-19](https://global.discourse-cdn.com/julialang/original/3X/0/2/02beecba17e4f5cc8cd9b463bfbbd94eab7acb88.png)

march=pentium4 ? i don’t have this shit old feet warmer from 2000 😷 🙂

the module looks like this

```julia
module Fib

fib(n, a=0, b=1) = n > 0 ? fib(n-1, b, a+b) : a

Base.@ccallable function julia_main(ARGS::Vector{String})::Cint
    @show fib(10)
    return 0
end

end # module

```

---

<div class="post-metadata">

**Author:** ![ufechner7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ufechner7/32/51363_2.png) [@ufechner7](https://discourse.julialang.org/u/ufechner7)\
**Post date:** [January 12, 2020, 4:39pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/28 "2020-01-12T16:39:43Z")

</div>

Why do you make the function ccallable? Which goal do you want to achieve?

---

<div class="post-metadata">

**Author:** ![mwolff](https://avatars.discourse-cdn.com/v4/letter/m/c2a13f/32.png) [@mwolff](https://discourse.julialang.org/u/mwolff)\
**Post date:** [January 12, 2020, 6:33pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/29 "2020-01-12T18:33:36Z")

</div>

For creating binary files with PackageCompilerX. There is a post from mason you see this…

---

<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:** [January 28, 2020, 5:01pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/30 "2020-01-28T17:01:39Z")

</div>

> [@mwolff](#):
>
> what could I do to get the program up and running? I only get error messages like this.

As reference, tihs was a bug with PackageCompilerX on 32-bit Julias which has now been fixed (requires gcc 7 though).

---

<div class="post-metadata">

**Author:** ![mwolff](https://avatars.discourse-cdn.com/v4/letter/m/c2a13f/32.png) [@mwolff](https://discourse.julialang.org/u/mwolff)\
**Post date:** [January 28, 2020, 5:31pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/31 "2020-01-28T17:31:39Z")

</div>

ok thanks again for your help. gcc is now linked to version 7.4, before it was 5.4. Now it runs, but unfortunately it takes a long time to create. My ThinkPad is a bit too old for this 😅

best regards  
Michael

---

<div class="post-metadata">

**Author:** ![billtubbs](https://avatars.discourse-cdn.com/v4/letter/b/67e7ee/32.png) [@billtubbs](https://discourse.julialang.org/u/billtubbs)\
**Post date:** [June 21, 2020, 1:57am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/32 "2020-06-21T01:57:56Z")

</div>

Is there a reason they use a recursive Fibonacci algorithm for the benchmark? It’s a very inefficient way to compute it (I compared the Python Fib code used in the benchmark test with a non-recursive method and found it was 2200 times slower). Specifically to test speed on recursive tasks maybe?

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [June 21, 2020, 2:06am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/33 "2020-06-21T02:06:15Z")

</div>

Yes. The point of the benchmark is not to optimize the Fibonacci algorithm, it’s to test performance of recursion.

---

<div class="post-metadata">

**Author:** ![billtubbs](https://avatars.discourse-cdn.com/v4/letter/b/67e7ee/32.png) [@billtubbs](https://discourse.julialang.org/u/billtubbs)\
**Post date:** [June 21, 2020, 2:07am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/34 "2020-06-21T02:07:02Z")

</div>

That makes sense. Thanks.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 21, 2020, 3:08am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/35 "2020-06-21T03:08:01Z")

</div>

> [@John\_Gibson](#):
>
> . The point of the benchmark is not to optimize the Fibonacci algorithm, it’s to test performance of recursion.

Feels like Ackerman’s function would be better suited and cause less questions like this.

---

<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:** [June 22, 2020, 2:34am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/36 "2020-06-22T02:34:48Z")

</div>

```julia
function A(m,n)
    if iszero(m)
        n + one(n)
    elseif iszero(n)
        A(m - one(m), one(n))
    else
        A(m - one(m), A(m, n - one(n)))
    end
end

ccode = """
long A(long m, long n){
    long x;
    if (m == 0) {
        x = n + 1;
    } else if (n == 0) {
        x = A(m - 1, 1);
    } else {
        x = A(m - 1, A(m, n - 1));
    }
    return x;
}

""";
open("ackerman.c", "w") do io
    write(io, ccode)
end
run(`gcc -O3 -march=native -shared -fPIC ackerman.c -o libackerman.so`)
const AckerC = joinpath(pwd(), "libackerman.so")
Ac(m::Clong, n::Clong) = @ccall AckerC.A(m::Clong, n::Clong)::Clong

```

This yields:

```julia
julia> @time A(3,3)
  0.000005 seconds
61

julia> @time Ac(3,3)
  0.000003 seconds
61

julia> @time A(4, 1)
  4.537859 seconds
65533

julia> @time Ac(4, 1)
  1.829240 seconds
65533

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 22, 2020, 6:01am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/37 "2020-06-22T06:01:42Z")

</div>

> [@Elrod](#):
>
> ```julia
> julia> @time A(3,3)
> 0.000005 seconds
> 61
> 
> julia> @time Ac(3,3)
> 0.000003 seconds
> 61
> 
> julia> @time A(4, 1)
> 4.537859 seconds
> 65533
> 
> julia> @time Ac(4, 1)
> 1.829240 seconds
> 65533
> 
> ```

Wow

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 22, 2020, 9:23am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/38 "2020-06-22T09:23:16Z")

</div>

The Ackermann function is interesting in that it actually pays off to compile it separately for each value of `m`, even when compile time is accounted for.

```julia
using StaticNumbers
function A(m,n)
    if iszero(m)
        n + one(n)
    elseif iszero(n)
        A(@stat(m - one(m)), one(n))
    else
        A(@stat(m - one(m)), A(m, n - one(n)))
    end
end
@time A(static(4), 1)

```

This yields more than a 5x speedup on my system.

---

<div class="post-metadata">

**Author:** ![braamvandyk](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/braamvandyk/32/5086_2.png) [@braamvandyk](https://discourse.julialang.org/u/braamvandyk)\
**Post date:** [June 27, 2020, 2:56pm UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/39 "2020-06-27T14:56:24Z")

</div>

Running this function on my PC (Windows 10, Julia 1.4.2) gives a stack overflow for A(4,1). ☹

---

<div class="post-metadata">

**Author:** ![Fourier](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fourier/32/38176_2.png) [@Fourier](https://discourse.julialang.org/u/Fourier)\
**Post date:** [December 5, 2024, 11:15am UTC](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369/40 "2024-12-05T11:15:39Z")

</div>

The updated version of this is

```julia
using Pkg
Pkg.generate("Fib")

```

_edit the files_

```julia
 using PackageCompiler
create_app("Fib", "FibCompiled")

```

[Previous page](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369.md?page=1)

[Next page](https://discourse.julialang.org/t/simple-recursive-fibonaci-example-how-to-make-it-faster/32369.md?page=3)
