secret
Last active

Fibonacci microbenchmark, moved to here: https://github.com/wting/fib-benchmark#performance

  • Download Gist
Fib.java
Java
1 2 3 4 5 6 7 8 9 10 11
class Fib {
static int fib(int n) {
if (n < 2)
return 1;
return fib(n-2) + fib(n-1);
}
 
public static void main(String[] args) {
System.out.println(fib(40));
}
}
fib.c
C
1 2 3 4 5 6 7 8 9 10 11 12 13
// gcc -O2 fib.c
#include <stdio.h>
 
int fib(n) {
if (n < 2)
return 1;
return fib(n-2) + fib(n-1);
}
 
int main(int argc, char const* argv[]) {
printf("%d\n", fib(40));
return 0;
}
fib.clj
Clojure
1 2 3 4 5 6 7
(defn fib [n]
(if (= n 0) 0
(if (= n 1) 1
(+ (fib (- n 1)) (fib (- n 2))))))
 
(defn -main
(println (fib 30)))
fib.go
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
package main
 
import "fmt"
 
func fib(n int) int {
if n < 2 {
return 1
}
 
return fib(n-2) + fib(n-1)
}
 
func main() {
fmt.Println(fib(40))
}
fib.hs
Haskell
1 2 3 4 5 6 7 8
-- ghc -O -O2 -optc-O3 fib.hs
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
 
main = do
print (fib 40)
fib.lua
Lua
1 2 3
function fib(n) return n < 2 and 1 or fib(n-2) + fib(n-1) end
 
print(fib(40))
fib.py
Python
1 2 3 4 5 6
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)
 
print(fib(40))
fib.rb
Ruby
1 2 3 4 5 6 7 8
def fib(n)
if n < 2
return 1
end
return fib(n-2) + fib(n-1)
end
 
puts fib(40)
fib.rc
1 2 3 4 5 6 7 8 9 10
fn fib(n: int) -> int {
if n < 2 {
return 1;
}
fib(n-2) + fib(n-1)
}
 
fn main() {
io::println(fmt!("%d", fib(40)));
}
results.md
Markdown

Performance

C:              0.38s
Java:           0.55s
Go:             0.90s
Rust:           1.29s
Haskell:        1.32s
LuaJit:         2.17s
PyPy:          10.06s
Lua:           21.18s
Ruby 1.9.3:    22.13s
Ruby 2.0.0:    22.13s
Python 2.7.3:  43.88s
Python 3.3.0:  66.28s

Test Machine

CPU: i7-2640M @ 2.80GHz
RAM: 16GB
HDD: SSD

The Lua version should be
function fib(n) return n < 2 and 1 or fib(n-2) + fib(n-1) end

so that fib(0) will be 1, just like your other implementations.

Edit: swapped the order of the recursive calls to be consistent with original implementation

Thanks, I've updated the code and ran the benchmark again but it only made a marginal difference (~0.1s).

The Clojure results seem to be missing.

@johntyree: Clojure results added here. Gists don't support directories so I had to migrate to a repo.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.