Binary Search Cache Effects

benchmark.py

import os

steps = 8192
end   = 6291456

sizes = range(steps, end + 1, steps)

def benchmark(size: int):
    time = 0
    # run LowerBound with the specified size, record the stdout time
    import subprocess

    try:
        result = subprocess.run(f"./LowerBound {size}", shell=True, check=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        exit_code = result.returncode
        if exit_code != 0:
            raise RuntimeError(f"Command '{f'./LowerBound {size}'}' failed with exit code {exit_code}.")

        output_ns = float(result.stdout.decode().strip())
        return output_ns

    except subprocess.CalledProcessError as e:
        exit_code = e.returncode
        raise RuntimeError(f"Command failed: {e.stderr.decode().strip()}")

if __name__ == "__main__":
    print(f"{'size':>10} {'time (s)':>10}")
    print("-" * 20)
    for size in sizes:
        try:
            elapsed = benchmark(size)
            print(f"{size:>10} {elapsed:>10.4f}")
            with open("benchmark_results.csv", "a") as f:
                if f.tell() == 0:  # Check if file is empty to write the header
                    f.write("size,time taken\n")
                f.write(f"{size},{elapsed:.4f}\n")
        except Exception as e:
            print(f"Failed to benchmark size {size}: {e}")

BinarySearch.cpp

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

int lower_bound(int needle, std::vector<int> haystack) {
        int l = 0, r = haystack.size() - 1;
        while (l < r)
        {
                int m = (l + r) / 2;
                if (haystack[m] == needle) return m;
                if (haystack[m] >= needle)
                {
                        r = m;
                } else {
                        l = m + 1;
                }
        }

        return haystack[l];
}

int main(int argc, char** args) {
        if (argc < 2) {
                std::cout << "Usage: " << args[0] << " <size of array>" << std::endl;
        }

        int size = std::atoi(args[1]);

        std::vector<int> array(size);

        // Generate n-element array.
        for(int i = 0; i < size; i++) {
                array.push_back(i);
        }

        long double total_time = 0;
        for (int i = 0; i < 100; i++) {
                int random_number = std::rand() % size; // Generate a random number within the array range.
                auto start = std::chrono::high_resolution_clock::now();
                volatile int result = lower_bound(random_number, array); // Prevent optimization.
                auto end = std::chrono::high_resolution_clock::now();
                total_time += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }

        std::cout << (total_time / 100) << std::endl;

        return 0;
}