znippy-plugin-git 0.1.1

//! `FourTables` vs `OneTableFourColumns` vs `PackedPayload` — the measurement
//! behind [`znippy_plugin_git::index_layout`].
//!
//! ```text
//! CARGO_TARGET_DIR=/home/rickard/scratch/cargo/znippy-plugin-git-indexlayout \
//!   cargo run --release --no-default-features --example index_layout_bench
//! ```
//!
//! Arguments (all optional, `key=value`):
//!   `sizes=1000,100000,1000000`   object counts to sweep
//!   `queries=100000`              lookups per timed run (constant across batch
//!                                 sizes, so ns/lookup is comparable)
//!   `runs=5`                      timed runs per cell; the spread across them
//!                                 IS the noise band
//!   `oid=20`                      20 (sha1) or 32 (sha256)
//!   `rot=0|1|2`                   which arm is timed first in every cell
//!
//! ## The three arms, and what actually differs between them
//!
//! | arm | payload columns | buffers touched by a full-row fetch |
//! |---|---:|---:|
//! | `FourTables` | 5, in 4 IPC sections | 5 |
//! | `OneTableFourColumns` | 5, in 1 IPC section | 5 |
//! | `PackedPayload` | **1**, in 1 IPC section | **1** |
//!
//! The arm names count sections and tables — the variable under test. Both
//! columnar arms carry five payload columns since `delta_base` (PLAN §13)
//! joined the schema, and the packed record is 33 bytes rather than 25.
//!
//! The first two differ in table count and agree in **column** count, which is
//! why they tied. The variable that a full-row fetch can actually feel is the
//! number of columns, and only the third arm changes it.
//!
//! ## The access patterns, and which real call site each one is
//!
//! * **`ordinals` — the floor.** oid → ordinal and stop; no payload byte is
//!   read. Identical code in all three arms (the same shared `stree`), so it
//!   measures the part no layout can change. Every other pattern minus this is
//!   the payload cost, which is the only thing under comparison. Without it a
//!   tie is unreadable: it could mean the layouts are equivalent, or it could
//!   mean the harness never touched a payload byte.
//! * **`full row` — all five facts.** `want`/`have` resolution, which needs the
//!   type and the size to decide what to send, and receive-pack, which needs the
//!   delta base. Row-shaped: `PackedPayload` should win.
//! * **`extents` — offset and len only.** The wire path about to copy bytes out
//!   of a pack. Two of five columns, so the columnar arms read less than they
//!   do for a full row and the packed arm reads exactly the same 33 bytes.
//! * **`sum sizes` — one 8-byte fact across every row.** The quota gate. Column
//!   shaped: `PackedPayload` should lose, dragging 33 bytes through cache per 8
//!   it uses.
//! * **`count type` — one *byte* across every row.** The most column-shaped
//!   query there is, and where the packed arm should lose worst: 33 bytes
//!   touched per 1 used.
//!
//! Hit-rate mixes matter because a `have` negotiation is mostly misses, and a
//! miss stops in the stree and never reads a payload column at all.
//!
//! ## Method
//!
//! * **Every returned fact is folded into a black-boxed sink** and the sink is
//!   compared across arms before any timing is quoted. A harness that discarded
//!   the row would be measuring the stree and nothing else.
//! * **Constant query budget.** Every cell performs the same number of lookups;
//!   only the batch they arrive in changes.
//! * **Position is cancelled by rotation.** Whichever arm is timed first pays
//!   the cold TLB for the others, worth a couple of per cent. The sweep is run
//!   three times with the arm order rotated, so each arm occupies each position
//!   exactly once, and the reported ratio is the geometric mean over the three.
//! * **`/proc/loadavg` with every figure**, and the run refuses to start above
//!   1-minute load 4.0. oden is shared; a figure from a busy box is worse than
//!   no figure.
//!
//! Single-threaded on purpose: this is a memory-layout question and a fan-out
//! would measure the scheduler. (No rayon here or anywhere — LAW 3; the fan-out
//! primitive in this tree is `gatling`, and it is not needed.)

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

use znippy_plugin_git::index_layout::{
    FourTables, IndexEntry, IndexRow, ObjType, ObjectIndex, OneTableFourColumns, PackedPayload,
    Rng, synthetic_entries,
};

// ── 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())
}

/// Resident set size in bytes, from `/proc/self/statm` field 2 (resident pages).
fn rss_bytes() -> u64 {
    let s = std::fs::read_to_string("/proc/self/statm").unwrap_or_default();
    let pages: u64 = s.split_whitespace().nth(1).and_then(|x| x.parse().ok()).unwrap_or(0);
    pages * 4096
}

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

/// Median, min and max of a sample. The **spread** `(max-min)/median` is the
/// noise band, and no difference smaller than it is claimed anywhere.
#[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] }
    }

    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 oids, interleaved by a
/// seeded shuffle so hits and misses are not in runs — a run of hits would let
/// the prefetcher carry the payload read for the next one.
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 }
}

/// Fold **every** fact of every returned row into one number.
///
/// This is the sink that makes the comparison mean anything. It reads all five
/// facts plus the ordinal, the result is `black_box`ed so the optimiser cannot
/// prove it dead, and the value is compared across arms before any timing is
/// reported — so an arm that returned the right number of `Some`s with wrong
/// contents fails loudly rather than benchmarking well.
#[inline]
fn fold(rows: &[Option<IndexRow>]) -> u64 {
    let mut acc = 0u64;
    for r in rows {
        if let Some(r) = r {
            acc = acc
                .wrapping_add(r.offset)
                .wrapping_add(r.len)
                .wrapping_add(r.uncompressed_size)
                .wrapping_add(r.obj_type.code() as u64)
                .wrapping_add(r.delta_base)
                .wrapping_add(r.ordinal as u64);
        }
    }
    black_box(acc)
}

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

#[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)
}

// ── the timed cells ───────────────────────────────────────────────────────────

/// Which access pattern a cell measures.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Path {
    /// oid → ordinal only. The floor.
    Ordinals(usize),
    /// All five facts, at this batch size.
    FullRow(usize),
    /// Serial `lookup`, one oid per call, all five facts.
    Serial,
    /// Offset + len only, at this batch size.
    Extents(usize),
}

impl Path {
    fn label(&self) -> String {
        match self {
            Path::Ordinals(b) => format!("ordinals only, batch {b}"),
            Path::FullRow(b) => format!("full row, batch {b}"),
            Path::Serial => "full row, serial lookup".to_string(),
            Path::Extents(b) => format!("extents only, batch {b}"),
        }
    }
}

fn time_build<I: ObjectIndex>(entries: &[IndexEntry], runs: usize) -> (Stat, I, u64, usize) {
    let mut samples = Vec::with_capacity(runs);
    let mut last: Option<I> = None;
    let mut rss_delta = 0u64;
    for r in 0..runs {
        drop(last.take());
        let before = rss_bytes();
        let t = Instant::now();
        let idx = I::build(entries).expect("build");
        samples.push(t.elapsed().as_secs_f64() * 1e3); // ms
        // First build only: by the second the allocator hands back a same-sized
        // freed region and the delta reads ~0. Even the first is
        // allocator-dependent; `resident_bytes()` is the exact figure.
        if r == 0 {
            rss_delta = rss_bytes().saturating_sub(before);
        }
        last = Some(idx);
    }
    let idx = last.unwrap();
    let resident = idx.resident_bytes();
    (Stat::of(samples), idx, rss_delta, resident)
}

/// ns per lookup for one access pattern. Returns the checksum so the caller can
/// prove the arms agree before quoting the timing.
fn time_path(idx: &dyn ObjectIndex, q: &Queries, path: Path, runs: usize) -> (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;
        match path {
            Path::Serial => {
                for o in &refs {
                    if let Some(r) = idx.lookup(o) {
                        hits += 1;
                        acc = acc.wrapping_add(fold(&[Some(r)]));
                    }
                }
            }
            Path::FullRow(b) => {
                for chunk in refs.chunks(b) {
                    let rows = idx.lookup_batch(chunk);
                    hits += rows.iter().filter(|r| r.is_some()).count();
                    acc = acc.wrapping_add(fold(&rows));
                }
            }
            Path::Extents(b) => {
                for chunk in refs.chunks(b) {
                    let rows = idx.extents_batch(chunk);
                    hits += rows.iter().filter(|r| r.is_some()).count();
                    acc = acc.wrapping_add(fold_extents(&rows));
                }
            }
            Path::Ordinals(b) => {
                for chunk in refs.chunks(b) {
                    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;
        assert_eq!(hits, q.expected_hits, "{} hit count wrong on {}", idx.name(), path.label());
        samples.push(ns);
        checksum = acc;
    }
    (Stat::of(samples), black_box(checksum))
}

/// ns per row for a full column scan.
fn time_scan(idx: &dyn ObjectIndex, sizes: bool, runs: usize) -> (Stat, u64) {
    let mut samples = Vec::with_capacity(runs);
    let mut checksum = 0u64;
    for _ in 0..runs {
        let t = Instant::now();
        let v = if sizes {
            idx.sum_uncompressed()
        } else {
            idx.count_type(ObjType::Blob) as u64
        };
        let v = black_box(v);
        samples.push(t.elapsed().as_nanos() as f64 / idx.len() as f64);
        checksum = v;
    }
    (Stat::of(samples), checksum)
}

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

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];
    let mut total_queries = 100_000usize;
    let mut runs = 5usize;
    let mut oid_len = 20usize;
    let mut force = false;
    let mut rot = 0usize;
    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,
            "force" => force = true,
            other => panic!("unknown argument `{other}`"),
        }
    }

    let (load1, load) = loadavg();
    println!("# FourTables vs OneTableFourColumns vs PackedPayload");
    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}"
    );
    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, 50, "50% hit (mixed)", 2),
            queries(&present, &absent, total_queries, 10, "10% hit (have negotiation)", 3),
        ];

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

        // Build every arm, in rotated order.
        let mut a: Option<(Stat, FourTables, u64, usize)> = None;
        let mut b: Option<(Stat, OneTableFourColumns, u64, usize)> = None;
        let mut c: Option<(Stat, PackedPayload, u64, usize)> = None;
        for slot in 0..3 {
            match (slot + rot) % 3 {
                0 => a = Some(time_build::<FourTables>(&present, runs)),
                1 => b = Some(time_build::<OneTableFourColumns>(&present, runs)),
                _ => c = Some(time_build::<PackedPayload>(&present, runs)),
            }
        }
        let (a_build, a, a_rss, a_res) = a.unwrap();
        let (b_build, b, b_rss, b_res) = b.unwrap();
        let (c_build, c, c_rss, c_res) = c.unwrap();
        assert_eq!(a.len(), n);
        assert_eq!(b.len(), n);
        assert_eq!(c.len(), n);

        // LAW 2 for the bench itself: prove the three arms are the same index on
        // this exact workload before quoting a single timing.
        for m in &mixes {
            let refs = m.refs();
            let ra = a.lookup_batch(&refs);
            let rb = b.lookup_batch(&refs);
            let rc = c.lookup_batch(&refs);
            assert_eq!(ra, rb, "A and B disagree on the {} workload", m.label);
            assert_eq!(ra, rc, "A and C disagree on the {} workload", m.label);
            assert_eq!(
                ra.iter().filter(|r| r.is_some()).count(),
                m.expected_hits,
                "{} hit rate is not what was generated",
                m.label
            );
        }
        assert_eq!(a.sum_uncompressed(), c.sum_uncompressed(), "scan answers differ");
        assert_eq!(a.count_type(ObjType::Blob), c.count_type(ObjType::Blob));

        let (_, load_here) = loadavg();
        println!("loadavg: `{load_here}`");
        println!();
        println!("| figure | FourTables | OneTableFourColumns | PackedPayload |");
        println!("|---|---:|---:|---:|");
        println!(
            "| build (ms, median of {runs}) | {:.2} | {:.2} | {:.2} |",
            a_build.med, b_build.med, c_build.med
        );
        println!(
            "| IPC + stree resident (MiB) | {:.4} | {:.4} | {:.4} |",
            a_res as f64 / 1048576.0,
            b_res as f64 / 1048576.0,
            c_res as f64 / 1048576.0
        );
        println!(
            "| RSS delta, first build (MiB) | {:.2} | {:.2} | {:.2} |",
            a_rss as f64 / 1048576.0,
            b_rss as f64 / 1048576.0,
            c_rss as f64 / 1048576.0
        );
        for s in [a_build.spread(), b_build.spread(), c_build.spread()] {
            all_spreads.push(s);
        }

        // ── column scans, mix-independent ──────────────────────────────────
        println!();
        println!("### {n} objects · column scans (ns per row)");
        println!();
        println!("| scan | A | B | C | C/B | band |");
        println!("|---|---:|---:|---:|---:|---:|");
        for (want_sizes, name) in [(true, "sum sizes (8 B/row used)"), (false, "count type (1 B/row used)")]
        {
            let mut sa = None;
            let mut sb = None;
            let mut sc = None;
            for slot in 0..3 {
                match (slot + rot) % 3 {
                    0 => sa = Some(time_scan(&a, want_sizes, runs)),
                    1 => sb = Some(time_scan(&b, want_sizes, runs)),
                    _ => sc = Some(time_scan(&c, want_sizes, runs)),
                }
            }
            let ((sa, ka), (sb, kb), (sc, kc)) = (sa.unwrap(), sb.unwrap(), sc.unwrap());
            assert_eq!(ka, kb, "scan `{name}`: A and B disagree on the answer");
            assert_eq!(ka, kc, "scan `{name}`: A and C disagree on the answer");
            let band = sa.spread().max(sb.spread()).max(sc.spread());
            for s in [sa.spread(), sb.spread(), sc.spread()] {
                all_spreads.push(s);
            }
            println!(
                "| {name} | {:.3} | {:.3} | {:.3} | {:.2} | {:.1}% |",
                sa.med,
                sb.med,
                sc.med,
                sc.med / sb.med,
                band * 100.0
            );
        }

        // ── lookup paths, per hit-rate mix ─────────────────────────────────
        let paths = [
            Path::Ordinals(1000),
            Path::Serial,
            Path::FullRow(1),
            Path::FullRow(100),
            Path::FullRow(1000),
            Path::FullRow(10000),
            Path::Extents(1000),
        ];
        for m in &mixes {
            println!();
            println!("### {n} objects · {}", m.label);
            println!();
            println!("| path | A ns | B ns | C ns | C/B | band |");
            println!("|---|---:|---:|---:|---:|---:|");
            for &p in &paths {
                let mut ra = None;
                let mut rb = None;
                let mut rc = None;
                for slot in 0..3 {
                    match (slot + rot) % 3 {
                        0 => ra = Some(time_path(&a, m, p, runs)),
                        1 => rb = Some(time_path(&b, m, p, runs)),
                        _ => rc = Some(time_path(&c, m, p, runs)),
                    }
                }
                let ((ta, ka), (tb, kb), (tc, kc)) = (ra.unwrap(), rb.unwrap(), rc.unwrap());
                assert_eq!(ka, kb, "{}: A and B checksums differ", p.label());
                assert_eq!(ka, kc, "{}: A and C checksums differ", p.label());
                let band = ta.spread().max(tb.spread()).max(tc.spread());
                for s in [ta.spread(), tb.spread(), tc.spread()] {
                    all_spreads.push(s);
                }
                println!(
                    "| {} | {:.1} | {:.1} | {:.1} | {:.3} | {:.1}% |",
                    p.label(),
                    ta.med,
                    tb.med,
                    tc.med,
                    tc.med / tb.med,
                    band * 100.0
                );
            }
        }
    }

    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}`");
}