Different results for fib benchmark

I'm a new and enthusiastic user of Julia. However, in trying some benchmarks, I seem to get Fibonacci being orders of magnitude faster with C than Julia. If anyone could diagnose why, I'd be interested.

The C code I am using is

double fib(int n){
  if(n<=2)
    return(1.0);
  else
    return(fib(n-2)+fib(n-1));
}

main(int argc, char * argv[]){
  struct timeval t0;
  struct timeval t1;
  int num = atoi(argv[1]);
  gettimeofday(&t0, 0);
  double f = fib(num);
  gettimeofday(&t1, 0);
  printf("time in c (fib): %f \n", t1.tv_sec-t0.tv_sec + (t1.tv_usec-t0.tv_usec)/1000000.0);
  printf("f: %f \n", f);
}

While for Julia I tried 2 different definitions

function fib(n)
     if n <= 2
            1.0
     else
        fib(n-1)+fib(n-2);
     end
end
fib2(n) = n < 2 ? n : fib2(n-1) + fib2(n-2)

function mytest()
         gc()
     tic()
         fib(35)
         time = toc()
     println("time in julia (fib): ",time)

         gc()
     tic()
         fib2(35)
         time = toc()
     println("time in julia (fib2): ",time)
end

Now, I know that Julia is timing the print statement here, but I tried fixing that, and it makes no difference. I also tried adding types to the Julia function, again with no difference.

The results I get show Julia far behind:

time in c (fib): 0.005555 
time in julia (fib): 0.26958513259887695
time in julia (fib2): 0.2444448471069336

What gives? For details, this is on a MacBook Pro, with OS X 10.7.4, I used gcc -O2, and tried Julia with both a precompiled binary, and one I built myself.

[timholy]

Hi Justin,

Nice to hear from you again!

One obvious point is that your fib2 actually calls fib:

On Monday, October 01, 2012 10:05:06 PM justindomke wrote:

function fib(n)
if n <= 2
1.0
else
fib(n-1)+fib(n-2);
end
end
fib2(n) = n < 2 ? n : fib(n-1) + fib(n-2)

You want the rhs to be calling fib2, not fib. On my machine that makes a ~20%
difference.

While the Julia code gives similar timing on my machine as what your report,
on mine the C code is more than one order of magnitude slower than what you're
reporting (even when I remember to include -O2!). I can make my C code go 2x
faster by changing double->int, so there are no type conversions (notice it's
getting an int input and providing a double output, which is a bit strange for
a recursive function). Even with that change, it's a lot slower than yours. I
wonder what gives? Worth looking to see what the compiled binary looks like? I
wonder if your compiler is somehow "unwinding" some of the recursive calls, or
building a cache of prior results? (In other words, cheating.) On mine, if I
fix the double->int thing, objdump -d ctest.o gives me this for :

0000000000000000 :
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 53 push %rbx
5: 48 83 ec 18 sub $0x18,%rsp
9: 89 7d ec mov %edi,-0x14(%rbp)
c: 83 7d ec 02 cmpl $0x2,-0x14(%rbp)
10: 7f 07 jg 19 <fib+0x19>
12: b8 01 00 00 00 mov $0x1,%eax
17: eb 1e jmp 37 <fib+0x37>
19: 8b 45 ec mov -0x14(%rbp),%eax
1c: 83 e8 02 sub $0x2,%eax
1f: 89 c7 mov %eax,%edi
21: e8 00 00 00 00 callq 26 <fib+0x26>
26: 89 c3 mov %eax,%ebx
28: 8b 45 ec mov -0x14(%rbp),%eax
2b: 83 e8 01 sub $0x1,%eax
2e: 89 c7 mov %eax,%edi
30: e8 00 00 00 00 callq 35 <fib+0x35>
35: 01 d8 add %ebx,%eax
37: 48 83 c4 18 add $0x18,%rsp
3b: 5b pop %rbx
3c: 5d pop %rbp
3d: c3 retq

I don't really know how to interpret this, but I do notice the two "callq"
statements which makes me guess mine, at least, is not cheating.

--Tim

function mytest()
gc()
tic()
fib(35)
time = toc()
println("time in julia (fib): ",time)

     gc()

tic()
fib2(35)
time = toc()
println("time in julia (fib2): ",time)
end

Now, I know that Julia is timing the print statement here, but I tried
fixing that, and it makes no difference.  I also tried adding types to the
Julia function, again with no difference.

The results I get show Julia far behind:
```c
time in c (fib): 0.005555
time in julia (fib): 0.26958513259887695
time in julia (fib2): 0.2521979808807373

What gives? For details, this is on a MacBook Pro, with OS X 10.7.4, I used
gcc -O2, and tried Julia with both a precompiled binary, and one I built
myself.

---

Reply to this email directly or view it on GitHub:
#1325

[StefanKarpinski]

Your Fibonacci algorithm is a bit off: fib(2) ≠ 1 — the comparison with 2 should be strict. Also, doing the computation with floating-point arithmetic in C is kind of bizarre. With -O0 I get similar timings in Julia and C, with -O1 C becomes twice as fast, and with -O2 it is, as you note, an order of magnitude faster. Not sure what the C compiler is doing here, but it's something very clever and opaque. The Julia compiler doesn't generally do anything all that clever (yet), it mostly just does what you ask it to with obvious transparent optimizations.

Heynow, it isn't crazy to say that fib(2)==1. (It seems natural in a language where indices start at 0.)

Thanks for pointing out the error in fib2, Tim. I fixed it above, and redid the timing. Changing things to be ints rather than doubles doesn't make a big difference for me. I used doubles because I've run this for some very large values and wanted to avoid overflow.

I though that perhaps gcc was clever enough to silently transform the recursive algorithm into a dynamic programming version? (Which would be amazing.) However, taking some timings indicates this isn't the case:

n    time
35  0.005934 
36  0.008927 
37  0.013821 
38  0.021166

I'll see if I can get the gcc assembly in case someone can figure out what's going on. Could it possibly be pre-calculating the values for small n?

It still isn't clear to me why http://julialang.org/ shows Julia as being within a factor of 2. Is this because of using a different system, or a different compiler?

[StefanKarpinski]

It still isn't clear to me why http://julialang.org/ shows Julia as being within a factor of 2. Is this because of using a different system, or a different compiler?

The current timings are done with clang (which is different than but not unilaterally better or worse than gcc). What's going on with the fib timing is that with -O1 or greater the C compiler optimizes the entire benchmark away to a constant which causes the timing to become zero and since we take the smallest positive timing from all executions at all optimization levels, these timings are not used. With -O0 the C compiler does a normal recursive computation without any bizarre shenanigans and that's the timing that julia is within 2x of. Perhaps we should change the way this benchmark is measured, but I'm not certain.

Yep, C will optimize to a constant if it knows the constant at compile-time. That's why I read the number 35 in from the command line above, which prevents this.

BTW, I get about .02s for clang with -O2. (Compared with .004s for gcc and .24s with Julia.)

[StefanKarpinski]

Yeah, that's one of the benchmarks that gcc beats clang on. Like I said, it's a mixed bag which one wins across all the benchmarks.

I guess my point was more that .24/.02 = 12, not 1.97. So, yes, I'd definitely endorse changing the benchmarks on julialang.org so that you don't spuriously rule out the use of optimization in cases like this. For this one, reading the function argument (e.g. 35) in from the command line or a file is a good way to defeat the c compiler optimizing away the entire function call.

(Also, just so I don't sound so negative: I think that Julia is a great language, which I'm planning to use for a new project I'll start soon.)

[ViralBShah]

I am not sure how you are getting such a major performance difference between clang and julia. I ran the benchmark on my mac (2.4GHz Core i5), and I see that C is at 0.07, whereas julia is at 0.18. It's a bit strange that clang produces faster code and julia produces slower code on your machine compared to mine!

In any case, I think we all need to collectively work towards a better and more realistic performance suite - which I believe you did start on in your blog post. I think it is ok if julia is between 2 and 12 times slower than fib, but it wouldn't be ok if julia was 12 times slower than C on real codes that people use.

[staticfloat]

On my machine (2.8 GHz Core 2 Duo macbook pro) the timing is even worse:

[@time fib2(35) for x = 1:10]                                            
elapsed time: 0.41972899436950684 seconds
elapsed time: 0.4220139980316162 seconds
elapsed time: 0.44595789909362793 seconds
elapsed time: 0.4203450679779053 seconds
elapsed time: 0.42096400260925293 seconds
elapsed time: 0.42056703567504883 seconds
elapsed time: 0.4207420349121094 seconds
elapsed time: 0.4235351085662842 seconds
elapsed time: 0.4177379608154297 seconds
elapsed time: 0.420849084854126 seconds

$ gcc -o test -O2 test.c
$ ./test 35
time in c (fib): 0.014804 
f: 9227465.000000 

My disassembled output, which also shows a few callq's back to the address of fib:

_fib:
0000000100000d90        pushq   %rbp
0000000100000d91        movq    %rsp,%rbp
0000000100000d94        pushq   %r15
0000000100000d96        pushq   %r14
0000000100000d98        pushq   %rbx
0000000100000d99        subq    $0x08,%rsp
0000000100000d9d        cmpl    $0x03,%edi
0000000100000da0        jl      0x100000e13
0000000100000da2        movl    %edi,%ebx
0000000100000da4        leal    0xfe(%rbx),%r14d
0000000100000da8        cmpl    $0x02,%r14d
0000000100000dac        jg      0x100000db5
0000000100000dae        movl    $0x00000001,%eax
0000000100000db3        jmp     0x100000ddd
0000000100000db5        leal    0xfc(%rbx),%edi
0000000100000db8        callq   0x100000d90
0000000100000dbd        leal    0xfd(%rbx),%ecx
0000000100000dc0        cmpl    $0x02,%ecx
0000000100000dc3        movl    %eax,%r15d
0000000100000dc6        jg      0x100000dcf
0000000100000dc8        movl    $0x00000001,%eax
0000000100000dcd        jmp     0x100000dda
0000000100000dcf        leal    0xfb(%rbx),%edi
0000000100000dd2        callq   0x100000d90
0000000100000dd7        addl    %r15d,%eax
0000000100000dda        addl    %r15d,%eax
0000000100000ddd        movl    %eax,%r15d
0000000100000de0        leal    0xff(%rbx),%eax
0000000100000de3        cmpl    $0x02,%eax
0000000100000de6        jg      0x100000def
0000000100000de8        movl    $0x00000001,%eax
0000000100000ded        jmp     0x100000e05
0000000100000def        movl    %ebx,%edi
0000000100000df1        addl    $0xfd,%edi
0000000100000df4        callq   0x100000d90
0000000100000df9        movl    %eax,%ebx
0000000100000dfb        movl    %r14d,%edi
0000000100000dfe        callq   0x100000d90
0000000100000e03        addl    %ebx,%eax
0000000100000e05        addl    %r15d,%eax
0000000100000e08        addq    $0x08,%rsp
0000000100000e0c        popq    %rbx
0000000100000e0d        popq    %r14
0000000100000e0f        popq    %r15
0000000100000e11        popq    %rbp
0000000100000e12        ret
0000000100000e13        movl    $0x00000001,%eax
0000000100000e18        jmp     0x100000e08
0000000100000e1a        nopw    0x00(%rax,%rax)

[StefanKarpinski]

I'm using these versions of the code:

fib(n) = n <= 2 ? n : fib(n-1) + fib(n-2)

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

long fib(long n) {
    return n <= 2 ? n : fib(n-1) + fib(n-2);
}

int main(int argc, char * argv[]) {
    struct timeval t0, t1;
    long n = atoll(argv[1]);
    gettimeofday(&t0, 0);
    long f = fib(n);
    gettimeofday(&t1, 0);
    printf("time in c (fib): %f \n",
           t1.tv_sec-t0.tv_sec + (t1.tv_usec-t0.tv_usec)/1000000.0);
    printf("fib(%ld): %ld\n", n, f);
    return 0;
}

Note that these versions both do integer computations using whatever your native integer size is (32 or 64). The other versions above are not comparing apples to apples so it is hard to draw any conclusions.

I get the following timings:

julia> @time fib(35)
elapsed time: 0.29952287673950195 seconds
14930352

$ clang -O2 tmp/fib.c -o tmp/fib
$ tmp/fib 35
time in c (fib): 0.100359 
fib(35): 14930352

That makes Julia about 3x slower than C on this particular test. While that's not exactly what the fib benchmark on http://julialang.org/ has, it's in the same ballpark. Can you try timing these versions using clang -O2 and see if your results are wildly different?

[staticfloat]

$ gcc -O2 -o test-gcc test.c && ./test-gcc 35
time in c (fib): 0.046282 
fib(35): 14930352

$ clang -O2 -o test-clang test.c && ./test-clang 35
time in c (fib): 0.087051 
fib(35): 14930352

julia> fib(n) = n <= 2 ? n : fib(n-1) + fib(n-2)

julia> @time fib(35)
elapsed time: 0.2999460697174072 seconds
14930352

julia> @time fib(35)
elapsed time: 0.26885294914245605 seconds
14930352

julia> @time fib(35)
elapsed time: 0.26906800270080566 seconds
14930352

This now shows Julia as 3-6x slower than C, depending on whether you use clang or gcc-llvm as your backend compiler. This is much closer than what I originally got, interesting that changing that strict inequality to an inclusive inequality in Julia shaved off more than a tenth of a second. I suppose with the range of performance given by C here, we really need to either stick to a single compiler for all tests, compare multiple compilers, or take the best performance from the range of compilers to compare against.

[StefanKarpinski]

Spending any more time screwing around with trivial benchmarks like fib is silly. Obviously we take performance seriously, but mileage may vary a lot by both compiler and architecture, and comparing with every single C compiler in the world is a waste of time. I'm sure ICC is even faster than both clang and gcc.

Note that Fortran is really the thing to beat here. On our benchmarks, Fortran is 3.5x faster than C and 7x faster than Julia. Which actually just makes me suspicious that the Fortran code may not be doing 64-bit integer arithmetic. I don't really know enough Fortran to tell though.