examples/stree_lab.rs
//! stree_lab — the 2026-08-10 ragnar-brief experiment harness.
//!
//! Replicates the `__gunnar_oid__` workload shape at the zoomies level so the
//! read-only znippy repo never has to change to *measure*: a sorted random
//! i64 key column at stride 8 (exactly `GitOidIndex`'s keyspace — see
//! oid_index.rs:519 `STree64Mmap::new_with_stride(keys, count, 8)`), random
//! present-key queries, every arm verified against `binary_search` before it
//! is timed. What this deliberately omits is the full-oid verify step — it is
//! identical across arms, so ratios between arms are unaffected; absolute
//! ns/query here are therefore LOWER than the git_oid_lookup arms by the
//! verify cost (~30-60 ns at 8e6).
//!
//! Env knobs: LAB_N (keys), LAB_Q (queries), LAB_REPS (median-of), LAB_SEED.
//! Output: one `name ns_per_query` line per arm, then a summary block.
use std::hint::black_box;
use std::time::Instant;
use znippy_zoomies::stree::STree64Mmap;
use znippy_zoomies::stree512::STree512Mmap;
use znippy_zoomies::stree_hi32::STreeHi32Mmap;
use znippy_zoomies::stree_simd::SimdPath;
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 >> 12;
self.0 ^= self.0 << 25;
self.0 ^= self.0 >> 27;
self.0.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
}
fn envn(k: &str, d: usize) -> usize {
std::env::var(k).ok().and_then(|v| v.parse().ok()).unwrap_or(d)
}
#[inline]
fn id_at(data: &[u8], idx: usize) -> i64 {
i64::from_le_bytes(data[idx * 8..idx * 8 + 8].try_into().unwrap())
}
/// The oid_index::lookup_binary_search shape: same key column, same reader.
fn binsearch(data: &[u8], count: usize, key: i64) -> Option<usize> {
let mut lo = 0usize;
let mut hi = count;
while lo < hi {
let mid = lo + (hi - lo) / 2;
if id_at(data, mid) < key { lo = mid + 1 } else { hi = mid }
}
if lo < count && id_at(data, lo) == key { Some(lo) } else { None }
}
fn median(mut v: Vec<f64>) -> f64 {
v.sort_by(|a, b| a.partial_cmp(b).unwrap());
v[v.len() / 2]
}
fn main() {
// Without this the sandbox's PR_SET_THP_DISABLE makes every hugepage
// hint below a silent no-op. See stree::thp_enable_for_process.
let thp = znippy_zoomies::stree::thp_enable_for_process();
println!("# thp_enabled={thp}");
let n = envn("LAB_N", 8_000_000);
let q = envn("LAB_Q", 200_000);
let reps = envn("LAB_REPS", 5);
let seed = envn("LAB_SEED", 0x9AD1_5EED) as u64;
// Distinct sorted random keys (uniform over i64 like top-bit-flipped oids).
let mut rng = Rng(seed);
let mut keys: Vec<i64> = Vec::with_capacity(n + n / 8);
// Leaf storage on hugepages too: advise before first touch (the push /
// extend below is the first fault). One leaf touch per query — its dTLB
// miss is as real as the tree's.
znippy_zoomies::stree::advise_hugepage_raw(keys.as_ptr() as *const u8, keys.capacity() * 8);
while keys.len() < n + n / 16 {
keys.push(rng.next() as i64);
}
keys.sort_unstable();
keys.dedup();
keys.truncate(n);
assert_eq!(keys.len(), n, "not enough distinct keys generated");
let mut data: Vec<u8> = Vec::with_capacity(n * 8);
znippy_zoomies::stree::advise_hugepage_raw(data.as_ptr(), data.capacity());
for k in &keys {
data.extend_from_slice(&k.to_le_bytes());
}
let mut rq = Rng(seed ^ 0xC0FF_EE00);
let queries: Vec<i64> = (0..q).map(|_| keys[(rq.next() as usize) % n]).collect();
// Ground truth once.
let truth: Vec<Option<usize>> = queries.iter().map(|&k| binsearch(&data, n, k)).collect();
assert!(truth.iter().all(Option::is_some), "a present key missed");
let t64 = STree64Mmap::new_with_stride(&data, n, 8);
let t64_ph16 = STree64Mmap::new_with_stride_phase(&data, n, 8, 16);
let t512 = STree512Mmap::new_with_stride(&data, n, 8);
// In-RAM trees (leaf layer inside the node buffer) — the stree_* arm shape.
let ram0 = znippy_zoomies::stree::STree64::new(&keys);
let ram16 = znippy_zoomies::stree::STree64::new_phase(&keys, 16);
println!(
"# lab n={n} q={q} reps={reps} tree64_phase={} tree64_ph16_phase={} tree512_phase=0",
t64.tree_phase(),
t64_ph16.tree_phase()
);
// Did madvise(MADV_HUGEPAGE) actually get the trees onto 2 MB pages?
// (H: never verified — the hint is best-effort and THP=madvise needs it
// to succeed for the RAM-bound regime.)
if let Ok(s) = std::fs::read_to_string("/proc/self/smaps_rollup") {
for line in s.lines() {
if line.starts_with("AnonHugePages") || line.starts_with("Rss") {
println!("# smaps {}", line.split_whitespace().collect::<Vec<_>>().join(" "));
}
}
}
let per_q = |ns: f64| ns / q as f64;
let mut results: Vec<(String, f64)> = Vec::new();
macro_rules! arm {
($name:expr, $body:expr) => {{
let run = || -> Vec<Option<usize>> { $body };
// verify
let got = run();
assert_eq!(got, truth, "arm {} disagrees with binary search", $name);
// warm
black_box(run());
let mut samples = Vec::with_capacity(reps);
for _ in 0..reps {
let t = Instant::now();
black_box(run());
samples.push(t.elapsed().as_nanos() as f64);
}
let ns = per_q(median(samples));
println!("{} {:.1}", $name, ns);
results.push(($name.to_string(), ns));
}};
}
// Baselines.
arm!("binsearch", queries.iter().map(|&k| binsearch(&data, n, k)).collect());
arm!("serial64", queries.iter().map(|&k| t64.find_exact(k, &data)).collect());
// Current production path and its P sweep (two-phase sort pipeline).
arm!("pipe_p8", t64.lookup_batch_pipeline::<8>(&queries, &data));
arm!("pipe_p16", t64.lookup_batch_pipeline::<16>(&queries, &data));
arm!("pipe_p32", t64.lookup_batch_pipeline::<32>(&queries, &data));
arm!("pipe_p64", t64.lookup_batch_pipeline::<64>(&queries, &data));
// Fused single-phase (no sort, leaf prefetched) P sweep.
arm!("fused_p8", t64.lookup_batch_fused::<8>(&queries, &data));
arm!("fused_p16", t64.lookup_batch_fused::<16>(&queries, &data));
arm!("fused_p32", t64.lookup_batch_fused::<32>(&queries, &data));
arm!("fused_p64", t64.lookup_batch_fused::<64>(&queries, &data));
arm!("fused_p128", t64.lookup_batch_fused::<128>(&queries, &data));
// Hi32 routing: u32 high-half internal nodes, fanout 17, one-line nodes.
let thi = STreeHi32Mmap::new_with_stride(&data, n, 8);
arm!("hi32_serial", queries.iter().map(|&k| thi.find_exact(k, &data)).collect());
arm!("hi32_fused_p16", thi.lookup_batch_fused::<16>(&queries, &data));
arm!("hi32_fused_p32", thi.lookup_batch_fused::<32>(&queries, &data));
arm!("hi32_fused_p64", thi.lookup_batch_fused::<64>(&queries, &data));
arm!("hi32_fused_p128", thi.lookup_batch_fused::<128>(&queries, &data));
// Two-stage software pipeline: chunk k's leaf scan under chunk k+1's routing.
arm!("fused2_p32", t64.lookup_batch_fused2::<32>(&queries, &data));
arm!("fused2_p64", t64.lookup_batch_fused2::<64>(&queries, &data));
arm!("fused2_p128", t64.lookup_batch_fused2::<128>(&queries, &data));
// H4: same fused arm on a deliberately 16-byte-phased tree (the glibc
// reality the default allocation used to have).
arm!("fused_p32_ph16", t64_ph16.lookup_batch_fused::<32>(&queries, &data));
arm!("serial64_ph16", queries.iter().map(|&k| t64_ph16.find_exact(k, &data)).collect());
// In-RAM STree64 (the stree_*/OSM arm shape), aligned vs phase-16 nodes.
arm!("ram_serial", queries.iter().map(|&k| ram0.find_exact(k)).collect());
arm!("ram_stream_p32", ram0.batch_stream::<32>(&queries));
arm!("ram_stream_p64", ram0.batch_stream::<64>(&queries));
arm!("ram_stream_p128", ram0.batch_stream::<128>(&queries));
arm!("ram_stream_p128_ph16", ram16.batch_stream::<128>(&queries));
arm!("ram_serial_ph16", queries.iter().map(|&k| ram16.find_exact(k)).collect());
// H2: B=16 AVX-512 tree.
arm!("s512_serial", queries.iter().map(|&k| t512.find_exact(k, &data)).collect());
arm!("s512_fused_p8", t512.lookup_batch_fused::<8>(&queries, &data));
arm!("s512_fused_p16", t512.lookup_batch_fused::<16>(&queries, &data));
arm!("s512_fused_p32", t512.lookup_batch_fused::<32>(&queries, &data));
arm!("s512_fused_p64", t512.lookup_batch_fused::<64>(&queries, &data));
arm!("s512_fused_p128", t512.lookup_batch_fused::<128>(&queries, &data));
let bin = results[0].1;
println!("# ratios vs binsearch:");
for (name, ns) in &results {
println!("# {name}: {:.2}x", bin / ns);
}
// ── SIMD-path A/B ─────────────────────────────────────────────────────────
//
// The whole point of the runtime dispatch: one binary, N kernels. Here we
// pin each kernel in turn (`stree_simd::force`, clamped to what CPUID
// allows) and re-run the arms that matter, so the AVX-512-vs-AVX2 delta is
// measured on ONE machine in ONE process — same trees, same query vector,
// same page state. On a box without AVX-512 the avx512 rows simply do not
// appear, because `force` clamps and we skip anything above `detected()`.
//
// best-of-N, not median: we want the machine's capability, and every
// source of noise here is additive. The spread (worst/best) is printed
// beside it — a delta smaller than the spread is not a result.
println!("# ── simd path A/B ── {}", znippy_zoomies::stree_simd::describe());
let ab_reps = envn("LAB_AB_REPS", 7).max(3);
let mut ab: Vec<(String, SimdPath, f64, f64)> = Vec::new();
macro_rules! ab_arm {
($name:expr, $body:expr) => {{
for p in [SimdPath::Scalar, SimdPath::Avx2, SimdPath::Avx512] {
if p > znippy_zoomies::stree_simd::detected() {
continue;
}
assert_eq!(znippy_zoomies::stree_simd::force(p), p);
let run = || -> Vec<Option<usize>> { $body };
assert_eq!(run(), truth, "{} on {:?} disagrees", $name, p);
black_box(run()); // warm
black_box(run());
let mut s = Vec::with_capacity(ab_reps);
for _ in 0..ab_reps {
let t = Instant::now();
black_box(run());
s.push(per_q(t.elapsed().as_nanos() as f64));
}
s.sort_by(|a, b| a.partial_cmp(b).unwrap());
let (best, worst) = (s[0], s[s.len() - 1]);
println!("ab {} {} {:.2} spread={:.1}%", $name, p.as_str(), best, 100.0 * (worst - best) / best);
ab.push(($name.to_string(), p, best, 100.0 * (worst - best) / best));
}
}};
}
// Scalar is included so the dispatch itself is visible, but it is slow at
// this size; LAB_AB_SCALAR=0 drops it once that has been seen once.
ab_arm!("hi32_fused_p64", thi.lookup_batch_fused::<64>(&queries, &data));
ab_arm!("hi32_serial", queries.iter().map(|&k| thi.find_exact(k, &data)).collect());
ab_arm!("fused_p64", t64.lookup_batch_fused::<64>(&queries, &data));
ab_arm!("serial64", queries.iter().map(|&k| t64.find_exact(k, &data)).collect());
ab_arm!("ram_stream_p128", ram0.batch_stream::<128>(&queries));
ab_arm!("s512_fused_p64", t512.lookup_batch_fused::<64>(&queries, &data));
println!("# ── avx512 delta vs avx2 (negative = avx512 faster) ──");
for (name, p, best, spread) in ab.iter() {
if *p != SimdPath::Avx512 {
continue;
}
if let Some((_, _, a2, s2)) = ab.iter().find(|(n, q, _, _)| n == name && *q == SimdPath::Avx2)
{
let d = 100.0 * (best - a2) / a2;
let noise = spread.max(*s2);
let verdict = if d.abs() < noise { "WITHIN NOISE" } else if d < 0.0 { "avx512 wins" } else { "avx2 wins" };
println!("# {name}: avx2 {a2:.2} ns -> avx512 {best:.2} ns ({d:+.1}%, max spread {noise:.1}%) {verdict}");
}
}
znippy_zoomies::stree_simd::force(SimdPath::Avx512);
}