I just stumbled over this nice little repo comparing the simple recursive fibonacci function for several compiled and interpreted languages: https://github.com/drujensen/fib. It seems quite fair as it does not do any optimisation tricks anywhere. I know there are better ways to use Go's powers, but I just wondered, why Go seems to be much slower than other compiled and statically typed languages? I can confirm on my machine with 11s it looks quite similar for Go.
The reason is a combinatorial explosion of recursive computations. In Algorithms 101 they usually explain why Dru Jensen's recursive algorithm is the terrible way to calculate the Fibonacci numbers: http://www.cs.toronto.edu/~gfb/csc104/2016W/Lectures/CSC104.2016W.Week-7.Lecture.Fibonacci.I.pdf. The fib procedure calls itself twice each time it is invoked. By design, Go doesn't have tail recursion: Tail call. By design, Go starts with a very small stack for each goroutine, which it has to grow explosively. No Go programmer would want to use this algorithm, which is around 382,358,169 times slower than the next slowest and 18,593,103,127 times slower than the fastest, so optimization, which would sacrifice performance elsewhere, is pointless.
Here are some Go benchmark results:
$ go test fib_test.go -bench=.
BenchmarkDruJensen-8 1 9482482595 ns/op
BenchmarkPeterSO1-8 50000000 24.8 ns/op
BenchmarkPeterSO2-8 2000000000 0.51 ns/op
fib_test.go:
package main
import (
"fmt"
"testing"
)
// Dru Jensen: https://github.com/drujensen/fib
func fib(n uint64) uint64 {
if n <= 1 {
return 1
} else {
return fib(n-1) + fib(n-2)
}
}
func BenchmarkDruJensen(b *testing.B) {
for i := 0; i < b.N; i++ {
fib(46)
}
}
// PeterSO
func fibonacci1(n int) uint64 {
f := uint64(0)
a, b := uint64(0), uint64(1)
for i := 0; i < n; i++ {
f, a, b = a, b, a+b
if a > b {
break
}
}
return f
}
func BenchmarkPeterSO1(b *testing.B) {
for i := 0; i < b.N; i++ {
fibonacci1(46)
}
}
var fibonaccis = []uint64{
0,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073,
4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
53316291173, 86267571272, 139583862445, 225851433717, 365435296162,
591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881,
6557470319842, 10610209857723, 17167680177565, 27777890035288,
44945570212853, 72723460248141, 117669030460994, 190392490709135,
308061521170129, 498454011879264, 806515533049393, 1304969544928657,
2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464,
14472334024676221, 23416728348467685, 37889062373143906,
61305790721611591, 99194853094755497, 160500643816367088,
259695496911122585, 420196140727489673, 679891637638612258,
1100087778366101931, 1779979416004714189, 2880067194370816120,
4660046610375530309, 7540113804746346429, 12200160415121876738,
}
// PeterSO
func fibonacci2(n int) uint64 {
return fibonaccis[n]
}
func BenchmarkPeterSO2(b *testing.B) {
for i := 0; i < b.N; i++ {
fibonacci2(46)
}
}
TL;DR My conclusion up to now is, that we probably should avoid recursion in favour of iterative algorithms principally, as long as there is no tail call optimisation in Go. If not using recursion, Go seems to be insanely fast :-)
Out of curiosity I compared another (simpler) iterative algorithm to Peter's version (BTW, you need to change i < n to i <= n to get the correct Fibonacci of 46). Interestingly, in main.go order matters, if not using the compiled variant. The second function call is the faster. We need to use the benchmark to get objective results, that are like this:
go test -bench .
BenchmarkFibIt-4 100000000 18.5 ns/op
BenchmarkFibP-4 50000000 29.1 ns/op
BenchmarkFib-4 1 12008314197 ns/op
By not using variable f but directly using x, it gets a bit faster ;-) To my surprise, the uncompiled variant of running main.go is nearly as fast as the compiled one, sometimes it's even faster!
My conclusion up to now is, that we probably should avoid recursion in favour of iterative algorithms principally, as long as there is no tail call optimisation in Go.
main.go:
package main
import (
"fmt"
"log"
"time"
)
func fib(n int) uint64 {
if n <= 1 {
return 1
}
return fib(n-1) + fib(n-2)
}
func fibIt(n int) uint64 {
var x, y uint64
x, y = 0, 1
for i := 0; i < n; i++ {
// c <- x
x, y = y, x+y
}
return x
}
func fibP(n int) uint64 {
f := uint64(0)
a, b := uint64(0), uint64(1)
for i := 0; i <= n; i++ {
f, a, b = a, b, a+b
if a > b {
break
}
}
return f
}
func main() {
var start time.Time
var elapsed time.Duration
start = time.Now()
fibIt(46)
elapsed = time.Since(start)
fmt.Println("Iterative Fibonacci of 46 took", elapsed)
start = time.Now()
fibP(46)
elapsed = time.Since(start)
fmt.Println("Peter's Iterative Fibonacci of 46 took", elapsed)
start = time.Now()
fib(46)
elapsed = time.Since(start)
fmt.Println("Recursive Fibonacci of 46 took", elapsed)
}
main_test.go:
package main
import (
"testing"
)
func BenchmarkFibIt(b *testing.B) {
for i := 0; i < b.N; i++ {
fibIt(46)
}
}
func BenchmarkFibP(b *testing.B) {
for i := 0; i < b.N; i++ {
fibP(46)
}
}
func BenchmarkFib(b *testing.B) {
for i := 0; i < b.N; i++ {
fib(46)
}
}