plugins/native/znippy-plugin-git/examples/oid_align_bench.rs
//! Does aligning the `stree` keyspace to the cache line make oid→ordinal
//! lookup faster? Three arms, one variable.
//!
//! ```text
//! CARGO_TARGET_DIR=~/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}`");
}