examples/ragnar_bench.rs
//! HEAVY benchmark: Ragnar-fast static index vs the linear scan, for `as_of`
//! (point-in-time) and exact lookups over a realistically large version log.
//!
//! Run (full cores, release):
//! cargo run --release --example ragnar_bench
//! Tunables (env): `RAGNAR_N` (log size), `RAGNAR_QF` (fast queries),
//! `RAGNAR_QL` (linear queries). Defaults are HEAVY.
//!
//! Prints a markdown results block and writes it to
//! `.nornir/warehouse-ragnar-benchmarks.md`.
use std::time::Instant;
use nornir::warehouse::ragnar::{LinearScan, RagnarLog};
use znippy_zoomies::gatling_forkjoin::gatling_map_owned;
fn env_usize(k: &str, d: usize) -> usize {
std::env::var(k)
.ok()
.and_then(|v| v.parse().ok())
.unwrap_or(d)
}
/// Peak resident set (VmHWM) in MiB, from /proc.
fn peak_rss_mib() -> u64 {
std::fs::read_to_string("/proc/self/status")
.ok()
.and_then(|s| {
s.lines()
.find(|l| l.starts_with("VmHWM:"))
.and_then(|l| l.split_whitespace().nth(1))
.and_then(|kb| kb.parse::<u64>().ok())
})
.map(|kb| kb / 1024)
.unwrap_or(0)
}
// Deterministic xorshift so the run is reproducible.
struct Rng(u64);
impl Rng {
#[inline]
fn next(&mut self) -> u64 {
let mut x = self.0;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.0 = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
}
fn main() {
let n = env_usize("RAGNAR_N", 20_000_000);
let qf = env_usize("RAGNAR_QF", 8_000_000);
let ql = env_usize("RAGNAR_QL", 4_000);
let cores = std::thread::available_parallelism()
.map(|n| n.get())
.unwrap_or(1);
eprintln!("building version log: {n} entries, {cores} cores…");
// A strictly increasing, gappy key space (snapshot-id / ts_micros style).
let mut rng = Rng(0x1234_5678_9ABC_DEF0);
let mut rows: Vec<(i64, i64)> = Vec::with_capacity(n);
let mut k = 1_000_000i64;
for _ in 0..n {
k += 1 + (rng.next() % 100) as i64;
rows.push((k, k ^ 0x5555_5555));
}
let key_lo = rows[0].0;
let key_hi = rows[n - 1].0;
let span = (key_hi - key_lo).max(1);
// Pre-generate the query set (shared by both paths for a fair comparison).
let mut qrng = Rng(0xC0FF_EE00_1234_5678);
let queries_f: Vec<i64> = (0..qf)
.map(|_| key_lo + (qrng.next() % span as u64) as i64)
.collect();
let queries_l: Vec<i64> = (0..ql)
.map(|_| key_lo + (qrng.next() % span as u64) as i64)
.collect();
// Build both structures.
let t = Instant::now();
let ragnar = RagnarLog::build(rows.clone());
let build_ms = t.elapsed().as_secs_f64() * 1e3;
let linear = LinearScan::build(rows);
eprintln!("built RagnarLog in {build_ms:.1} ms; running queries…");
// ── as_of (point-in-time) ────────────────────────────────────────────────
// Fast path: qf queries, parallel across all cores.
let t = Instant::now();
let fast_hits: u64 = gatling_map_owned(queries_f.clone(), |q| {
ragnar.as_of(q).map(|v| *v as u64).unwrap_or(0)
})
.into_iter()
.sum();
let fast_secs = t.elapsed().as_secs_f64();
let fast_qps = qf as f64 / fast_secs;
let fast_ns = fast_secs / qf as f64 * 1e9;
// Linear path: ql queries (each O(n)), parallel across all cores.
let t = Instant::now();
let lin_hits: u64 = gatling_map_owned(queries_l.clone(), |q| {
linear.as_of(q).map(|v| *v as u64).unwrap_or(0)
})
.into_iter()
.sum();
let lin_secs = t.elapsed().as_secs_f64();
let lin_qps = ql as f64 / lin_secs;
let lin_ns = lin_secs / ql as f64 * 1e9;
let speedup = fast_qps / lin_qps;
// ── exact lookups (Ragnar STree64) ───────────────────────────────────────
let t = Instant::now();
let exact_hits: u64 = gatling_map_owned(queries_f.clone(), |q| {
ragnar.at_exact(q).map(|v| *v as u64).unwrap_or(0)
})
.into_iter()
.sum();
let exact_secs = t.elapsed().as_secs_f64();
let exact_qps = qf as f64 / exact_secs;
let exact_ns = exact_secs / qf as f64 * 1e9;
let rss = peak_rss_mib();
// ── report ────────────────────────────────────────────────────────────────
let md = format!(
"# Warehouse Ragnar-fast — HEAVY benchmark\n\
\n\
Static search-tree (`RagnarLog`: znippy `STree64` exact + Eytzinger floor) vs the\n\
linear scan (`LinearScan`) it replaces, over the warehouse commit/version log.\n\
\n\
## Machine / run\n\
\n\
| | |\n\
|---|---|\n\
| cores | **{cores}** |\n\
| peak RSS (VmHWM) | **{rss} MiB** |\n\
| version-log entries (n) | {n} |\n\
| key span | {key_lo} … {key_hi} |\n\
| RagnarLog build time | {build_ms:.1} ms |\n\
| as-of fast queries | {qf} |\n\
| as-of linear queries | {ql} |\n\
\n\
## as-of / point-in-time lookup (the headline)\n\
\n\
| path | ns / query | queries / sec | checksum |\n\
|---|---:|---:|---:|\n\
| linear scan (`LinearScan::as_of`, O(n)) | {lin_ns:.1} | {lin_qps:.0} | {lin_hits} |\n\
| **Ragnar-fast (`RagnarLog::as_of`, O(log n))** | **{fast_ns:.1}** | **{fast_qps:.0}** | {fast_hits} |\n\
\n\
**Speedup: {speedup:.0}× faster** (throughput, full {cores} cores, same query set).\n\
\n\
## exact lookup (Ragnar `STree64`)\n\
\n\
| path | ns / query | queries / sec | checksum |\n\
|---|---:|---:|---:|\n\
| Ragnar-fast (`RagnarLog::at_exact`) | {exact_ns:.1} | {exact_qps:.0} | {exact_hits} |\n\
\n\
_HEAVY run: full cores, whole-log in RAM. Checksums are the summed payloads —\n\
they only exist to stop the optimizer eliding the work; fast and linear as-of\n\
checksums match because the two paths return identical answers (see the\n\
differential tests in `src/warehouse/ragnar.rs` and `funnel.rs`)._\n",
);
println!("{md}");
// Sanity: fast and linear must agree on the (smaller) linear query set.
let mut disagree = 0u64;
for &q in &queries_l {
if ragnar.as_of(q).copied() != linear.as_of(q).copied() {
disagree += 1;
}
}
if disagree != 0 {
eprintln!("FATAL: fast vs linear disagreed on {disagree} queries");
std::process::exit(1);
}
if let Err(e) = std::fs::write(".nornir/warehouse-ragnar-benchmarks.md", &md) {
eprintln!("note: could not write results file: {e}");
} else {
eprintln!("wrote .nornir/warehouse-ragnar-benchmarks.md");
}
}