Skip to content

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 and benchmarks crude for now.

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. Then comment out that line and uncomment the iterative version, measure and so on..

\(45^{th}\) Fibonacci number

  • 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 is unbearably slow and took 3.3 seconds. The iterative and matrix implementations were 3500x faster.

Billionth Fibonacci number

  • Recursive algorithm

(Stack overflow and timed out1)

  • 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 slowly.

Exercise 1

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?

  1. If we estimate the amount of time this code will take to finish if we given it enough memory, it will be unimaginably wrong. The universe will probably end before it finishes. ↩