znippy-plugin-git 0.2.3

//! **What the ordinal space costs to fold, before and after S-082.**
//!
//! Before, [`crate::git_ops::Absorber::refold`] turned the flat `oids_raw`
//! buffer into TWO more per-oid `String` tables at every open: a hex
//! `Vec<String>` (ordinal → hex) and a `HashMap<String, u32>` (hex → ordinal).
//! After, neither is built: oid ⇄ ordinal is a slice and a binary search over
//! `oids_raw`, through [`crate::reach::OrdinalSpace`], which owns nothing.
//!
//! This runner builds a realistic `oids_raw` (N distinct sha1-width oids,
//! sorted — exactly the shape `refold` hands over), then measures, on the SAME
//! bytes:
//!
//! * **build**: the CPU the OLD two tables cost, against the ~0 the new view
//!   costs. This is the ~0.21 s the fold no longer spends.
//! * **lookup parity**: M random oid→ordinal lookups through the old `HashMap`
//!   and through the new binary search, asserting **the same answer every
//!   time**, and timing both so a serve-path regression would show.
//! * **resident**: the heap the two old tables held, which the flat buffer
//!   never needed a second copy of.
//!
//! It is CPU, not wall (`getrusage`), so the A/B is readable on a loaded box —
//! the loadavg of the run is printed so a number is never compared across box
//! states by accident.
//!
//! Run: `cargo run --release --example ordinal_space_open_cost -- 136000`

use std::collections::HashMap;
use std::time::{Duration, Instant};

use znippy_plugin_git::reach::OrdinalSpace;

fn cpu_self() -> Duration {
    let mut ru: libc::rusage = unsafe { std::mem::zeroed() };
    unsafe { libc::getrusage(libc::RUSAGE_SELF, &mut ru) };
    let d = |t: libc::timeval| Duration::new(t.tv_sec as u64, (t.tv_usec * 1000) as u32);
    d(ru.ru_utime) + d(ru.ru_stime)
}

fn loadavg() -> String {
    std::fs::read_to_string("/proc/loadavg")
        .map(|s| s.split_whitespace().take(3).collect::<Vec<_>>().join(" "))
        .unwrap_or_else(|_| "?".into())
}

/// splitmix64 — deterministic, so a run is reproducible.
struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }
}

const OID_LEN: usize = 20;

fn main() {
    let n: usize = std::env::args()
        .nth(1)
        .and_then(|s| s.parse().ok())
        .unwrap_or(136_000);
    let lookups: usize = 200_000;

    // Build N distinct oids, then sort into the flat buffer refold hands over.
    let mut rng = Rng(0xABCD_1234);
    let mut oids: Vec<[u8; OID_LEN]> = Vec::with_capacity(n);
    {
        use std::collections::HashSet;
        let mut seen: HashSet<[u8; OID_LEN]> = HashSet::with_capacity(n * 2);
        while oids.len() < n {
            let mut o = [0u8; OID_LEN];
            for c in o.chunks_mut(8) {
                let w = rng.next().to_le_bytes();
                let k = c.len();
                c.copy_from_slice(&w[..k]);
            }
            if seen.insert(o) {
                oids.push(o);
            }
        }
    }
    oids.sort_unstable();
    let mut oids_raw = Vec::with_capacity(n * OID_LEN);
    for o in &oids {
        oids_raw.extend_from_slice(o);
    }

    // ── OLD build: the hex Vec<String> + the HashMap<String, u32> ────────────
    let t = Instant::now();
    let c0 = cpu_self();
    let old_oids: Vec<String> = oids_raw.chunks_exact(OID_LEN).map(hex::encode).collect();
    let build_vec_cpu = cpu_self() - c0;
    let build_vec_wall = t.elapsed();

    let t = Instant::now();
    let c0 = cpu_self();
    let old_ordinal: HashMap<String, u32> = old_oids
        .iter()
        .enumerate()
        .map(|(i, o)| (o.clone(), i as u32))
        .collect();
    let build_map_cpu = cpu_self() - c0;
    let build_map_wall = t.elapsed();

    // ── NEW build: an OrdinalSpace over the same bytes ───────────────────────
    let t = Instant::now();
    let c0 = cpu_self();
    let space = OrdinalSpace::new(&oids_raw, OID_LEN);
    std::hint::black_box(&space);
    let build_new_cpu = cpu_self() - c0;
    let build_new_wall = t.elapsed();

    // ── lookup parity + timing: old HashMap vs new binary search ─────────────
    let mut rng = Rng(0xFEED_FACE);
    let qs: Vec<[u8; OID_LEN]> = (0..lookups).map(|_| oids[(rng.next() as usize) % n]).collect();

    let t = Instant::now();
    let mut sink_old = 0u64;
    for q in &qs {
        sink_old += *old_ordinal.get(hex::encode(q).as_str()).unwrap() as u64;
    }
    let lookup_old = t.elapsed();

    let t = Instant::now();
    let mut sink_new = 0u64;
    for q in &qs {
        sink_new += space.ordinal_of_raw(q).unwrap() as u64;
    }
    let lookup_new = t.elapsed();

    // The whole point: the two answers are IDENTICAL. (raw and hex both.)
    assert_eq!(sink_old, sink_new, "the binary search disagreed with the HashMap");
    for (i, q) in qs.iter().enumerate().step_by(n.max(1) / 997 + 1) {
        let old = *old_ordinal.get(hex::encode(q).as_str()).unwrap();
        assert_eq!(space.ordinal_of_raw(q), Some(old), "raw lookup {i} disagrees");
        assert_eq!(space.ordinal_of_hex(&hex::encode(q)), Some(old), "hex lookup {i} disagrees");
    }

    // ── resident: what the two old tables held on the heap ───────────────────
    // hex Vec<String>: N * (24-byte String header + 40-byte hex buffer).
    // HashMap<String, u32>: at least N * (40-byte key buffer + 24 header + 4 val),
    //   before the table's own ~1.1× slot overhead — a floor, not the peak.
    let vec_bytes = n * (std::mem::size_of::<String>() + 2 * OID_LEN);
    let map_bytes = n * (std::mem::size_of::<String>() + 2 * OID_LEN + std::mem::size_of::<u32>());
    let old_resident = vec_bytes + map_bytes;
    let new_resident = 0usize; // OrdinalSpace borrows oids_raw; oids_raw exists in both worlds.

    let ms = |d: Duration| d.as_secs_f64() * 1000.0;
    println!("load {}; N={n} oids ({} bytes flat), {lookups} lookups", loadavg(), oids_raw.len());
    println!(
        "  OLD build  hex Vec<String>: {:.2} ms cpu / {:.2} ms wall",
        ms(build_vec_cpu),
        ms(build_vec_wall)
    );
    println!(
        "  OLD build  HashMap<String,u32>: {:.2} ms cpu / {:.2} ms wall",
        ms(build_map_cpu),
        ms(build_map_wall)
    );
    println!(
        "  OLD build  TOTAL: {:.2} ms cpu / {:.2} ms wall",
        ms(build_vec_cpu + build_map_cpu),
        ms(build_vec_wall + build_map_wall)
    );
    println!(
        "  NEW build  OrdinalSpace: {:.4} ms cpu / {:.4} ms wall  (a borrow: two words)",
        ms(build_new_cpu),
        ms(build_new_wall)
    );
    println!(
        "  lookup {lookups}x  OLD HashMap: {:.2} ms   NEW binary search: {:.2} ms   ({:.2}x)",
        ms(lookup_old),
        ms(lookup_new),
        lookup_old.as_secs_f64() / lookup_new.as_secs_f64().max(1e-9)
    );
    println!(
        "  resident  OLD two tables: {} KiB (~{} B/oid)   NEW: {} KiB",
        old_resident / 1024,
        old_resident / n.max(1),
        new_resident / 1024
    );
}