Stack performance in programming languages
Question: Just for fun, I tried to compare the stack performance of a couple of
programming languages calculating the Fibonacci series using the naive
recursive algorithm. The code is mainly the same in all languages, i'll post a
java version:

    
    
    public class Fib {
     public static int fib(int n) {
      if (n < 2) return 1;
      return fib(n-1) + fib(n-2);
     }
    
     public static void main(String[] args) {
      System.out.println(fib(Integer.valueOf(args[0])));
     }
    }
    

Ok so the point is that using this algorithm with input 40 I got these
timings:

    
    
    C: 2.796s
    Ocaml: 2.372s
    Python: 106.407s
    Java: 1.336s
    C#(mono): 2.956s
    

They are taken in a Ubuntu 10.04 box using the versions of each language
available in the official repositories, on a dual core intel machine.

I know that functional languages like ocaml have the slowdown that comes from
treating functions as first order citizens and have no problem to explain
CPython's running time because of the fact that it's the only interpreted
language in this test, but I was impressed by the java running time which is
half of the c for the same algorithm! Would you attribute this to the JIT
compilation?

How would you explain these results?

EDIT: thank you for the interesting replies! I recognize that this is not a
proper benchmark (never said it was :P) and maybe I can make a better one and
post it to you next time, in the light of what we've discussed :)

EDIT 2: I updated the runtime of the ocaml implementation, using the
optimizing compiler ocamlopt. Also I published the testbed at
<https://github.com/hoheinzollern/fib-test>. Feel free to make additions to it
if you want :)


Answer: You might want to crank up the optimisation level of your C compiler. With
`gcc -O3`, that makes a big difference, a drop from 2.015 seconds to 0.766
seconds, a reduction of about 62%.

Beyond that, you need to ensure you've tested correctly. You should run each
program ten times, remove the outliers (fastest and slowest), then average the
other eight.

In addition, make sure you're measuring CPU time rather than clock time.

Anything less than that, I would not consider a decent statistical analysis
and it may well be subject to noise, rendering your results useless.

For what it's worth, those C timings above were for seven runs with the
outliers taken out before averaging.

* * *

In fact, this question shows how important algorithm selection is when aiming
for high performance. Although recursive solutions are usually elegant, this
one suffers from the fault that you duplicate a _lot_ of calculations. The
iterative version:

    
    
    int fib(unsigned int n) {
        int t, a, b;
        if (n < 2) return 1;
        a = b = 1;
        while (n-- >= 2) {
            t = a + b;
            a = b;
            b = t;
        }
        return b;
    }
    

further drops the time taken, from 0.766 seconds to 0.078 seconds, a further
reduction of 89% and a _whopping_ reduction of 96% from the original code.

* * *

And, as a final attempt, you should try out the following, which combines a
lookup table with calculations beyond a certain point:

    
    
    static int fib(unsigned int n) {
        static int lookup[] = {
            1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
            610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
            46368, 75025, 121393, 196418, 317811, 514229, 832040,
            1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
            24157817, 39088169, 63245986, 102334155, 165580141 };
        int t, a, b;
    
        if (n < sizeof(lookup)/sizeof(*lookup))
            return lookup[n];
        a = lookup[sizeof(lookup)/sizeof(*lookup)-2];
        b = lookup[sizeof(lookup)/sizeof(*lookup)-1];
        while (n-- >= sizeof(lookup)/sizeof(*lookup)) {
            t = a + b;
            a = b;
            b = t;
        }
    
        return b;
    }
    

That reduces the time yet again but I suspect we're hitting the point of
diminishing returns here.

