Fibonacci: non-recursive vs memoized recursive puzzling timing results

user_30767 0
Viewed 164

After watching an MIT lecture on dynamic programming, I felt like practicing a bit with Fibonacci. I first wrote the naive recursive implementation and then added memoization. Here is the memoized version:

package main

import (
    "fmt"
)

func fib_memoized(n int, memo map[int]int64) int64 {
    memoized, ok := memo[n]
    if ok {
        return memoized
    }
    if n < 2 {
        return int64(n)
    }
    f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)
    memo[n] = f
    return f
}

func main() {
    memo := make(map[int]int64)
    for i := 0; i < 10000; i++ {
        fmt.Printf("fib(%d) = %d\n", i, fib_memoized(i, memo))
    }
}

I then proceeded to write a non-recursive version of the program:

package main

import (
    "fmt"
)

func fib(n int) int64 {
    var f1 int64 = 1
    var f2 int64 = 0
    for i := 0; i < n; i++ {
        f1, f2 = f2, f1+f2
    }
    return f2
}

func main() {
    for i := 0; i < 10000; i++ {
        fmt.Printf("fib(%d) = %d\n", i, fib(i))
    }
}

What has puzzled me is the fact that the memoized version seems to perform at least as well as the non-recursive one and, sometimes, even outperform it. Naturally, I was expecting memoization to bring great improvements in comparison to the naive recursive implementation, but I just haven't been able to figure out why/how the memoized version could be on par and even surpass its non-recursive counterpart.

I did try looking into the assembly output (obtained with go tool compile -S) of both versions, but to no avail. I still see the CALL instructions in the memoized version and, to my mind, that should incur enough overhead to justify it being at least slightly outperformed by the non-recursive version.

Could anyone more knowledgeable help me understand what's going on?

P.S. I'm aware of integer overflow; I used 10000 just to increase the load.

Thank you.

go recursion algorithm performance
3 Answers

One quite important thing to keep in mind: memo is preserved between iterations of the testbench. So the memoized version has at most two recursive calls per iteration of the loop in main. I.e. you allow the memoized version to keep memory between individual iterations, while the iterative version needs to calculate from scratch in each iteration.

Next point:
Writing benchmarks is tricky. Tiny details can have a significant impact on the outcome. E.g. the calls to printf most likely take a considerable time to execute, but don't actually account for the runtime of the fibonacci-calculation. I don't have any environment available to test how much the timing is actually affected by these IO-operations, but it's quite likely considerable. Especially since your algorithm is running for a rather minuscule 10000 iterations, or barely 100 microseconds, as can be seen in @Brackens answer.

So to summarize:
Drop the IO from the benchmark, start with an empty memo in each iteration and increase the number of iterations to get better timing.

user_46686060

I think you are asking why the memoized recursive implementation is not much faster than the iterative implementation. Though you mention a "naive recursive implementation" that you do not show?

Using benchmarking you can see the performance of both is comparable, maybe iterative is a little faster:

package kata

import (
    "fmt"
    "os"
    "testing"
)

func fib_memoized(n int, memo map[int]int64) int64 {
    memoized, ok := memo[n]
    if ok {
        return memoized
    }
    if n < 2 {
        return int64(n)
    }
    f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)
    memo[n] = f
    return f
}

func fib(n int) int64 {
    var f1 int64 = 1
    var f2 int64 = 0
    for i := 0; i < n; i++ {
        f1, f2 = f2, f1+f2
    }
    return f2
}

func BenchmarkFib(b *testing.B) {
    out, err := os.Create("/dev/null")
    if err != nil {
        b.Fatal("Can't open: ", err)
    }
    b.Run("Recursive Memoized", func(b *testing.B) {
        memo := make(map[int]int64)
        for j := 0; j < b.N; j++ {
            for i := 0; i < 100; i++ {
                fmt.Fprintf(out, "fib(%d) = %d\n", i, fib_memoized(i, memo))
            }
        }
    })
    b.Run("Iterative", func(b *testing.B) {
        for j := 0; j < b.N; j++ {
            for i := 0; i < 100; i++ {
                fmt.Fprintf(out, "fib(%d) = %d\n", i, fib(i))
            }
        }
    })
}

% go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/brackendawson/kata
cpu: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz
BenchmarkLoop/Recursive_Memoized-12                13424             91082 ns/op
BenchmarkLoop/Iterative-12                         13917             82837 ns/op
PASS
ok      github.com/brackendawson/kata    4.323s

I expect your memoized recursive implementation is not much faster because:

  1. Go does not have good Tail Call Optimization (TCO). As you may have seen from the assembly there are still CALLs, recursion is usually only faster if the CALLs can be optimised out.
  2. Your memoized recursive implementation is not a tail call, the recursive call must be the last statement in the function to use TCOs.
user_14407860
user_155715600
Related