znippy-plugin-git 0.1.1

//! Does aligning the `stree` keyspace to the cache line make oid→ordinal
//! lookup faster? Three arms, one variable.
//!
//! ```text
//! CARGO_TARGET_DIR=/home/rickard/scratch/cargo/gunnar-oidalign \
//!   cargo run --release --no-default-features --example oid_align_bench -- rot=0
//! ```
//!
//! Arguments (`key=value`, all optional):
//!   `sizes=1000,100000,1000000,4000000`  object counts to sweep
//!   `queries=100000`                     lookups per timed run
//!   `runs=5`                             timed runs per cell; their spread IS the band
//!   `oid=20`                             20 (sha1) or 32 (sha256)
//!   `rot=0|1|2`                          which arm is built and timed first
//!   `only=0|1|2`                         build and time ONE arm — for `perf stat`,
//!                                        which cannot attribute a counter to an
//!                                        arm when three of them share a process
//!   `buildruns=<runs>`                   build repetitions, when the timed cells want
//!                                        more runs than a 4-second build does
//!   `dry`                                run the timing loop with the lookup call
//!                                        and nothing else removed — the `perf stat`
//!                                        subtrahend, see `time_ordinals`
//!   `force`                              measure even on a busy box
//!
//! ## The question, and why the header is only half of it
//!
//! [`znippy_plugin_git::oid_index`] wrote a 24-byte header and started the
//! `stree` keyspace right after it. 24 mod 64 = 24, so every 64-byte leaf block
//! straddles two cache lines. The obvious fix — pad the header to 64 — is not
//! sufficient on its own: the section is a `Vec<u8>`, whose alignment is 1 by
//! type, so a 64-byte header over an arbitrary base is still an arbitrary phase.
//! Both terms have to move, and the third arm exists so the two can be told
//! apart:
//!
//! | arm | header | allocation | keyspace phase |
//! |---|---:|---|---:|
//! | `compact24` | 24 | `Vec<u8>` | whatever glibc gives + 24 |
//! | `compact24+align` | 24 | 64-aligned | 24 |
//! | `aligned64` | 64 | 64-aligned | **0** |
//!
//! ## What alignment can and cannot reach here
//!
//! `stree`'s internal nodes are 8 × `i64` — one cache line — but they are **not
//! in this section**. `STree64Mmap` builds them into its own `Vec<[i64; 8]>`,
//! which no header can move. The section holds the **leaf layer** only: the
//! sorted key array that a routed query linear-scans for up to `B + 1` = 9 keys.
//! So the ceiling on this experiment is one memory access per lookup — the last
//! and coldest one — not one per level. That is stated before the measurement,
//! not after it.
//!
//! ## Method
//!
//! * **Only `ordinals_batch` is timed.** It is the oid→ordinal step and nothing
//!   else: no payload column is touched. All three arms are `PackedPayload` and
//!   differ in exactly one argument.
//! * **The arms are proved distinct before anything is timed** —
//!   `keyspace_phase()` is asserted per arm. Two arms on the same phase would be
//!   one arm measured twice, and would look exactly like a null result.
//! * **The arms are proved identical in output** — every arm's full
//!   `Vec<Option<u32>>` is compared against `compact24`'s for every workload.
//! * **Position is cancelled by rotation**: run with `rot=0,1,2` and take the
//!   geometric mean, so each arm builds and times first exactly once. The prior
//!   payload sweep measured a real 1.1% penalty for whichever arm ran second.
//! * **`/proc/loadavg` with every figure**, and the run refuses above 1-min 4.0.
//!
//! Single-threaded on purpose (LAW 3: no rayon anywhere; the fan-out primitive
//! in this tree is `gatling`, and a memory-phase question does not want one).
//!
//! ## The answer: no
//!
//! `aligned64` takes **5.2% off cache-misses**, in four passes out of four, with
//! `instructions` identical to five figures and `dTLB-load-misses` unmoved. And
//! it does not move the clock: **0 of 24 cells** clear their own noise band
//! (median 8.2%), geomean `aligned/compact` 0.998; re-run at 4e6 with the band
//! tightened to 5.0%, **0 of 6**. The misses were already hidden by the eight-
//! deep pipelined walk. Full write-up in [`znippy_plugin_git::oid_index`].

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

use znippy_plugin_git::index_layout::{
    IndexEntry, ObjectIndex, PackedPayload, Rng, synthetic_entries,
};
use znippy_plugin_git::oid_index::OidLayout;

// ── environment ───────────────────────────────────────────────────────────────

fn loadavg() -> (f64, String) {
    let s = std::fs::read_to_string("/proc/loadavg").unwrap_or_default();
    let one = s
        .split_whitespace()
        .next()
        .and_then(|x| x.parse::<f64>().ok())
        .unwrap_or(f64::NAN);
    (one, s.trim().to_string())
}

// ── statistics ────────────────────────────────────────────────────────────────

#[derive(Clone, Copy)]
struct Stat {
    med: f64,
    lo: f64,
    hi: f64,
}

impl Stat {
    fn of(mut v: Vec<f64>) -> Self {
        v.sort_by(|a, b| a.partial_cmp(b).unwrap());
        Stat {
            med: v[v.len() / 2],
            lo: v[0],
            hi: v[v.len() - 1],
        }
    }

    /// `(max - min) / median` — the run-to-run noise band. Nothing is claimed
    /// below it.
    fn spread(&self) -> f64 {
        if self.med == 0.0 {
            0.0
        } else {
            (self.hi - self.lo) / self.med
        }
    }
}

// ── workload ──────────────────────────────────────────────────────────────────

struct Queries {
    owned: Vec<Vec<u8>>,
    expected_hits: usize,
    label: &'static str,
}

impl Queries {
    fn refs(&self) -> Vec<&[u8]> {
        self.owned.iter().map(|o| o.as_slice()).collect()
    }
}

/// `total` queries of which `hit_pct`% are present, interleaved by a seeded
/// shuffle so hits and misses do not arrive in runs.
fn queries(
    present: &[IndexEntry],
    absent: &[IndexEntry],
    total: usize,
    hit_pct: usize,
    label: &'static str,
    seed: u64,
) -> Queries {
    let mut rng = Rng(seed);
    let mut owned = Vec::with_capacity(total);
    let mut expected_hits = 0usize;
    for _ in 0..total {
        if (rng.next_u64() % 100) < hit_pct as u64 {
            owned.push(
                present[(rng.next_u64() as usize) % present.len()]
                    .oid
                    .clone(),
            );
            expected_hits += 1;
        } else {
            owned.push(absent[(rng.next_u64() as usize) % absent.len()].oid.clone());
        }
    }
    Queries {
        owned,
        expected_hits,
        label,
    }
}

#[inline]
fn fold_ordinals(rows: &[Option<u32>]) -> u64 {
    let mut acc = 0u64;
    for r in rows {
        if let Some(o) = r {
            acc = acc.wrapping_add(*o as u64);
        }
    }
    black_box(acc)
}

/// ns per lookup for `ordinals_batch` at one batch size. Returns the checksum so
/// the caller can prove the arms agree before quoting a timing.
///
/// `dry` runs the identical loop with the `ordinals_batch` call and nothing
/// else removed. It exists for `perf stat`, which counts a whole process: the
/// query vectors are 5–10 million small allocations and the `refs()` slice
/// rebuild is hundreds of MB, so a counter taken over the run as a whole is
/// mostly bookkeeping. `dry` is the subtrahend that leaves the lookups —
/// **and** the per-chunk result `Vec` inside them, which is genuinely part of
/// the path being measured.
fn time_ordinals(
    idx: &dyn ObjectIndex,
    q: &Queries,
    batch: usize,
    runs: usize,
    dry: bool,
) -> (Stat, u64) {
    let refs = q.refs();
    let mut samples = Vec::with_capacity(runs);
    let mut checksum = 0u64;
    for _ in 0..runs {
        let t = Instant::now();
        let mut acc = 0u64;
        let mut hits = 0usize;
        for chunk in refs.chunks(batch) {
            if dry {
                acc = acc.wrapping_add(black_box(chunk).len() as u64);
                continue;
            }
            let rows = idx.ordinals_batch(chunk);
            hits += rows.iter().filter(|r| r.is_some()).count();
            acc = acc.wrapping_add(fold_ordinals(&rows));
        }
        let ns = t.elapsed().as_nanos() as f64 / refs.len() as f64;
        if !dry {
            assert_eq!(hits, q.expected_hits, "hit count wrong at batch {batch}");
        }
        samples.push(ns);
        checksum = acc;
    }
    (Stat::of(samples), black_box(checksum))
}

// ── driver ────────────────────────────────────────────────────────────────────

fn build(entries: &[IndexEntry], layout: OidLayout, runs: usize) -> (Stat, PackedPayload) {
    let mut samples = Vec::with_capacity(runs);
    let mut last: Option<PackedPayload> = None;
    for _ in 0..runs {
        drop(last.take());
        let t = Instant::now();
        let idx = PackedPayload::build_with_oid_layout(entries, layout).expect("build");
        samples.push(t.elapsed().as_secs_f64() * 1e3);
        last = Some(idx);
    }
    (Stat::of(samples), last.unwrap())
}

fn main() {
    // S-070: agent sandboxes set PR_SET_THP_DISABLE and children inherit it, so
    // every MADV_HUGEPAGE this bench's trees issue is a silent no-op and every
    // number here was taken THP-less without saying so. Clearing the flag is a
    // per-binary decision (the library must never flip process state); this
    // binary wants real numbers, and prints which kind it got.
    let thp = znippy_zoomies::stree::thp_enable_for_process();
    eprintln!("thp_enabled={}", thp);
    let mut sizes: Vec<usize> = vec![1_000, 100_000, 1_000_000, 4_000_000];
    let mut total_queries = 100_000usize;
    let mut runs = 5usize;
    let mut oid_len = 20usize;
    let mut rot = 0usize;
    let mut only: Option<usize> = None;
    let mut dry = false;
    let mut buildruns: Option<usize> = None;
    let mut force = false;
    for a in std::env::args().skip(1) {
        let (k, v) = a.split_once('=').unwrap_or((a.as_str(), ""));
        match k {
            "sizes" => sizes = v.split(',').map(|x| x.parse().unwrap()).collect(),
            "queries" => total_queries = v.parse().unwrap(),
            "runs" => runs = v.parse().unwrap(),
            "oid" => oid_len = v.parse().unwrap(),
            "rot" => rot = v.parse::<usize>().unwrap() % 3,
            "only" => only = Some(v.parse::<usize>().unwrap() % 3),
            "dry" => dry = true,
            "buildruns" => buildruns = Some(v.parse().unwrap()),
            "force" => force = true,
            other => panic!("unknown argument `{other}`"),
        }
    }
    let active: Vec<usize> = match only {
        Some(a) => vec![a],
        None => (0..3).map(|slot| (slot + rot) % 3).collect(),
    };

    let arms = OidLayout::ALL;
    let (load1, load) = loadavg();
    println!("# stree keyspace alignment — oid→ordinal only");
    println!();
    println!("host loadavg at start: `{load}`  (1-min {load1:.2})");
    println!(
        "oid width {oid_len} B · {total_queries} lookups per timed cell · {runs} runs per cell · \
         rotation {rot} (first arm: {})",
        arms[rot % 3].name()
    );
    if load1 > 4.0 && !force {
        println!();
        println!(
            "**REFUSING TO MEASURE**: 1-minute load is {load1:.2}. oden is shared and a figure \
             taken on a busy box is worse than no figure."
        );
        std::process::exit(2);
    }

    let mut all_spreads: Vec<f64> = Vec::new();

    for &n in &sizes {
        let present = synthetic_entries(n, oid_len, 0x5EED_0001 ^ n as u64);
        let absent = synthetic_entries(n.clamp(1000, 200_000), oid_len, 0xDEAD_0002 ^ n as u64);
        let mixes = [
            queries(
                &present,
                &absent,
                total_queries,
                100,
                "100% hit (want resolution)",
                1,
            ),
            queries(
                &present,
                &absent,
                total_queries,
                10,
                "10% hit (have negotiation)",
                3,
            ),
        ];

        // Build in rotated order, so no arm is always the one that warms the
        // allocator and the TLB for the others.
        let mut built: Vec<Option<(Stat, PackedPayload)>> = (0..3).map(|_| None).collect();
        for &a in &active {
            built[a] = Some(build(&present, arms[a], buildruns.unwrap_or(runs)));
        }

        println!();
        println!("## {n} objects");
        println!();

        // LAW 2 — prove each arm sits on the cache-line phase it claims before
        // quoting any timing. Two arms on the same phase is a null result by
        // construction, and would be indistinguishable from a real one.
        let mut phases = [usize::MAX; 3];
        for &a in &active {
            let phase = built[a].as_ref().unwrap().1.keyspace_phase();
            phases[a] = phase;
            match arms[a] {
                OidLayout::Aligned64 => {
                    assert_eq!(phase, 0, "aligned64 is at phase {phase}, not 0")
                }
                OidLayout::Compact64Alloc => {
                    assert_eq!(phase, 24, "compact24+align is at phase {phase}, not 24")
                }
                OidLayout::Compact => {}
            }
        }
        if only.is_none() && !dry {
            assert_ne!(
                phases[0], phases[2],
                "compact24 and aligned64 share a phase"
            );

            // …and that the arms are the same index. Every arm's whole answer
            // vector, hits and misses, compared element for element.
            for m in &mixes {
                let refs = m.refs();
                let base = built[0].as_ref().unwrap().1.ordinals_batch(&refs);
                assert_eq!(
                    base.iter().filter(|r| r.is_some()).count(),
                    m.expected_hits,
                    "{} hit rate is not what was generated",
                    m.label
                );
                for a in 1..3 {
                    assert_eq!(
                        built[a].as_ref().unwrap().1.ordinals_batch(&refs),
                        base,
                        "{} disagrees with compact24 on the {} workload",
                        arms[a].name(),
                        m.label
                    );
                }
            }
        }

        let (_, load_here) = loadavg();
        println!("loadavg: `{load_here}`");
        println!();
        println!(
            "keyspace phase (bytes into the cache line): {}",
            active
                .iter()
                .map(|&a| format!("{}={}", arms[a].name(), phases[a]))
                .collect::<Vec<_>>()
                .join(" ")
        );
        println!();
        for &a in &active {
            let b = built[a].as_ref().unwrap();
            all_spreads.push(b.0.spread());
            println!(
                "DATA\t{n}\tbuild\tbuild_ms\t{}\t{:.6}\t{:.6}\t{:.6}",
                arms[a].name(),
                b.0.med,
                b.0.lo,
                b.0.hi
            );
        }

        for m in &mixes {
            println!();
            println!("### {n} objects · {}", m.label);
            println!();
            for &batch in &[1usize, 100, 1000] {
                let mut cells: Vec<Option<(Stat, u64)>> = (0..3).map(|_| None).collect();
                for &a in &active {
                    cells[a] = Some(time_ordinals(
                        &built[a].as_ref().unwrap().1,
                        m,
                        batch,
                        runs,
                        dry,
                    ));
                }
                if only.is_none() && !dry {
                    assert_eq!(
                        cells[0].unwrap().1,
                        cells[1].unwrap().1,
                        "batch {batch}: checksums differ"
                    );
                    assert_eq!(
                        cells[0].unwrap().1,
                        cells[2].unwrap().1,
                        "batch {batch}: checksums differ"
                    );
                }
                for &a in &active {
                    let c = cells[a].unwrap();
                    all_spreads.push(c.0.spread());
                    println!(
                        "DATA\t{n}\t{}\tbatch{batch}\t{}\t{:.6}\t{:.6}\t{:.6}",
                        m.label.split(' ').next().unwrap(),
                        arms[a].name(),
                        c.0.med,
                        c.0.lo,
                        c.0.hi
                    );
                }
            }
        }
    }

    all_spreads.sort_by(|x, y| x.partial_cmp(y).unwrap());
    let med = all_spreads[all_spreads.len() / 2];
    let p90 = all_spreads[all_spreads.len() * 9 / 10];
    let (_, load_end) = loadavg();
    println!();
    println!("## Noise band");
    println!();
    println!(
        "Across all {} timed cells, run-to-run spread `(max-min)/median` was median **{:.1}%**, \
         p90 **{:.1}%**, worst **{:.1}%**.",
        all_spreads.len(),
        med * 100.0,
        p90 * 100.0,
        all_spreads.last().unwrap() * 100.0
    );
    println!();
    println!("loadavg at end: `{load_end}`");
}