Simple recursive Fibonaci example. How to make it faster?

General Usage Performance
16

Here’s how you can semi-manually get the tail call elimination.

julia> fib(n, a=0, b=1) = n > 0 ? fib(n-1, b, a+b) : a
fib (generic function with 3 methods)

julia> @btime fib($46)
  64.136 ns (0 allocations: 0 bytes)
1836311903

and the version compiled to an app:

[mason@mason-pc ~]$ cat Fib/src/Fib.jl
module Fib

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

Base.@ccallable function julia_main()::Cint
    @show fib(46)
    return 0
end

end # module

[mason@mason-pc ~]$ julia -e 'using PackageCompilerX; create_app("Fib", "FibCompiled")'
  Updating registry at `~/.julia/registries/General`
  Updating git-repo `https://github.com/JuliaRegistries/General.git`
 Resolving package versions...
  Updating `~/Fib/Project.toml`
 [no changes]
[ Info: PackageCompilerX: creating base system image (incremental=false)...
[ Info: PackageCompilerX: creating system image object file, this might take a while...
[ Info: PackageCompilerX: creating system image object file, this might take a while...

[mason@mason-pc ~]$ time FibCompiled/bin/Fib
fib(46) = 1836311903

real    0m0.330s
user    0m0.384s
sys     0m0.505s

but again, this is cheating since it’s not the algorithm asked for, even if other languages might have done something similar under the hood.

3 Likes