obj-core 1.0.2

//! M4 exit-criterion benchmark: range-scan throughput over a B+tree
//! populated with 100 000 random `(key=8 bytes, value=512 bytes)`
//! pairs (issue #30).
//!
//! `design.md` cites ~38 ms as the collection-scan target on Linux
//! x86-64 hardware with fast solid-state storage. The bench's
//! `TARGET_MS` constant is the **gate baseline** — the wall time
//! the bench is expected to clear on the CI shared runner, with
//! enough headroom to absorb run-to-run noise. It is not the
//! design.md aspirational number; that target is tracked in
//! `design.md` § Performance, and improvements move the gate
//! baseline downward over time. The benchmark prints both the
//! measured median and the gate so a glance at the output tells
//! the developer whether the commit moves the bar.
//!
//! # Fail-gate (#32)
//!
//! By default the bench is informational — it prints the design
//! target alongside criterion's median and never fails the run.
//! Set `OBJ_BENCH_ENFORCE=1` to upgrade the gate to a hard failure
//! when the median exceeds `TARGET_MS`. The CI `bench` workflow
//! sets this so a regression on the Linux x86-64 runner blocks
//! merge; local `cargo bench` stays informational by default.
//! `CONTRIBUTING.md` § Performance bar documents how to interpret
//! a miss on each platform.
//!
//! The bench is intentionally allocation-tolerant: the iterator
//! yields owned `(Vec<u8>, Vec<u8>)` pairs in M4 because the
//! `pager.read_page` lifetime is per-step. M6 MVCC reader snapshots
//! may revisit this trade-off; until then the benchmark is the
//! reference measurement for the current design.
//!
//! # Running
//!
//! ```text
//! cargo bench --bench btree_range
//! ```
//!
//! Performance is hardware-dependent. On Apple Silicon the benchmark
//! may exceed the Linux fast-SSD target listed in `design.md`; this
//! is a platform difference, not a regression. `CONTRIBUTING.md`
//! § 8 documents the target and how to interpret a miss.

#![forbid(unsafe_code)]

use std::hint::black_box;
use std::time::{Duration, Instant};

use criterion::{criterion_group, criterion_main, Criterion};
use obj_core::btree::BTree;
use obj_core::pager::{Config, Pager};
use obj_core::platform::FileHandle;
use rand::{Rng, SeedableRng};
use rand_chacha::ChaCha8Rng;

const NUM_ENTRIES: usize = 100_000;
const KEY_BYTES: usize = 8;
const VALUE_BYTES: usize = 512;
/// Seed for the random key/value generator. Fixed so that the
/// bench's tree shape is reproducible across runs.
const SEED: u64 = 0xDEAD_BEEF;
/// Gate baseline wall time for the 100k-doc scan on the CI shared
/// runner (Linux x86-64, 2 vCPU, no `NVMe`). Set above the observed
/// median with headroom for run-to-run noise; "we work from here"
/// — improvements drive this number down, regressions push it up
/// past the gate. See `design.md` § Performance for the aspirational
/// target this baseline is meant to approach.
const TARGET_MS: u128 = 600;
/// Sample count for the `OBJ_BENCH_ENFORCE` gate. Independent of
/// criterion's own sample count — small enough that the extra
/// measurement does not meaningfully extend bench time, large enough
/// that the median is stable.
const GATE_SAMPLES: usize = 11;

fn populate_tree() -> (Pager<FileHandle>, BTree<FileHandle>) {
    let mut pager = Pager::<FileHandle>::memory(Config::default()).expect("pager init");
    let mut tree = BTree::<FileHandle>::empty(&mut pager).expect("empty tree");
    let mut rng = ChaCha8Rng::seed_from_u64(SEED);
    let mut inserted = 0usize;
    let mut value = [0u8; VALUE_BYTES];
    while inserted < NUM_ENTRIES {
        let key = random_key(&mut rng);
        rng.fill(&mut value[..]);
        // Skip duplicate keys: random 8-byte keys collide with
        // negligible probability across 100k draws (birthday
        // paradox: <1% at this scale) but the insert path returns
        // BTreeKeyExists if a duplicate appears.
        match tree.insert(&mut pager, &key, &value) {
            Ok(()) => inserted += 1,
            Err(obj_core::Error::BTreeKeyExists) => (),
            Err(e) => panic!("populate: insert failed: {e:?}"),
        }
    }
    pager.commit().expect("commit");
    (pager, tree)
}

fn random_key(rng: &mut ChaCha8Rng) -> [u8; KEY_BYTES] {
    let mut buf = [0u8; KEY_BYTES];
    rng.fill(&mut buf);
    buf
}

fn bench_full_scan(c: &mut Criterion) {
    // Build the tree ONCE — populate is expensive; criterion's
    // measurement loop reuses it across iterations.
    let (mut pager, tree) = populate_tree();
    let mut group = c.benchmark_group("btree_range");
    group.sample_size(30);
    // Wall-clock measurement budget — 30 samples * ~scan time is
    // small, but criterion sometimes needs more time to stabilise
    // its statistics on the slower platforms (macOS Apple Silicon
    // in particular).
    group.measurement_time(Duration::from_secs(15));
    group.bench_function("full_scan_100k_x_512b", |b| {
        b.iter(|| {
            let iter = tree.iter(&mut pager).expect("iter");
            let mut count = 0usize;
            for step in iter {
                let (k, v) = step.expect("iter step");
                black_box(&k);
                black_box(&v);
                count += 1;
            }
            assert_eq!(count, NUM_ENTRIES, "scan must return every entry");
            black_box(count);
        });
    });
    group.finish();
    // #32: gather an independent median from `GATE_SAMPLES` scans for
    // the fail-gate. Criterion's analysis is statistically richer but
    // its median is not exposed to bench code, and an external median
    // is sufficient for a "did the commit blow past the target" check.
    let median_ms = measure_median_ms(&mut pager, &tree);
    eprintln!(
        "btree_range: gate baseline = {TARGET_MS} ms; OBJ_BENCH_ENFORCE gate \
         measured median = {median_ms} ms. CONTRIBUTING.md § Performance bar \
         documents how to interpret a miss."
    );
    // Hard fail — the CI bench workflow sets OBJ_BENCH_ENFORCE=1 and
    // treats a non-zero exit as a regression. Local runs (no env var
    // set) stay informational. Per #30's note that shared CI runners
    // are noisy, the gate lives in a dedicated workflow (bench.yml),
    // NOT in the per-PR `test` job.
    assert!(
        !(bench_enforce_enabled() && median_ms > TARGET_MS),
        "btree_range: OBJ_BENCH_ENFORCE=1 and measured median {median_ms} ms > target {TARGET_MS} ms"
    );
}

/// Measure `GATE_SAMPLES` full-scan wall times and return the median
/// in whole milliseconds. Power-of-ten Rule 2: the sample-count loop
/// is bounded by `GATE_SAMPLES`.
fn measure_median_ms(pager: &mut Pager<FileHandle>, tree: &BTree<FileHandle>) -> u128 {
    let mut samples_ms: Vec<u128> = Vec::with_capacity(GATE_SAMPLES);
    for _ in 0..GATE_SAMPLES {
        let start = Instant::now();
        let iter = tree.iter(pager).expect("iter");
        let mut count = 0usize;
        for step in iter {
            let (k, v) = step.expect("iter step");
            black_box(&k);
            black_box(&v);
            count += 1;
        }
        let elapsed = start.elapsed();
        assert_eq!(
            count, NUM_ENTRIES,
            "gate scan must return every entry (got {count})"
        );
        samples_ms.push(elapsed.as_millis());
    }
    samples_ms.sort_unstable();
    samples_ms[GATE_SAMPLES / 2]
}

fn bench_enforce_enabled() -> bool {
    std::env::var("OBJ_BENCH_ENFORCE")
        .ok()
        .is_some_and(|v| !v.is_empty() && v != "0")
}

criterion_group!(benches, bench_full_scan);
criterion_main!(benches);