Julia: Performance gap on a sequential fibonacci func

Created on 28 Sep 2016 · 5Comments · Source: JuliaLang/julia

Following the blog post https://www.ibm.com/developerworks/community/blogs/jfp/entry/Python_Meets_Julia_Micro_Performance?lang=en
I have tried Python/Cython, C# and Julia implementations of sequential fibonacci calculation (macOS, Julia 0.5). Both Python/Cython and C# versions showed around 80 ns execution time, while Julia consistently showed 130 ns. From where this gap stems, is this an issue?

Julia code:

function fib(n::Int64)::Int64
    if n < 2
        return n
    end
    a::Int64 = 1
    b::Int64 = 0
    for i in 1:n-1
        c = a + b
        b = a
        a = c
    end
    a
end

tic()
n = 100000000
for i in 1:n
    fib(20)
end
t = toq()
"$(t * 1000_000_000 / n) ns"

Equivalent, in my understanding, C# code:

``` C#
public static Int64 Fib(Int64 n) {
if (n < 2) {
return n;
}
Int64 a = 1;
Int64 b = 0;
for (Int64 i = 0; i < n - 1; i++) {
Int64 c = a + b;
b = a;
a = c;
}
return a;
}

var sw = System.Diagnostics.Stopwatch.StartNew();
int n = 100000000;
Int64 k;
sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
k = Fib(20);
}
sw.Stop();
WriteLine(sw.ElapsedMilliseconds * 1000000 / n);
```

Source

wgreenr

All 5 comments

Don't use global variable in the benchmark, in particular, the n.

yuyichao on 28 Sep 2016

(Or rather, don't use non-const global variable) Here's the speed up on my machine.

julia> n = 100000000
100000000

julia> const m = 100000000
100000000

julia> @time for i in 1:m
           fib(20)
       end
  1.585658 seconds

julia> @time for i in 1:n
           fib(20)
       end
 11.383704 seconds (300.00 M allocations: 5.960 GB, 6.48% gc time)

yuyichao on 28 Sep 2016

👍1

The manual's performance tips section might be helpful. Best!

Sacha0 on 28 Sep 2016

👍1

Note that there is also a Benchmark library to make this stuff easier:

Pkg.add("BenchmarkTools")
using BenchmarkTools

and then

julia> @benchmark fib(20)
BenchmarkTools.Trial: 
  samples:          10000
  evals/sample:     999
  time tolerance:   5.00%
  memory tolerance: 1.00%
  memory estimate:  0.00 bytes
  allocs estimate:  0
  minimum time:     10.00 ns (0.00% GC)
  median time:      10.00 ns (0.00% GC)
  mean time:        10.67 ns (0.00% GC)
  maximum time:     63.00 ns (0.00% GC)