Fibonacci and performance

Fri Apr 27 10:54:00 GMT 2001

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