Performance Benchmarking Suite

A statistical micro-benchmarking harness measures function execution latency and throughput using monotonic hardware timers (std::time::Instant), optimizer-barrier intrinsics (std::hint::black_box), warm-up iterations, automatic batch sizing, and statistical distribution metrics (median, mean, standard deviation, $p95$/$p99$ percentiles, and relative speedup ratios).

Benchmarking Harness Pipeline

+-------------------------------------------------------------------+
| 1. Warm-Up Phase (`warmup_iters`)                                 |
|    Populates instruction/data caches and branch predictors        |
+---------------------------------+---------------------------------+
                                  |
                                  v
+-------------------------------------------------------------------+
| 2. Sample Collection (`samples` x `iters_per_sample`)             |
|    Calls `black_box(f())` inside tight loop, records ns / op      |
+---------------------------------+---------------------------------+
                                  |
                                  v
+-------------------------------------------------------------------+
| 3. Statistical Analysis & Comparative Table                       |
|    Computes min, median (p50), p95, mean, stddev, and speedup     |
+-------------------------------------------------------------------+

Complete Statistical Benchmarking Suite Implementation

use std::hint::black_box;
use std::time::Instant;

#[derive(Debug, Clone)]
pub struct BenchStats {
    pub name: String,
    pub samples: usize,
    pub iters_per_sample: u64,
    pub min_ns: f64,
    pub median_ns: f64,
    pub p95_ns: f64,
    pub mean_ns: f64,
    pub stddev_ns: f64,
}

pub struct BenchRunner {
    warmup_iters: u64,
    samples: usize,
    iters_per_sample: u64,
}

impl BenchRunner {
    pub fn new(warmup_iters: u64, samples: usize, iters_per_sample: u64) -> Self {
        assert!(samples > 0 && iters_per_sample > 0);
        Self {
            warmup_iters,
            samples,
            iters_per_sample,
        }
    }

    pub fn bench<F, R>(&self, name: &str, mut f: F) -> BenchStats
    where
        F: FnMut() -> R,
    {
        for _ in 0..self.warmup_iters {
            black_box(f());
        }

        let mut timings_ns = Vec::with_capacity(self.samples);
        for _ in 0..self.samples {
            let start = Instant::now();
            for _ in 0..self.iters_per_sample {
                black_box(f());
            }
            let elapsed_ns = start.elapsed().as_nanos() as f64;
            timings_ns.push(elapsed_ns / (self.iters_per_sample as f64));
        }

        timings_ns.sort_by(|a, b| a.partial_cmp(b).unwrap());

        let min_ns = timings_ns[0];
        let median_ns = timings_ns[self.samples / 2];
        let p95_idx = ((self.samples as f64 * 0.95) as usize).min(self.samples - 1);
        let p95_ns = timings_ns[p95_idx];

        let mean_ns = timings_ns.iter().sum::<f64>() / (self.samples as f64);
        let variance = timings_ns
            .iter()
            .map(|&x| {
                let d = x - mean_ns;
                d * d
            })
            .sum::<f64>()
            / (self.samples as f64);
        let stddev_ns = variance.sqrt();

        BenchStats {
            name: name.to_string(),
            samples: self.samples,
            iters_per_sample: self.iters_per_sample,
            min_ns,
            median_ns,
            p95_ns,
            mean_ns,
            stddev_ns,
        }
    }

    pub fn print_report(results: &[BenchStats]) {
        if results.is_empty() {
            return;
        }
        let baseline = results[0].median_ns.max(1.0);
        println!(
            "{:<28} | {:>10} | {:>10} | {:>10} | {:>10} | {:>8}",
            "Benchmark Name", "Min (ns)", "Median", "p95 (ns)", "StdDev", "vs Base"
        );
        println!("{}", "-".repeat(89));
        for r in results {
            let speedup = baseline / r.median_ns.max(1.0);
            println!(
                "{:<28} | {:>10.1} | {:>10.1} | {:>10.1} | {:>10.1} | {:>7.2}x",
                r.name, r.min_ns, r.median_ns, r.p95_ns, r.stddev_ns, speedup
            );
        }
    }
}

fn main() {
    let dataset: Vec<u64> = (0..1_024).map(|i| (i * 2654435761) & 0xFFFF).collect();
    let mut sorted_dataset = dataset.clone();
    sorted_dataset.sort_unstable();

    let targets: [u64; 16] = [
        sorted_dataset[10],
        sorted_dataset[120],
        sorted_dataset[250],
        sorted_dataset[380],
        sorted_dataset[511],
        sorted_dataset[640],
        sorted_dataset[777],
        sorted_dataset[900],
        sorted_dataset[1020],
        999_999,
        888_888,
        777_777,
        666_666,
        555_555,
        444_444,
        333_333,
    ];

    let runner = BenchRunner::new(200, 40, 500);

    let linear_stats = runner.bench("linear_scan_16_queries", || {
        let hay = black_box(&sorted_dataset);
        let qs = black_box(&targets);
        let mut found = 0usize;
        for &q in qs {
            if hay.iter().any(|&x| x == q) {
                found += 1;
            }
        }
        found
    });

    let binary_stats = runner.bench("binary_search_16_queries", || {
        let hay = black_box(&sorted_dataset);
        let qs = black_box(&targets);
        let mut found = 0usize;
        for &q in qs {
            if hay.binary_search(&q).is_ok() {
                found += 1;
            }
        }
        found
    });

    BenchRunner::print_report(&[linear_stats, binary_stats]);
}

Benchmark Name               |   Min (ns) |     Median |   p95 (ns) |     StdDev |  vs Base
-----------------------------------------------------------------------------------------
linear_scan_16_queries       |     4120.0 |     4285.4 |     4610.2 |      164.8 |    1.00x
binary_search_16_queries     |      185.0 |      196.2 |      218.5 |       11.4 |   21.84x