fibonacci_benchmark.cpp

#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <vector>
#include <cstdlib>

uint64_t fib_naive(const int n)
{
    asm(""); // Prevent optimizations
    if (n < 2)
        return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

uint64_t fib_memo_impl(const int n, std::vector<uint64_t>& memo)
{
    asm(""); // Prevent optimizations
    if (n < 2)
        return n;
    if (memo[n] != -1)
        return memo[n];

    return memo[n] = fib_memo_impl(n - 1, memo) + fib_memo_impl(n - 2, memo);
}
uint64_t fib_memo(const int n)
{
    asm(""); // Prevent optimizations
    std::vector<uint64_t> memo(n + 1, -1);
    return fib_memo_impl(n, memo);
}

uint64_t fib_iter(const int n)
{
    asm(""); // Prevent optimizations
    if (n < 2)
        return n;

    uint64_t a = 0, b = 1;
    for (int i = 2; i <= n; ++i)
    {
        const uint64_t c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// Prevent over-optimization
volatile uint64_t fib_sink = 0;
long double bench_ms(const std::function<uint64_t(int)>& fn, const int n, const int repeats)
{
    using clock = std::chrono::steady_clock;
    long double total_ms = 0.0;

    for (int r = 0; r < repeats; ++r)
    {
        auto t0 = clock::now();
        fib_sink = fn(n);
        auto t1 = clock::now();
        std::chrono::duration<long double, std::milli> ms = t1 - t0;
        total_ms += ms.count();
    }
    return total_ms / repeats;
}

struct BenchmarkData
{
    std::function<uint64_t(int)> f;
    std::string name;
    std::vector<long double> times;
};

int main(int, char**)
{
    const std::vector<int> ns =
    {
        1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42
    };

    std::cout << std::fixed << std::setprecision(4);

    static constexpr int repeats = 25;

    std::vector<BenchmarkData> benchmarks
    {
        {
            .f = fib_iter,
            .name = "Iterative",
            .times = {}
        },
        {
            .f = fib_memo,
            .name = "Memoization",
            .times = {}
        },
        {
            .f = fib_naive,
            .name = "Naive",
            .times = {}
        },
    };

    for (auto& f : benchmarks)
    {
        f.times.resize(ns.size());
        for (size_t i = 0; i < ns.size(); ++i)
        {
            const long double t = bench_ms(f.f, ns[i], repeats);
            f.times[i] = t;
        }
    }

    // Print results
    std::cout << "N,";
    for (auto& f : benchmarks)
        std::cout << f.name << ",";
    std::cout << std::endl;
    for (size_t i = 0; i < ns.size(); ++i)
    {
        std::cout << ns[i] << ",";
        for (auto& f : benchmarks)
            std::cout << f.times[i] << ",";
        std::cout << std::endl;
    }
    return 0;
}