RE: Fibonacci and performance

["Boehm, Hans" <hans_boehm at hp dot com>]

A lot of the overhead here is again related to dynamic libraries.  On a
300MHz PII,

C++, statically linked: 12382 ms
C++, dyn. linked: 12451 ms
Java, statically linked: 18055 ms
Java, dyn. linked: 23269 ms

Perhaps it makes sense to inline the class initialization test as

static volatile bool I_already_initialized_this_class_from_this_file;
	/* The volatile declaration should suffice to make this thread-safe
on X86 and IA64.	*/
	/* The current code already looks dubious to me for something like
Alpha.			*/

if (!I_already_initialized_this_class_from_this_file) {
    _Jv_InitClass(...);	// Checks whether someone else initialized it.
    I_already_initialized_this_class_from_this_file = true;
}

That way, even with dynamic libraries, the static variable should end up in
a short data segment, and the fast path should consist of something like a
ld instruction with an offset from the gp, followed by a test and
conditional branch.  (On IA64, you'd use an ld.acq, but I suspect that
really corrects a bug with the current approach.  I don't think the current
code guarantees that if you see the initialization state to be
JV_STATE_DONE, you will actually see all initializations.  I suspect worse
problems along these lines on Alpha.)

Hans

> -----Original Message-----
> From: Tom Tromey [mailto:tromey@redhat.com]
> Sent: Friday, April 27, 2001 7:26 AM
> To: Java Discuss List
> Subject: Fibonacci and performance
> 
> 
> 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;
> }
>