crates/gunnar-delta/examples/bench.rs
//! **The measurements. Run it, do not believe it.**
//!
//! ```text
//! cargo run --release --example bench
//! cargo run --release --example bench --no-default-features # portable scan
//! ```
//!
//! Three things are measured, in the order they matter:
//!
//! 1. **the match scan**, portable against AVX2, at match lengths either side of
//! the vector width. SIMD is claimed to earn its keep here and nowhere else,
//! and that claim is worth exactly the ratio printed below;
//! 2. **one pair**, over the three shapes a real object pair takes: a small edit
//! to a large file (nearly all match extension), a shifted file (match
//! extension with a moving offset), and two unrelated files (nearly all
//! rolling hash and no match at all). The last is the encoder's worst case
//! and the honest number to quote;
//! 3. **the window search across cores**, reported as speedup against one
//! thread, because a raw objects-per-second figure at 32 threads says nothing
//! about whether the parallelism worked.
//!
//! Every figure is the fastest of repeated runs, and the input sizes are fixed
//! constants at the top so the whole example's peak memory can be read off
//! without running it.
//! # What it measured on an idle machine, 2026-08-03
//!
//! Threadripper PRO 3975WX, 32 physical cores (no SMT), AVX2, no AVX-512. Three
//! repetitions at load average 13.6, after waiting 34 minutes for the box to
//! drain — every earlier run of this file was taken at load 120 to 200 and the
//! high-thread rows were worthless.
//!
//! | threads | 1 | 2 | 4 | 8 | 16 | 32 |
//! |---|---|---|---|---|---|---|
//! | wall (ms) | 126.8 / 127.2 / 128.3 | 69.0 / 67.2 / 68.2 | 36.5 / 36.7 / 36.7 | 20.9 / 20.7 / 20.6 | 12.5 / 12.3 / 12.3 | 8.96 / 9.95 / 8.93 |
//! | speedup | 1.00× | 1.84–1.89× | 3.46–3.50× | 6.08–6.21× | 10.15–10.45× | 12.8–14.4× |
//!
//! One through sixteen reproduce inside 2%. Thirty-two spreads 11% — two runs
//! at 8.9 ms and one at 10.0 — so quote it as 12.8× to 14.4× and not as a
//! single number.
//!
//! Efficiency falls from 65% at 16 threads to about 44% at 32. The chunk supply
//! is not the limit at this corpus size (2048 objects is 128 chunks, four per
//! thread, exactly what `chunk_len` aims for), so the remaining ceiling is
//! shared memory bandwidth: the rolling hash walks the target once per candidate
//! and every anchor hit is a random probe into an index that does not fit in
//! cache. That is inferred from the shape of the curve, not measured with
//! counters.
//!
//! One pair, 4 MiB: 777 to 814 MiB/s for a small edit, 57 to 61 MiB/s for two
//! unrelated objects. 2035 of 2048 objects deltified, 96 MiB in, 0.84 MiB of
//! delta out.
//!
use std::hint::black_box;
use std::sync::atomic::AtomicBool;
use std::time::{Duration, Instant};
use gix_object::Kind;
use gunnar_delta::scan::{backend, common_prefix_len, portable};
use gunnar_delta::{delta, deltify, Object, Options};
/// Object size for the window benchmark.
///
/// Small and many, because that is the shape of a repository: a repack sees
/// hundreds of thousands of blobs and trees, not hundreds of large ones. It also
/// decides how much parallelism there is to find. A chunk is tens of objects, so
/// a corpus of a few hundred simply does not contain enough chunks to keep 32
/// cores busy, and a benchmark built that way measures its own corpus size.
const OBJ: usize = 48 * 1024;
/// Objects in the window benchmark. `OBJECTS * OBJ` is the resident corpus.
const OBJECTS: usize = 2_048;
/// Object size for the single-pair benchmarks.
const PAIR: usize = 4 * 1024 * 1024;
fn noise(seed: u64, len: usize) -> Vec<u8> {
let mut s = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
(0..len)
.map(|_| {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
(s >> 24) as u8
})
.collect()
}
/// Fastest wall time across `runs` calls to `f`.
///
/// The minimum, not the median, and deliberately. Everything that makes a run
/// slower than the code deserves (another process on the core, a migration, a
/// cold cache) is additive noise, so the fastest run is the closest estimate of
/// what the code costs when it is allowed to run. A median is the right
/// statistic for "what will a user see on a loaded box" and the wrong one for
/// "did this change make the code faster", which is the only question here.
///
/// It does not rescue the thread-scaling table: an N-thread run needs N free
/// cores *at the same moment*, and on a machine already oversubscribed that
/// simply does not happen, however many times it is repeated. Read the load
/// average printed at the end before believing that section.
fn best<T>(runs: usize, mut f: impl FnMut() -> T) -> Duration {
(0..runs)
.map(|_| {
let t = Instant::now();
black_box(f());
t.elapsed()
})
.min()
.expect("at least one run")
}
fn gib_per_s(bytes: u64, d: Duration) -> f64 {
bytes as f64 / d.as_secs_f64() / (1024.0 * 1024.0 * 1024.0)
}
fn mib_per_s(bytes: u64, d: Duration) -> f64 {
bytes as f64 / d.as_secs_f64() / (1024.0 * 1024.0)
}
fn scan_bench() {
println!("\n## match scan: {:?} vs portable\n", backend());
println!(
"{:>10} {:>12} {:>12} {:>7}",
"match len", "portable", "dispatched", "ratio"
);
let a = noise(1, 1 << 20);
for len in [16usize, 32, 64, 256, 1_024, 8_192, 65_536] {
// Two slices that agree for exactly `len` bytes and then diverge.
let x = &a[..len + 1];
let mut y = x.to_vec();
let last = y.len() - 1;
y[last] ^= 0x80;
// Enough repeats that the timer is not the thing being measured.
let reps = (1 << 24) / len.max(1);
let bytes = (reps * len) as u64;
let p = best(7, || {
let mut acc = 0usize;
for _ in 0..reps {
acc += portable::common_prefix_len(black_box(x), black_box(&y));
}
acc
});
let d = best(7, || {
let mut acc = 0usize;
for _ in 0..reps {
acc += common_prefix_len(black_box(x), black_box(&y));
}
acc
});
println!(
"{len:>10} {:>9.2} GiB/s {:>9.2} GiB/s {:>6.2}x",
gib_per_s(bytes, p),
gib_per_s(bytes, d),
p.as_secs_f64() / d.as_secs_f64()
);
}
}
fn pair_bench() {
println!("\n## one pair, {} MiB target\n", PAIR / (1024 * 1024));
println!("{:>28} {:>12} {:>10}", "shape", "throughput", "delta");
let base = noise(2, PAIR);
let mut edited = base.clone();
edited.splice(PAIR / 2..PAIR / 2 + 10, *b"CHANGED!!!");
let shifted = {
let mut v = base[PAIR / 3..].to_vec();
v.extend_from_slice(&base[..PAIR / 3]);
v
};
let unrelated = noise(3, PAIR);
for (name, target) in [
("one small edit", &edited),
("shifted by a third", &shifted),
("unrelated (worst case)", &unrelated),
] {
let d = best(5, || delta(&base, target).expect("encode"));
let size = delta(&base, target).expect("encode").len();
println!(
"{name:>28} {:>7.1} MiB/s {size:>10}",
mib_per_s(target.len() as u64, d)
);
}
}
fn window_bench() {
let total = (OBJECTS * OBJ) as u64;
println!(
"\n## window search — {OBJECTS} objects x {} KiB = {} MiB, window 10, depth 50\n",
OBJ / 1024,
total / (1024 * 1024)
);
// Near-duplicate revisions: the input a repack actually sees.
let mut seed = noise(4, OBJ);
let contents: Vec<Vec<u8>> = (0..OBJECTS)
.map(|rev| {
let stamp = format!("[rev {rev:05}]").into_bytes();
for at in (rev * 7..seed.len() - 64).step_by(3_331) {
seed.splice(at..at + stamp.len(), stamp.iter().copied());
}
let mut c = seed.clone();
c.truncate(c.len() - rev * 3);
c
})
.collect();
let objects: Vec<Object<'_>> = contents
.iter()
.enumerate()
.map(|(i, c)| {
let mut id = [0u8; 20];
id[..8].copy_from_slice(&(i as u64).to_be_bytes());
Object {
id: gix_hash::ObjectId::from(id),
kind: Kind::Blob,
name_hash: 0,
epoch: 0,
data: c.as_slice(),
}
})
.collect();
let run = |threads: usize| {
best(5, || {
deltify(
&objects,
&Options {
thread_limit: Some(threads),
..Options::default()
},
&mut gix_utils::progress::Discard,
&AtomicBool::default(),
)
.expect("deltify")
})
};
println!(
"{:>8} {:>12} {:>12} {:>9}",
"threads", "wall", "throughput", "speedup"
);
let one = run(1);
let cores = std::thread::available_parallelism().map_or(1, |n| n.get());
for threads in [1usize, 2, 4, 8, 16, 32]
.into_iter()
.filter(|&t| t == 1 || t <= cores)
{
let d = if threads == 1 { one } else { run(threads) };
println!(
"{threads:>8} {:>9.2} ms {:>7.1} MiB/s {:>8.2}x",
d.as_secs_f64() * 1e3,
mib_per_s(total, d),
one.as_secs_f64() / d.as_secs_f64()
);
}
let out = deltify(
&objects,
&Options::default(),
&mut gix_utils::progress::Discard,
&AtomicBool::default(),
)
.expect("deltify");
let delta_bytes: usize = out
.iter()
.filter_map(|d| d.data.as_ref())
.map(Vec::len)
.sum();
let whole: usize = out
.iter()
.filter(|d| !d.is_delta())
.map(|d| contents[d.source].len())
.sum();
println!(
"\n{} of {OBJECTS} deltified; {} MiB in -> {:.2} MiB out (uncompressed), {:.1}x",
out.iter().filter(|d| d.is_delta()).count(),
total / (1024 * 1024),
(delta_bytes + whole) as f64 / (1024.0 * 1024.0),
total as f64 / (delta_bytes + whole) as f64
);
}
fn main() {
println!(
"gunnar-delta bench — {} logical cores, scan backend {:?}",
std::thread::available_parallelism().map_or(0, |n| n.get()),
backend()
);
scan_bench();
pair_bench();
window_bench();
// The reader has to be able to discount every number above.
println!(
"\nload average during this run: {}",
std::fs::read_to_string("/proc/loadavg")
.unwrap_or_else(|_| "unknown\n".into())
.trim()
);
}