bench/examples/deltachain-probe.rs
//! What a delta chain costs gunnar, per link, per path, on real chains.
//!
//! # Why a separate target
//!
//! `nornir-bench.rs` is 10 000 lines with several concerns in it. This answers one
//! question — *what does resolving a chain of depth d cost, on which path* —
//! and it needs a corpus that is a real repository's pack rather than a
//! synthesised one, because the finding turns out to be about the **sizes** at
//! each depth and no synthesised chain has a real repository's size profile.
//!
//! # The corpus
//!
//! A bare repo holding one real pack, copied byte-for-byte out of a working
//! checkout — never `git clone --bare`, which silently repacks and would make
//! these depths gunnar's repacker's rather than the pushing client's.
//! Alongside it a manifest of `oid depth raw_size pack_size base_oid` parsed
//! from `git verify-pack -v`, whose parse is checked against git's own
//! `chain length = N` histogram before it is believed.
//!
//! ```text
//! deltachain-probe <corpus.git> <corpus.depths>
//! ```
//!
//! # The four paths
//!
//! * `never` — `gix_odb::Handle` with **no pack cache**, which is exactly what
//! `gunnar_store::fs::FsObjects::read` is today: `gix-odb`'s
//! `new_pack_cache` defaults to `None` (`gix-odb-0.83.0/src/cache.rs:102`)
//! and its `try_find` then passes `gix_pack::cache::Never` (`:228`).
//! * `lru` — the same store, same objects, same order, with a 64 MiB
//! `MemoryCappedHashmap`. The difference between the two IS the cost of the
//! delta base cache gunnar does not have.
//! * `header` — `try_header`, which walks entry headers without inflating the
//! payload. `ObjectStore::header` used to inflate whole chains for a type
//! byte; it was moved onto this today.
//! * `entry_copy` — `location_by_oid` + `entry_by_location`, the verbatim
//! pack-entry copy that clone and fetch serve from. It must be **flat** in
//! depth; if it is not, the copy path is resolving something it should not.
//!
//! # Why every sweep gets a fresh handle
//!
//! A cache measured by reading the same 17 objects 200 times reports its own
//! hit rate, not a workload. Each timed sweep here touches each object in the
//! bucket **once**, on a handle whose cache starts empty, which is the shape of
//! the two things that actually read: a graph walk, and a browse.
//!
//! Two orders, because locality is the cache's whole value: **pack order**
//! (what a walk over a freshly written pack tends to touch) and **random
//! order** (what a browse does).
use std::time::Instant;
use anyhow::{bail, ensure, Context, Result};
use gix_hash::ObjectId;
use gix_pack::Find as _;
/// One manifest row.
#[derive(Clone)]
struct Row {
id: ObjectId,
depth: u32,
raw: u64,
/// Raw size of the whole object at the bottom of this object's chain.
root_raw: u64,
}
/// The depths reported. The question asked was "1, 2, 4, 8, 16, 32, 50".
const BUCKETS: &[u32] = &[0, 1, 2, 4, 8, 16, 32, 50];
/// Cap on objects per bucket, so the widest bucket does not dominate wall clock.
const CAP: usize = 256;
/// Sweeps per (path, order, depth) cell. Each gets a fresh handle.
const SWEEPS: usize = 30;
fn lcg(state: &mut u64) -> u64 {
*state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
*state >> 33
}
fn open(dir: &std::path::Path, cached: bool) -> Result<gix_odb::Handle> {
open_sized(dir, if cached { 64 * 1024 * 1024 } else { 0 })
}
/// `bytes == 0` means the cache gunnar has today: none at all.
fn open_sized(dir: &std::path::Path, bytes: usize) -> Result<gix_odb::Handle> {
let mut h = gix_odb::at(dir, gix_hash::Kind::Sha1)?;
if bytes == 0 {
h.unset_pack_cache();
} else {
h.set_pack_cache(move || Box::new(gix_pack::cache::lru::MemoryCappedHashmap::new(bytes)));
}
h.prevent_pack_unload();
Ok(h)
}
fn main() -> Result<()> {
let mut args = std::env::args_os().skip(1);
let git_dir = std::path::PathBuf::from(
args.next()
.context("usage: deltachain-probe <repo.git> <depths>")?,
);
let depths = std::path::PathBuf::from(
args.next()
.context("usage: deltachain-probe <repo.git> <depths>")?,
);
// ── parse the manifest and resolve each chain's root ────────────────────
let text = std::fs::read_to_string(&depths)?;
let mut by_hex: std::collections::HashMap<&str, (u32, u64, &str)> =
std::collections::HashMap::new();
let mut order: Vec<&str> = Vec::new();
for line in text.lines() {
let f: Vec<&str> = line.split_whitespace().collect();
if f.len() < 5 {
continue;
}
by_hex.insert(f[0], (f[1].parse()?, f[2].parse()?, f[4]));
order.push(f[0]);
}
ensure!(
!by_hex.is_empty(),
"the manifest {} parsed to zero rows",
depths.display()
);
let mut rows: Vec<Row> = Vec::with_capacity(order.len());
for hex in &order {
let (depth, raw, mut base) = by_hex[hex];
let mut hops = 0u32;
let mut root_raw = raw;
while base != "-" {
let Some(&(_, braw, bbase)) = by_hex.get(base) else {
break;
};
root_raw = braw;
base = bbase;
hops += 1;
ensure!(hops <= 64, "chain from {hex} does not terminate");
}
rows.push(Row {
id: ObjectId::from_hex(hex.as_bytes()).map_err(|e| anyhow::anyhow!("{hex}: {e}"))?,
depth,
raw,
root_raw,
});
}
// ── the fixture trap, asserted rather than assumed ──────────────────────
// A corpus whose objects are not deltified answers every question 1.0x and
// looks clean doing it. A 243-byte fixture read 1.0123x straight
// through a 3-4.67x regression for exactly this reason.
let max_depth = rows.iter().map(|r| r.depth).max().unwrap_or(0);
ensure!(
max_depth >= 25,
"corpus max chain depth is {max_depth}: there is nothing here to measure. \
A `git clone --bare` fixture reads exactly like this."
);
let odb_dir = git_dir.join("objects");
let never = open(&odb_dir, false)?;
// ── measured, not asserted: prove the cached handle is actually cached ──
// `set_pack_cache` is a setter. Nothing about calling it proves the cache
// is reached, and a handle that silently ignored it would make every `lru`
// column below a second copy of the `never` column — matching numbers that
// read as agreement rather than as a bug.
{
let deepest = rows
.iter()
.max_by_key(|r| r.depth)
.cloned()
.context("non-empty")?;
let lru = open(&odb_dir, true)?;
let mut buf = Vec::new();
let twice = |h: &gix_odb::Handle, buf: &mut Vec<u8>| -> Result<(f64, f64)> {
let t0 = Instant::now();
gix_pack::Find::try_find(h, &deepest.id, buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("deepest object vanished")?;
let a = t0.elapsed().as_secs_f64();
let t1 = Instant::now();
gix_pack::Find::try_find(h, &deepest.id, buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("deepest object vanished")?;
Ok((a, t1.elapsed().as_secs_f64()))
};
let (n1, n2) = twice(&never, &mut buf)?;
let (l1, l2) = twice(&lru, &mut buf)?;
println!(
"# cache-liveness at depth {}: never {:.1}->{:.1}us lru {:.1}->{:.1}us",
deepest.depth,
n1 * 1e6,
n2 * 1e6,
l1 * 1e6,
l2 * 1e6
);
if l2 >= l1 * 0.5 {
bail!(
"the cached handle's SECOND read of a depth-{} object was not at least 2x \
faster than its first ({:.1}us -> {:.1}us). The pack cache is not being \
reached and every `lru` column would be measuring the `never` path.",
deepest.depth,
l1 * 1e6,
l2 * 1e6
);
}
}
println!(
"\n{:>5} {:>5} {:>8} {:>9} | {:>10} {:>10} {:>6} | {:>10} {:>10} {:>6} | {:>8} {:>9}",
"depth",
"n",
"meanRaw",
"meanRoot",
"packNever",
"packLru",
"x",
"randNever",
"randLru",
"x",
"header",
"entrycopy"
);
for &d in BUCKETS {
let pool: Vec<Row> = rows.iter().filter(|r| r.depth == d).cloned().collect();
if pool.is_empty() {
continue;
}
let mut seed = 0x5EED_u64 ^ u64::from(d);
// Pack order, which is the order a walk over a fresh pack tends to hit.
let mut with_off: Vec<(u64, Row)> = pool
.iter()
.map(|r| {
let off = never
.location_by_oid(&r.id, &mut Vec::new())
.ok()
.flatten()
.map_or(u64::MAX, |l| l.pack_offset);
(off, r.clone())
})
.collect();
with_off.sort_by_key(|(o, _)| *o);
with_off.truncate(CAP);
let pack_order: Vec<Row> = with_off.into_iter().map(|(_, r)| r).collect();
let mut random: Vec<Row> = pack_order.clone();
for i in (1..random.len()).rev() {
let j = (lcg(&mut seed) as usize) % (i + 1);
random.swap(i, j);
}
let n = pack_order.len();
let mean_raw = pack_order.iter().map(|r| r.raw).sum::<u64>() as f64 / n as f64;
let mean_root = pack_order.iter().map(|r| r.root_raw).sum::<u64>() as f64 / n as f64;
// One sweep = each object read once, on a handle whose cache is empty.
let sweep = |cached: bool, set: &[Row]| -> Result<f64> {
let mut best = f64::MAX;
for _ in 0..SWEEPS {
let h = open(&odb_dir, cached)?;
let mut buf = Vec::new();
let t = Instant::now();
for r in set {
gix_pack::Find::try_find(&h, &r.id, &mut buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("object vanished mid-sweep")?;
}
best = best.min(t.elapsed().as_secs_f64() / set.len() as f64);
}
Ok(best)
};
let pn = sweep(false, &pack_order)?;
let pl = sweep(true, &pack_order)?;
let rn = sweep(false, &random)?;
let rl = sweep(true, &random)?;
let hd = {
let mut best = f64::MAX;
for _ in 0..SWEEPS {
let t = Instant::now();
for r in &random {
gix_odb::Header::try_header(&never, &r.id)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("header vanished")?;
}
best = best.min(t.elapsed().as_secs_f64() / random.len() as f64);
}
best
};
let ec = {
let mut scratch = Vec::new();
let locs: Vec<_> = random
.iter()
.filter_map(|r| never.location_by_oid(&r.id, &mut scratch).ok().flatten())
.collect();
ensure!(
locs.len() == random.len(),
"only {} of {} objects at depth {d} have a pack location",
locs.len(),
random.len()
);
let mut best = f64::MAX;
let mut bytes = 0u64;
for _ in 0..SWEEPS {
let t = Instant::now();
for l in &locs {
let e = never.entry_by_location(l).context("entry vanished")?;
bytes += e.data.len() as u64;
}
best = best.min(t.elapsed().as_secs_f64() / locs.len() as f64);
}
ensure!(bytes > 0, "entry copy moved zero bytes");
best
};
println!(
"{:>5} {:>5} {:>8.0} {:>9.0} | {:>8.2}us {:>8.2}us {:>6.1} | {:>8.2}us {:>8.2}us {:>6.1} | {:>6.2}us {:>7.3}us",
d, n, mean_raw, mean_root,
pn * 1e6, pl * 1e6, pn / pl,
rn * 1e6, rl * 1e6, rn / rl,
hd * 1e6, ec * 1e6
);
}
// ── the whole-pack sweep ────────────────────────────────────────────────
//
// The per-depth table above reports 1.0x for the cache at every depth, and
// that is a property of the workload rather than of the cache: a bucket of
// objects all at depth 32 holds 256 objects on 256 DIFFERENT chains, so no
// intermediate one read produces is ever a base another needs. The cache
// can only pay where several objects of the SAME chain are read, which is
// what a graph walk does and what a same-depth sweep by construction cannot.
//
// So: every object in the pack, once, on a cold handle. That IS the walk.
{
let mut all: Vec<Row> = rows.clone();
let mut with_off: Vec<(u64, Row)> = all
.drain(..)
.map(|r| {
let off = never
.location_by_oid(&r.id, &mut Vec::new())
.ok()
.flatten()
.map_or(u64::MAX, |l| l.pack_offset);
(off, r)
})
.collect();
with_off.sort_by_key(|(o, _)| *o);
let packed: Vec<Row> = with_off.into_iter().map(|(_, r)| r).collect();
let mut shuffled = packed.clone();
let mut seed = 0xA11_u64;
for i in (1..shuffled.len()).rev() {
let j = (lcg(&mut seed) as usize) % (i + 1);
shuffled.swap(i, j);
}
let full = |cached: bool, set: &[Row]| -> Result<(f64, u64)> {
let mut best = f64::MAX;
let mut bytes = 0u64;
for _ in 0..5 {
let h = open(&odb_dir, cached)?;
let mut buf = Vec::new();
let mut b = 0u64;
let t = Instant::now();
for r in set {
let (data, _) = gix_pack::Find::try_find(&h, &r.id, &mut buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("object vanished mid-sweep")?;
b += data.data.len() as u64;
}
best = best.min(t.elapsed().as_secs_f64());
bytes = b;
}
Ok((best, bytes))
};
let (pn, bytes) = full(false, &packed)?;
let (pl, _) = full(true, &packed)?;
let (rn, _) = full(false, &shuffled)?;
let (rl, _) = full(true, &shuffled)?;
println!(
"\n# whole-pack sweep, {} objects, {:.1} MiB inflated",
packed.len(),
bytes as f64 / 1_048_576.0
);
println!(
"# pack order : never {:>8.3}s lru {:>8.3}s {:.2}x",
pn,
pl,
pn / pl
);
println!(
"# random : never {:>8.3}s lru {:>8.3}s {:.2}x",
rn,
rl,
rn / rl
);
}
// ── how big does the cache have to be ───────────────────────────────────
//
// gunnar's RSS is a headline (97 MB against gitea's 391 MB on the same
// push), and `gix-odb` builds one cache PER HANDLE, of which the pool holds
// one per concurrent operation. git's 96 MiB default is per *process* and
// git forks per connection; copying that number into a pooled server would
// multiply it by the connection count. So the useful question is not "does
// a cache help" but "what is the smallest one that gets most of the help".
{
let mut all: Vec<Row> = rows.clone();
let mut with_off: Vec<(u64, Row)> = all
.drain(..)
.map(|r| {
let off = never
.location_by_oid(&r.id, &mut Vec::new())
.ok()
.flatten()
.map_or(u64::MAX, |l| l.pack_offset);
(off, r)
})
.collect();
with_off.sort_by_key(|(o, _)| *o);
let packed: Vec<Row> = with_off.into_iter().map(|(_, r)| r).collect();
// ── FIFO against LRU, same cap, same sweep ─────────────────────────
//
// `gunnar_store::delta_cache::DeltaBaseCache` is FIFO and `std`-only;
// `gix-pack`'s `MemoryCappedHashmap` is a real LRU and costs four
// crates (`clru`, `hashbrown`, `allocator-api2`, `equivalent`,
// `foldhash` — appliance 280 -> 283, measured). Choosing the former is
// only defensible if the two land in the same place, which is a
// measurement and not an opinion.
//
// **The one gunnar-linking block in this file, and therefore the one
// thing behind a feature.** Every other measurement here is stock
// `gix-odb` / `gix-pack`, which is why `bench-stock/Cargo.toml` can
// build this same source with no gunnar crate in its dependency graph
// at all — the eighteen gunnar crates are parked under
// `parked-record/crates/` and `bench/` does not resolve without
// them. `bench/` turns `gunnar-fifo` ON by default, so the legacy build
// of this probe still prints the column it always printed.
#[cfg(feature = "gunnar-fifo")]
{
let sweep_with = |mk: &dyn Fn() -> Result<gix_odb::Handle>| -> Result<f64> {
let mut best = f64::MAX;
for _ in 0..5 {
let h = mk()?;
let mut buf = Vec::new();
let t = Instant::now();
for r in &packed {
gix_pack::Find::try_find(&h, &r.id, &mut buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("object vanished mid-sweep")?;
}
best = best.min(t.elapsed().as_secs_f64());
}
Ok(best)
};
const CAP: usize = 4 * 1024 * 1024;
let lru = sweep_with(&|| {
let mut h = gix_odb::at(&odb_dir, gix_hash::Kind::Sha1)?;
h.set_pack_cache(|| Box::new(gix_pack::cache::lru::MemoryCappedHashmap::new(CAP)));
h.prevent_pack_unload();
Ok(h)
})?;
// 🔴 The `gunnar FIFO` column is GONE, not missing.
//
// It was `gunnar_store::delta_cache::DeltaBaseCache`, gunnar's own
// FIFO delta-base cache, and it was deleted with the packfile engine
// on 2026-08-10. There is nothing to put in the column: the comparison
// was LRU-against-FIFO, and one of the two implementations no longer
// exists in the tree.
//
// It is NOT replaced by a second gix-pack cache dressed as the FIFO —
// that would print a ratio near 1.0 and read as "the two caches are
// equivalent", which is a finding, and a false one. The surviving
// column is printed alone and labelled as the only one.
println!(
"\n# 4 MiB cache, whole-pack sweep: gix-pack LRU {lru:.3}s \
(gunnar FIFO column retired: `gunnar_store::delta_cache::DeltaBaseCache` \
was deleted with the packfile engine on 2026-08-10, so there is no second \
implementation to compare against)"
);
}
println!("\n# whole-pack sweep in pack order, by delta-base-cache size");
let mut baseline = f64::NAN;
for kib in [0usize, 256, 1024, 4096, 16384, 65536] {
let mut best = f64::MAX;
for _ in 0..5 {
let h = open_sized(&odb_dir, kib * 1024)?;
let mut buf = Vec::new();
let t = Instant::now();
for r in &packed {
gix_pack::Find::try_find(&h, &r.id, &mut buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("object vanished mid-sweep")?;
}
best = best.min(t.elapsed().as_secs_f64());
}
if kib == 0 {
baseline = best;
}
println!(
"# {:>6} KiB : {:>7.3}s {:.2}x",
kib,
best,
baseline / best
);
}
}
// ── one chain, read end to end ──────────────────────────────────────────
//
// The narrowest statement about the missing cache there is: the SAME 51
// objects, base first, once each. With a cache each read is one patch on an
// already-materialised base; without one, object k re-inflates the root and
// re-applies k patches, which is the O(depth^2) git's `packfile.c:1715-1719`
// exists to avoid.
{
let deepest = rows.iter().max_by_key(|r| r.depth).context("non-empty")?;
// Walk from the tip back down to the root through the manifest, then
// reverse: that is the chain, in the order git materialises it.
let mut chain: Vec<ObjectId> = Vec::new();
{
let hex = deepest.id.to_string();
let mut cur: &str = &hex;
let mut owned: Vec<String> = vec![hex.clone()];
loop {
let Some(&(_, _, base)) = by_hex.get(cur) else {
break;
};
if base == "-" {
break;
}
owned.push(base.to_string());
cur = base;
}
for h in owned.iter().rev() {
chain.push(ObjectId::from_hex(h.as_bytes())?);
}
}
ensure!(
chain.len() >= 25,
"the longest chain resolved to {} links; the manifest's base column is not being followed",
chain.len()
);
let one = |cached: bool| -> Result<f64> {
let mut best = f64::MAX;
for _ in 0..SWEEPS {
let h = open(&odb_dir, cached)?;
let mut buf = Vec::new();
let t = Instant::now();
for id in &chain {
gix_pack::Find::try_find(&h, id, &mut buf)
.map_err(|e| anyhow::anyhow!("{e}"))?
.context("chain link vanished")?;
}
best = best.min(t.elapsed().as_secs_f64());
}
Ok(best)
};
let n = one(false)?;
let l = one(true)?;
println!(
"\n# one {}-link chain, base to tip, once each: never {:.1}us lru {:.1}us {:.1}x",
chain.len(),
n * 1e6,
l * 1e6,
n / l
);
}
Ok(())
}