crates/gunnar-bitmap/examples/bench.rs
//! What the word algebra costs, and the corpus shape that decided its design.
//!
//! ```text
//! cargo run --release --example bench -- <path-to-.bitmap>...
//! ```
//!
//! Three reports, in the order the decision needed them.
//!
//! 1. **Corpus shape.** How wide a real bitmap is in `u64` words, and how long
//! an EWAH literal run actually is. This is the number that decides the
//! question before any timing is taken: four `u64` lanes fit one AVX2
//! register, so a distribution concentrated below four lanes cannot be
//! helped by any vector unit, and one concentrated in the thousands can.
//! `gunnar-delta`'s `scan.rs` reverted a SIMD repair that won its
//! microbenchmark and lost on the encoder, because the microbenchmark was
//! measuring a case the encoder does not have. This report is how that
//! mistake is avoided rather than repeated.
//!
//! 2. **Microbenchmark** of the word loop over a sweep of lengths.
//!
//! 3. **The real path**: `Reachability::objects_to_send` over every commit pair
//! the corpus offers. This is the arm the AVX2 A/B was run on, by building
//! the crate two ways and alternating the binaries back to back under
//! `taskset`; `src/words.rs` carries the result and the reason it lost.
//!
//! Timings are printed here and persisted to nornir's `bench_runs` by the arm in
//! `bench/examples/nornir-bench.rs`, never to criterion.
use gunnar_bitmap::{words, Chunk, Index, Reachability};
use std::time::Instant;
fn main() {
let paths: Vec<String> = std::env::args().skip(1).collect();
if paths.is_empty() {
eprintln!("usage: bench <path-to-.bitmap>...");
std::process::exit(2);
}
println!("{} files", paths.len());
let mut indexes = Vec::new();
for path in &paths {
let Ok(data) = std::fs::read(path) else {
continue;
};
// The header checksum width follows the repository hash and nothing in
// the file records which; a wrong guess fails to parse rather than
// silently succeeding. Same two-try shape as `decode_real`.
let index = match Index::from_bytes(&data, gix_hash::Kind::Sha1) {
Ok(i) => i,
Err(_) => match Index::from_bytes(&data, gix_hash::Kind::Sha256) {
Ok(i) => i,
Err(_) => continue,
},
};
indexes.push((path.clone(), index));
}
if indexes.is_empty() {
eprintln!("no .bitmap file parsed; nothing to measure");
std::process::exit(2);
}
corpus_shape(&indexes);
micro();
real_path(&indexes);
}
/// Report 1 — the distribution that decides the question.
fn corpus_shape(indexes: &[(String, Index)]) {
// Buckets by lane count, against the AVX2 register width of 4 `u64`.
const EDGES: [usize; 8] = [1, 2, 4, 8, 32, 128, 1024, usize::MAX];
let mut runs = [0u64; 8];
let mut run_lanes = [0u64; 8];
let mut total_runs = 0u64;
let mut total_lanes = 0u64;
let mut widths: Vec<usize> = Vec::new();
let mut entries = 0u64;
for (_, index) in indexes {
for entry in index.entries() {
entries += 1;
widths.push(entry.bitmap.word_len());
for chunk in entry.bitmap.chunks() {
if let Chunk::Literals(lit) = chunk {
if lit.is_empty() {
continue;
}
let b = EDGES
.iter()
.position(|&e| lit.len() <= e)
.expect("last edge is MAX");
runs[b] += 1;
run_lanes[b] += lit.len() as u64;
total_runs += 1;
total_lanes += lit.len() as u64;
}
}
}
}
widths.sort_unstable();
let pct = |p: usize| widths.get(widths.len() * p / 100).copied().unwrap_or(0);
println!("\n-- corpus shape --");
println!("commit bitmaps: {entries}");
println!(
"bitmap width in u64 words: p50 {} p90 {} p99 {} max {}",
pct(50),
pct(90),
pct(99),
widths.last().copied().unwrap_or(0)
);
println!("\nEWAH literal runs, by length in u64 lanes (AVX2 register = 4 lanes):");
println!(
"{:>12} {:>10} {:>7} {:>12} {:>7}",
"lanes", "runs", "% runs", "lanes", "% lanes"
);
let mut lo = 1usize;
for (i, &hi) in EDGES.iter().enumerate() {
if runs[i] == 0 && run_lanes[i] == 0 {
lo = hi.saturating_add(1);
continue;
}
let label = if hi == usize::MAX {
format!(">{}", EDGES[i - 1])
} else {
format!("{lo}..={hi}")
};
println!(
"{label:>12} {:>10} {:>6.1}% {:>12} {:>6.1}%",
runs[i],
100.0 * runs[i] as f64 / total_runs.max(1) as f64,
run_lanes[i],
100.0 * run_lanes[i] as f64 / total_lanes.max(1) as f64,
);
lo = hi.saturating_add(1);
}
let short: u64 = runs[..3].iter().sum();
let short_lanes: u64 = run_lanes[..3].iter().sum();
println!(
"\nruns too short to fill one AVX2 register (<4 lanes): {}/{} = {:.1}% of runs, \
{:.1}% of lanes",
short,
total_runs,
100.0 * short as f64 / total_runs.max(1) as f64,
100.0 * short_lanes as f64 / total_lanes.max(1) as f64,
);
}
/// Report 2 — what the portable loop costs at a sweep of lengths.
///
/// The AVX2 column this table used to carry is gone with that backend; the
/// figures it produced are recorded in `src/words.rs` so the comparison does not
/// have to be re-run to be believed.
fn micro() {
println!("\n-- microbenchmark: Op::Or over one array --");
println!("{:>10} {:>15} {:>14}", "lanes", "per call", "per lane");
for &len in &[1usize, 2, 4, 8, 16, 64, 256, 1024, 8192, 65536] {
let src: Vec<u64> = (0..len as u64)
.map(|i| i.wrapping_mul(0x9E37_79B9_7F4A_7C15))
.collect();
let mut d: Vec<u64> = (0..len as u64)
.map(|i| i.wrapping_mul(0xBF58_476D_1CE4_E5B9))
.collect();
// Roughly equal total work at each length, and enough repetitions that
// the total is well above timer resolution.
let reps = ((1usize << 22) / len.max(1)).max(16);
let ns = time(reps, || {
words::apply(words::Op::Or, &mut d, &src);
std::hint::black_box(&d);
});
println!("{len:>10} {ns:>12.2} ns {:>11.3} ns", ns / len as f64);
}
}
/// Report 3 — the real serving path, one build's half of the A/B.
fn real_path(indexes: &[(String, Index)]) {
println!("\n-- real path: Reachability::objects_to_send --");
let mut queries = 0u64;
let mut objects = 0u64;
let start = Instant::now();
for (_, index) in indexes {
let reach = Reachability::new(index);
let positions: Vec<u32> = index.commit_index_positions().collect();
if positions.len() < 2 {
continue;
}
// Every adjacent pair, in both directions: the near-neighbour shape a
// fetch has, taken both ways so neither direction is the one chosen
// because it flatters the answer.
for pair in positions.windows(2) {
let s = reach.objects_to_send([pair[1]], [pair[0]]);
objects += s.objects.count_ones();
let s = reach.objects_to_send([pair[0]], [pair[1]]);
objects += s.objects.count_ones();
queries += 2;
}
}
let elapsed = start.elapsed();
println!("queries : {queries}");
// Printed so the two builds of the A/B can be checked to have done the same
// work. A faster build that selected fewer objects is not a faster build.
println!("objects selected : {objects}");
println!("total : {:.3} ms", elapsed.as_secs_f64() * 1e3);
println!(
"per query : {:.3} us",
elapsed.as_secs_f64() * 1e6 / queries.max(1) as f64
);
}
/// Best-of-five mean nanoseconds per iteration.
///
/// Best-of rather than mean-of: the box this runs on is shared, and a run that
/// lost its core to another lane is measuring the scheduler. The minimum is the
/// closest available estimate of the uncontended cost.
fn time(reps: usize, mut f: impl FnMut()) -> f64 {
let mut best = f64::INFINITY;
for _ in 0..5 {
let start = Instant::now();
for _ in 0..reps {
f();
}
let ns = start.elapsed().as_secs_f64() * 1e9 / reps as f64;
best = best.min(ns);
}
best
}