Computing Fibonacci numbers as a performance testsuite

[Alex Vinokur]

An algorithm which computes very long Fibonacci numbers

http://groups.google.com/groups?selm=bnni5p%2412i47o%241%40ID-79865.news.uni-berlin.de

was used as a performance testsuite
to compare speed of the code produced by various compilers.


=============== =============== =============== ==============
Windows 2000 Professional Ver 5.0 Build 2195 Service Pack 2
Intel(R) Celeron(R) CPU 1.70 GHz
GNU time 1.7 (to get the real time used)
=============== =============== =============== ==============


A. Real and processor time used to compute Fibonacci[10000] and Fibonacci[25000].

Here are summary results.

|============== =============== =============== =============
| | Opt | Fib-10000 | Fib-25000 |
| Compiler | Lev |-------------|-------------|
| | | Real : CPU | Real : CPU |
|============== =============== =============== ============|
| GNU gcc compiler |
|--------------------------------------------------------|
| g++ 3.3.1 (Cygwin) | No | 0.45 : 0.41 | 1.86 : 1.81 |
| | O1 | 0.28 : 0.24 | 1.03 : 0.99 |
| | O2 | 0.27 : 0.23 | 1.02 : 0.98 |
| | O3 | 0.27 : 0.24 | 1.02 : 0.98 |
| | | : | : |
| g++ 3.3.1 (Cygwin) | No | 0.33 : 0.30 | 1.59 : 1.56 |
| Mingw32 interface | O1 | 0.20 : 0.16 | 0.87 : 0.84 |
| | O2 | 0.19 : 0.16 | 0.85 : 0.82 |
| | O3 | 0.19 : 0.16 | 0.85 : 0.82 |
| | | : | : |
| gpp 3.2.1 (DJGPP) | No | 0.37 : 0.24 | 1.99 : 1.92 |
| | O1 | 0.20 : 0.11 | 1.15 : 1.05 |
| | O2 | 0.19 : 0.11 | 1.08 : 0.99 |
| | O3 | 0.19 : 0.11 | 1.08 : 0.99 |
| | | : | : |
|--------------------------------------------------------|
| Digital Mars C/C++ Compiler, STLport 4.5.3 |
|--------------------------------------------------------|
| Version 8.35n | - | 0.20 : 0.16 | 0.84 : 0.80 |
| | | : | : |
| Version 8.36.4n | - | 0.20 : 0.16 | 0.84 : 0.80 |
|============== =============== =============== =============



B. The names of DLL files on which the programs depend :

* g++ 3.3.1 (Cygwin)
------------------
C:\cygwin\bin\c ygwin1.dll
C:\WINNT\System 32\KERNEL32.dll
C:\WINNT\System 32\NTDLL.DLL


* g++ 3.3.1 (Cygwin, Mingw32 interface)
-------------------------------------
C:\WINNT\System 32\msvcrt.dll
C:\WINNT\System 32\KERNEL32.dll
C:\WINNT\System 32\NTDLL.DLL


* gpp 3.2.1 (DJGPP)
-----------------
Unknown


* Digital Mars C/C++ 8.35n
------------------------
C:\WINNT\System 32\KERNEL32.DLL
C:\WINNT\System 32\NTDLL.DLL
C:\WINNT\System 32\USER32.DLL
C:\WINNT\System 32\GDI32.DLL



C. Notes.
Note-1. The main() program in

http://groups.google.com/groups?selm=bnni5p%2412i47o%241%40ID-79865.news.uni-berlin.de

was slightly changed to get the processor time used.

// ------ Updated main() : BEGIN ------
#include <time.h> // Added
int main (int argc, char **argv)
{
const string option (check (argc, argv));
if (option.empty() )
{
usage (argv);
return 1;
}

const uint N = atoi (argv[2]);

const clock_t clock_start = clock(); // Added
assert (clock_start != clock_t (-1)); // Added

if (option == ALL_FIBS)
{
Fibonacci fib(N);
fib.show_all_nu mbers();
}

if (option == TH_FIB)
{
Fibonacci fib(N);
fib.show_last_n umber();
}

if (option == SOME_FIBS)
{
Fibonacci fib;
for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
}

if (option == RAND_FIBS)
{
const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi (argv[3]);
Fibonacci fib;
for (uint i = 0; i < N; i++) fib.show_number (rand()%max_ran d_fib);
}

// ------ Added : BEGIN ------
const clock_t clock_end = clock();
assert (clock_end != clock_t (-1));

cerr << "CPU time used : " << (double (clock_end - clock_start)/CLOCKS_PER_SEC) << " sec" << endl;
// ------ Added : END --------

return 0;
}
// ------ Updated main() : END --------



Note-2. To get the real time used the time() utility was used.



D. Comment.
It seems that there is some inconsistency between real-time and CPU-time
while computing Fibonacci [10000] through the DJGPP gpp compiler :
CPU-time is too small with regard to real-time.
Probably that might be caused by too small CLOCKS_PER_SEC value (91).
Note. In Cygwin, MinGW, Digital Mars : CLOCKS_PER_SEC = 1000.



--
=============== =============== =======
Alex Vinokur
mailto:alexvn@c onnect.to

http://mathforum.org/library/view/10978.html

news://news.gmane.org/gmane.comp.lang.c++.perfometer
=============== =============== =======