learn-fp-go
learn-fp-go copied to clipboard
l3x
Chapter 1 benchmarking confusion
I may have found an issue with the listing for the Fibonacci sequence using memoization. I think that there is a correct implementation in the memoize.go_ORIG but the memorize.go is not working as expected.
It looks to me like the current implementation is only caching the result of the outer function, not the intermediate steps. The benchmarks are misleading because they average all of the runs to generate the ops/sec metric. I think what is happening is the first call is taking a long time but each subsequent call is extremely quick and hence the average is very quick.
I wrote an example that I think demonstrates this:
func duration(name string, fn fib.Memoized, n int) {
// time the first pass through.
start := time.Now()
fib.FibMem(n)
end := time.Now()
elapsed := end.Sub(start)
fmt.Printf("First pass: %v(%v): %v\n", name, n, elapsed)
// time the second pass through
start = time.Now()
fib.FibMem(n)
end = time.Now()
elapsed = end.Sub(start)
fmt.Printf("Second pass: %v(%v): %v\n", name, n, elapsed)
}
func TestMis(t *testing.T) {
duration("FibMem", fib.FibMem, 44)
duration("FibMem2", fib.FibMem2, 44)
}
where FibMem is the listing in the book and FibMem2 is the old listing. The results are
First pass : FibMem(44): 2.364160474s
Second pass: FibMem(44): 380ns
First pass : FibMem2(44): 96ns
Second pass: FibMem2(44): 57ns
There is also a chance I am just getting mixed up. Could you help me work through this?
Thanks
I have a gist with a more complete listing if that is helpful.
https://gist.github.com/schafer14/266fb061a73b5e31df72a1efe7ef471a
Let me know if I can provide more helpful information.
I can confirm the same problem after running my benchmarks. The correct implementation is in file memoize.go_ORIG. memorize.go memoizes only the result but intermediate numbers and it's misleading.
