Fibonacci and performance

[Tom Tromey <tromey at redhat dot com>]

Consider this simple program, which I got from some comp.lang.java
newsgroup:

    public class Fib
    {
	    public static void main(String[] args)
	    {
		    final int n = 40;
		    long start = System.currentTimeMillis();
		    System.out.println(fib(n));
		    long end = System.currentTimeMillis();
		    System.out.println("Fibonacci: n = " + n + " took "+ (end -
    start) + " ms");

	    }

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

	}
    }

The equivalent C++ program is appended.

If I compile both with -O2, the C++ program is much faster:

    creche. g++ -O2 -o Fx fib.cc  -Wl,-rpath,/x1/gcc3/install/lib
    creche. ./Fx
    102334155
    Fibonacci: n = 40 took 13329 ms
    creche. gcj -O2 --main=Fib -o Fj -Wl,-rpath,/x1/gcc3/install/lib Fib.java 
    creche. ./Fj
    102334155
    Fibonacci: n = 40 took 36161 ms

Looking at the generated assembly, the only real difference I see is
the call to _Jv_InitClass in Fib.fib().  In this particular case we're
paying a pretty big penalty.

I wonder if inlining the "already initialized" check from
_Jv_InitClass would help or hurt (due to increased code size).

Tom

#include <iostream.h>
#include <sys/time.h>
#include <sys/select.h>
#include <unistd.h>

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

}

long millis ()
{
  struct timeval tv;
  gettimeofday (&tv, NULL);
  return (long) tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

int main( void )
{
        const int n = 40;
	long start  = millis();
	cout << fib(n);
	long endt = millis();
	cout <<"\nFibonacci: n = " << n << " took "<< endt - start << " ms\n";
	return 0;
}