cubbi.com: Benchmarks of different programming languages calculating fibonacci numbers

cubbi.com: Benchmarks of different programming languages calculating fibonacci numbers

serious stuff
  www.cubbi.com
personal
programming
  fibonacci numbers
    algorithms
    benchmarks
    forth examples
    postscript examples
    muf examples
    joy examples
    j examples
    scheme examples
    hope examples
    ocaml examples
    haskell examples
    prolog examples
    c++ examples
    java examples
    assembly language examples
    fortran examples
    c examples
    sh examples
    awk examples
    perl examples
    tcl examples
  asmix
  hacker test
  resume
science
martial arts
fun stuff
  www.cubbi.org

This page contains the benchmarks for my Fibonacci numbers page. Please remember that these benchmarks do not show strength or weakness of any programming language. All they show is how efficient specific language translators are at implementing the featured algorithms.

Benchmarked on Intel Pentium 4 2.20GHz running Linux 2.5.75 with 640M RAM
RAW BENCHMARK DATA available if you want to see them.

ALGORITHM 1a: BINARY RECURSION
The exact calculation time for the n'th Fibonacci number is T(n)=t₀φⁿ, where φ=(1+sqrt(5))/2 and t₀ is the time to execute a single recursion call.
Language	Translator [*]	t₀	T(46), seconds
OCaml	INRIA OCaml 3.07pl2 [c]	11.94 ns	49.33	Execution time (seconds) vs. Fibonacci number calculated
Assembly	GNU as 2.12.90.0.9 [c]	13.40 ns	55.37
C	GNU gcc 3.3.2 [c]	16.08 ns	66.17
C++	GNU g++ 3.3.2 [c]	19.28 ns	78.96
Haskell	GHC 6.2 [c]	23.19 ns	95.30
Java	Sun Java 2 1.4.2 [b]	23.77 ns	97.09
Scheme	MIT Scheme 7.7.1 [b]	38.35 ns	157.64
Forth	Tektronix PFE 0.32.94 [i]	258.5 ns	1061.8
Joy	Joy1 by Manfred von Thun, 07-May-03 [i]	600.9 ns	2467.4
PostScript	ESP Ghostscript 7.07.1 [i]	674.1 ns	2767.9
Prolog	Ciao Prolog 1.8p2 [b]	683.7 ns	2807.4
awk	awk by Brian Kernighan, 31-Jul-03 [i]	997.9 ns	4097.5
MUF	FuzzBall MUCK 6.01 [b]	1.717 μs	7050.2
perl	perl 5.8.3 [i]	2.540 μs	10429.5
J	Jsoftware J 5.02a [i]	4.244 μs	17426.3
Hope	Hope by Ross Paterson, 08-Dec-03 [i]	4.382 μs	17993.0
Tcl	Tcl 8.4.5 [i]	14.68 μs	60277.8
sh	zsh 4.0.9 [i]	372.6 μs	1529939.7

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter
Execution time is user time as reported by time(1) except for MUF, where an internal time function was called from the program. The time was measured in 11 points for calculation of t₀. T(46) was measured directly only when it was less than 2000 seconds.

ALGORITHM 2A: Data Structure
The exact calculation time for the n'th Fibonacci number should be T(n)=t₀n², because it takes n additions to calculate a Fibonacci number, and an addition of two big integers is O(n) of their length, and the length of n'th Fibonacci number is O(n). However manipulation of data structures seems to increase the overhead in most languages. This overhead appears to be different for different languages, causing interesting anomalities in their benchmark curves. See for example the weird shape of Java curve, and check out how Haskell beats OCaml at calculation of 140,000th and higher Fibonacci numbers!
Language	Translator [*]	t₀	T(50,000), seconds
Haskell	GHC 6.2 [c]	---	0.909	Execution time (seconds) vs. Fibonacci number calculated
OCaml	INRIA OCaml 3.07pl2 [c]	---	0.454
perl	perl 5.8.3 [i]	---	49.50
Prolog	Ciao Prolog 1.8p2 [b]	---	246
Scheme	MIT Scheme 7.7.1 [b]	---	5300
Java	SUN Java 2 1.4.2 [b]	---	?

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter

ALGORITHM 2B: Simple Recursion
The exact calculation time for the n'th Fibonacci number is T(n)=t₀n², because it takes n additions to calculate a Fibonacci number, and an addition of two big integers is O(n) of their length. The length of n'th Fibonacci number is O(n). Note how close are the top three languages!
Language	Translator [*]	t₀	T(500,000), seconds
OCaml	INRIA OCaml 3.07pl2 [c]	0.11 ns	27.99	Execution time (seconds) vs. Fibonacci number calculated
Haskell	GHC 6.2 [c]	0.14 ns	35.81
Scheme	MIT Scheme 7.7.1 [b]	0.15 ns	37.69
perl	perl 5.8.3 [i]	20.6 ns	5150
Prolog	Ciao Prolog 1.8p2 [b]	?	?
Java	SUN Java 2 1.4.2 [b]	?	?

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter
[?] - It seems that Prolog and Java implement this algorithm differently - the program execution time does not increase as n².

ALGORITHM 2C: Non-Recursive Loop
The exact calculation time for the n'th Fibonacci number is T(n)=t₀n², because it takes n additions to calculate a Fibonacci number, and an addition of two big integers is O(n) of their length. The length of n'th Fibonacci number is O(n).
Language	Translator [*]	t₀	T(500,000), seconds
OCaml	INRIA OCaml 3.07pl2 [c]	0.11 ns	27.43	Execution time (seconds) vs. Fibonacci number calculated
Scheme	MIT Scheme 7.7.1 [b]	0.15 ns	37.81
Java	SUN Java 2 1.4.2 [b]	0.37 ns	92
J	Jsoftware J 5.02a [i]	0.95 ns	240
perl	perl 5.8.3 [i]	20.0 ns	5000

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter

ALGORITHM 3A: Matrix Equation

Language	Translator [*]	t₀	T(1,000,000), seconds
OCaml	INRIA OCaml 3.07pl2 [c]	---	16.53	Execution time (seconds) vs. Fibonacci number calculated
Scheme	MIT Scheme 7.7.1 [b]	---	30.30
Prolog	Ciao Prolog 1.8p2 [b]	---	54.97
Haskell	GHC 6.2 [c]	---	61.97
Java	SUN Java 2 1.4.2 [b]	---	85.50
J	Jsoftware J 5.02a [i]	---	341.7
perl	perl 5.8.3 [i]	---	10500

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter

ALGORITHM 3B: Fast Recursion
Isn't it amazing how Haskell and Java give almost exactly the same time in this example?
Language	Translator [*]	t₀	T(1,000,000), seconds
OCaml	INRIA OCaml 3.07pl2 [c]	---	11.56	Execution time (seconds) vs. Fibonacci number calculated
Scheme	MIT Scheme 7.7.1 [b]	---	12.85
Prolog	Ciao Prolog 1.8p2 [b]	---	47.75
Haskell	GHC 6.2 [c]	---	68.78
Java	SUN Java 2 1.4.2 [b]	---	72.26
J	Jsoftware J 5.02a [i]	---	184.3
perl	perl 5.8.3 [i]	---	2100

[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter