plugins/native/znippy-plugin-git/examples/index_layout_bench.rs
//! `FourTables` vs `OneTableFourColumns` vs `PackedPayload` — the measurement
//! behind [`znippy_plugin_git::index_layout`].
//!
//! ```text
//! CARGO_TARGET_DIR=~/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}`");
}