Benchmarks

It is time to put theory to the test and see how each of these fibonacci implementations perform. We will build an optimized binary with the command:

$ odin build . -o:speed

and then run it with hyperfine. Let’s keep the code code minimal.

package main

import "core:fmt"

fibonacci_recursive :: proc(n: int) -> n {
    // ...
}


fibonacci_iterative :: proc(n: int) -> n {
    // ...
}


fibonacci_matrix :: proc(n: int) -> n {
    // ...
}

main :: proc() {
    fmt.println(fibonacci_recursive(45))
    // fmt.println(fibonacci_iterative(45))
    // fmt.println(fibonacci_matrix(45))
}

We will first run the recursive version with hyperfine. Then comment out that line and uncomment the iterative version, measure and so on..

F(45)

• Recursive algorithm

❯ hyperfine ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):      3.328 s ±  0.026 s    [User: 3.315 s, System: 0.002 s]
  Range (min … max):    3.295 s …  3.351 s    10 runs

• Iterative algorithm

❯ hyperfine ./fibonacci --shell=none
Benchmark 1: ./fibonacci
  Time (mean ± σ):     879.8 µs ± 211.7 µs    [User: 241.2 µs, System: 511.0 µs]
  Range (min … max):   666.6 µs … 1764.0 µs    3518 runs

• Matrix implementation

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     902.2 µs ± 221.5 µs    [User: 229.9 µs, System: 550.8 µs]
  Range (min … max):   650.5 µs … 1630.1 µs    3252 runs

The recursive version was unbearably slow and finished in 3.3 seconds. The iterative and matrix implementations are 3500x faster.

F(1_000_000_000)

• Recursive algorithm

Maybe it’ll finish running if I wait till the end of the universe and until time loops back to the present?

• Iterative algorithm

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     252.5 ms ±   1.9 ms    [User: 250.6 ms, System: 0.7 ms]
  Range (min … max):   249.8 ms … 256.3 ms    11 runs

• Matrix implementation

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     863.3 µs ± 207.5 µs    [User: 234.7 µs, System: 508.0 µs]
  Range (min … max):   637.9 µs … 1546.5 µs    3426 runs

The iterative version of fibonacci is slowing down but the matrix implementation is still fast because $\log (n)$ grows insanely slow.

Exercise

Use fibonacci_matrix to calculate F(100_000_000_000). Is there anything wrong with the output? If so what do you think went wrong and how will you fix it?