Fibonacci and performance

Fri Apr 27 07:15:00 GMT 2001

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;
}