crates/storage-git-gix/parked-gix-2/gunnar-wire-gix/tests/bitmap_cost.rs
//! What a fetch costs the object store, with a `.bitmap` and without it.
//!
//! # Why this counts store touches and not milliseconds
//!
//! Because the box this runs on carried a load average between 60 and 135 all
//! day, and a wall clock on such a box measures the box. A store touch is the
//! same number on an idle machine and a wedged one, and it is the quantity the
//! claim is actually about: "exclusion is `O(client history)`" is a statement
//! about how many objects the server opens to answer a fetch, not about how
//! long it takes to open them.
//!
//! The same reasoning `connectivity_cost.rs` and `want_cost.rs` already record,
//! and the same instrument (LAW 5) — `common::Counting`, now generic over the
//! store it wraps so it can sit on top of a real `FsObjects` with a real pack
//! and a real `.bitmap` under it.
//!
//! # The three configurations, all on one binary
//!
//! `Exclusion::from_env` and `Bitmaps::from_env` are read per request, so the
//! A/B needs no second build and no second binary — which matters, because two
//! builds is two chances to measure the wrong one.
//!
//! | | how the client's history is excluded |
//! |---|---|
//! | `GUNNAR_BITMAP=off GUNNAR_EXCLUSION=edges` | the shipping walk: the client's tips and the edge, and nothing deeper |
//! | `GUNNAR_BITMAP=off GUNNAR_EXCLUSION=full` | the exact walk: every commit the client holds, and every root tree |
//! | bitmap on | one `OR` per `have`, then one `AND NOT` |
//!
//! The middle row is the one the bitmap replaces *exactly*: it and the bitmap
//! answer the same object set (`src/bitmap.rs`'s tests assert it), so the ratio
//! between them is the honest price of exactness. The top row is what ships
//! today, and it is cheaper than the middle only because it is approximate.
mod common;
use std::path::{Path, PathBuf};
use std::sync::Arc;
use common::Counting;
use gix_hash::{Kind, ObjectId};
use gunnar_store::fs::FsStore;
use gunnar_store::{RefStore, RepackOptions, Target};
use gunnar_wire::upload_pack::FetchRequest;
use gunnar_wire::UploadPack;
fn git(dir: &Path, args: &[&str]) -> String {
let out = std::process::Command::new("git")
.current_dir(dir)
.args(args)
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.env("GIT_CONFIG_SYSTEM", "/dev/null")
.output()
.expect("run git");
assert!(
out.status.success(),
"git {args:?}: {}",
String::from_utf8_lossy(&out.stderr)
);
String::from_utf8_lossy(&out.stdout).into_owned()
}
/// A bare repository of `commits` commits with a `.bitmap`.
///
/// Over git's `MUST_REGION` of 100 on purpose: below it every commit is stored
/// and the client's history is always one `OR` away, which is the easy case and
/// not the one the claim is about.
fn bitmapped(commits: usize) -> (tempfile::TempDir, PathBuf) {
let dir = tempfile::tempdir().expect("tempdir");
let work = dir.path().join("work");
std::fs::create_dir_all(&work).expect("mkdir");
git(&work, &["init", "--quiet", "--initial-branch=main"]);
git(&work, &["config", "user.email", "t@example.invalid"]);
git(&work, &["config", "user.name", "t"]);
for i in 0..commits {
std::fs::write(work.join(format!("f{}", i % 11)), format!("{i}\n")).expect("write");
git(&work, &["add", "-A"]);
// Dates pinned, one hour apart, and this is not tidiness. Without it
// every commit carries the same second, git's `date_compare` ties, and
// both the bitmap's commit *selection* and the merged walk's ordering
// fall out differently on every run. MEASURED before pinning: the same
// request cost 213 store touches on one run and 58 on the next. A
// number that is not reproducible is not a measurement.
let at = 1_700_000_000i64 + i as i64 * 3600;
std::process::Command::new("git")
.current_dir(&work)
.args(["commit", "--quiet", "-m", &format!("c{i}")])
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.env("GIT_CONFIG_SYSTEM", "/dev/null")
.env("GIT_AUTHOR_DATE", format!("@{at} +0000"))
.env("GIT_COMMITTER_DATE", format!("@{at} +0000"))
.output()
.expect("run git");
}
let git_dir = dir.path().join("repo.git");
git(
dir.path(),
&[
"clone",
"--quiet",
"--bare",
work.to_str().unwrap(),
git_dir.to_str().unwrap(),
],
);
let store = FsStore::open_or_init(&git_dir, Kind::Sha1).expect("open");
let outcome = store.repack(&RepackOptions::new()).expect("repack");
assert!(
outcome.bitmap.is_some(),
"the fixture got no .bitmap, so every number below would be the walk twice"
);
drop(store);
(dir, git_dir)
}
/// One fetch, and how many objects the server opened to answer it.
fn touches(
git_dir: &Path,
want: ObjectId,
haves: &[ObjectId],
bitmap: bool,
exclusion: &str,
) -> usize {
// Read per request, so one process can ask all three ways. This test binary
// runs its cases one at a time for exactly that reason.
std::env::set_var("GUNNAR_BITMAP", if bitmap { "on" } else { "off" });
std::env::set_var("GUNNAR_EXCLUSION", exclusion);
let store = FsStore::open_or_init(git_dir, Kind::Sha1).expect("open");
let counting = Arc::new(Counting::new(store.objects()));
let refs = store.refs();
let request = FetchRequest {
wants: vec![want],
haves: haves.to_vec(),
done: true,
thin_pack: true,
ofs_delta: true,
..Default::default()
};
let upload = UploadPack::new(counting.as_ref(), &refs);
counting.reset();
let mut out = Vec::new();
upload.fetch(&request, &mut out).expect("the fetch");
let touched = counting.touches();
assert!(
touched > 0,
"a fetch that touched the store zero times is not measuring a fetch"
);
touched
}
fn head_and_history(git_dir: &Path) -> (ObjectId, Vec<ObjectId>) {
let head =
ObjectId::from_hex(git(git_dir, &["rev-parse", "HEAD"]).trim().as_bytes()).expect("oid");
let history: Vec<ObjectId> = git(git_dir, &["rev-list", "HEAD"])
.lines()
.map(|line| ObjectId::from_hex(line.trim().as_bytes()).expect("oid"))
.collect();
(head, history)
}
/// **The measurement.** The walk pays for the client's history; the bitmap pays
/// for the answer.
///
/// # What the first run of this test corrected
///
/// It was written asserting that the walk's cost climbs as the client falls
/// further behind. That is the wrong axis and the assertion said so. MEASURED
/// oden 2026-08-04, 400 commits over 11 files, store touches per fetch:
///
/// | client | sent | walk `edges` (ships) | walk `full` (exact) | bitmap |
/// |---|---|---|---|---|
/// | 10 commits behind | 10 commits | 48 | **1598** | **18** |
/// | 350 commits behind | 350 commits | 1068 | 1258 | 508 |
///
/// The exact walk costs **more** to serve a client that is nearly up to date
/// than one 35× further behind, because what it opens is the client's history
/// and the nearly-up-to-date client has almost all of it. That is
/// `O(client history)` as a measurement rather than as a complexity class, and
/// it is the pathology itself, not a detail of it.
///
/// The bitmap inverts it back: 18 touches to send 10 commits, 508 to send 350.
/// Cost tracks the answer, which is the only thing it should ever have tracked.
///
/// # Read both ratios, not the flattering one
///
/// Against the **exact** walk it reproduces, the bitmap is 88.8× cheaper on the
/// near client. Against the walk that actually **ships** — which is cheap
/// because it is approximate and knowingly re-sends a little — it is 2.7×.
/// Both are true and the second is the one an operator feels today. What the
/// first buys is that the approximation is no longer needed at all.
///
/// # The red condition
///
/// The **crossing** is asserted, not a ratio. A ratio can be satisfied by two
/// numbers that are both wrong; two costs that move in opposite directions
/// across the same pair of requests cannot be produced by a walk that is
/// secretly still walking, nor by a bitmap that is secretly still excluded by
/// one. The floor (`touched > 0`) closes the third case.
#[test]
fn the_walk_pays_for_the_clients_history_and_the_bitmap_does_not() {
let (_dir, git_dir) = bitmapped(400);
let (head, history) = head_and_history(&git_dir);
// Two clients: one 10 commits behind, one 350. Same want, same repository,
// same server. The only thing that changes is how much the client holds.
let shallow = vec![history[10]];
let deep = vec![history[350]];
let mut rows = Vec::new();
for (label, haves) in [("behind-10", &shallow), ("behind-350", &deep)] {
let edges = touches(&git_dir, head, haves, false, "edges");
let full = touches(&git_dir, head, haves, false, "full");
let bits = touches(&git_dir, head, haves, true, "edges");
eprintln!("{label}: walk/edges {edges}, walk/full {full}, bitmap {bits} store touches");
rows.push((edges, full, bits));
}
let (edges_near, full_near, bits_near) = rows[0];
let (edges_far, full_far, bits_far) = rows[1];
// 1. The crossing. The exact walk gets *more* expensive as the client gets
// *closer*, because it opens what the client holds; the bitmap gets
// cheaper, because it opens what it sends. Neither direction is
// reproducible by accident.
assert!(
full_near > full_far,
"the exact walk cost {full_near} touches for a client 10 commits behind and {full_far} for one 350 behind. It is supposed to be paying for the client's history, and the nearer client holds more of it"
);
assert!(
bits_near < bits_far,
"the bitmap cost {bits_near} touches to send 10 commits and {bits_far} to send 350. Its cost is supposed to track the answer, not the client"
);
// 2. ...and on the request where the walk is worst — a client almost up to
// date, which is every `git fetch` anybody runs in a loop — the bitmap
// must be dramatically cheaper. This is the number the feature is for.
assert!(
bits_near * 10 < full_near,
"a client 10 commits behind cost {bits_near} touches with the bitmap and \
{full_near} with the exact walk it agrees with; that is under 10x and the \
exclusion is still being walked"
);
eprintln!(
"RATIO client 10 behind: exact walk {full_near} / bitmap {bits_near} = \
{:.1}x cheaper; shipping walk {edges_near} / bitmap = {:.1}x cheaper",
full_near as f64 / bits_near as f64,
edges_near as f64 / bits_near as f64,
);
let _ = edges_far;
}
/// A **clone** is the other half, and it is the half with no exclusion at all.
///
/// Worth measuring separately and worth reporting honestly: a clone names every
/// object in the repository, so the bitmap replaces the *selection* walk but
/// nothing can replace touching what is about to be sent. If this shows no win,
/// that is the answer, not a bug.
#[test]
fn a_clone_is_measured_too_because_it_is_where_a_bitmap_helps_least() {
let (_dir, git_dir) = bitmapped(400);
let (head, _) = head_and_history(&git_dir);
let walk = touches(&git_dir, head, &[], false, "edges");
let bits = touches(&git_dir, head, &[], true, "edges");
eprintln!(
"clone: walk {walk}, bitmap {bits} store touches, {:.3}x",
bits as f64 / walk as f64
);
assert!(
walk > 0 && bits > 0,
"a clone that touched nothing is not a clone"
);
}
/// Every branch tip of a **real repository**, fetched at four depths.
///
/// The fixture above is 400 linear commits over 11 files, which is a shape
/// chosen to make the point. This is the shape that exists. Skipped when
/// `GUNNAR_BITMAP_REAL_REPOS` is unset, and the skip is printed.
#[test]
fn real_repositories_report_what_the_exclusion_costs() {
let Ok(list) = std::env::var("GUNNAR_BITMAP_REAL_REPOS") else {
eprintln!("SKIPPED: set GUNNAR_BITMAP_REAL_REPOS to a colon-separated list of repos");
return;
};
let scratch = tempfile::tempdir().expect("tempdir");
let mut measured = 0usize;
let mut total_bitmap = 0usize;
let mut total_full = 0usize;
let mut total_edges = 0usize;
for src in list.split(':').filter(|s| !s.is_empty()) {
let name = Path::new(src)
.file_name()
.unwrap()
.to_string_lossy()
.into_owned();
let mirror = scratch.path().join(format!("{name}.git"));
let cloned = std::process::Command::new("git")
.current_dir(scratch.path())
.args([
"clone",
"--quiet",
"--mirror",
&format!("file://{src}"),
mirror.to_str().unwrap(),
])
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.output()
.expect("run git");
if !cloned.status.success() {
continue;
}
if git(&mirror, &["rev-parse", "--show-object-format"]).trim() != "sha1" {
// The cost question is hash-independent and the fixture above
// covers the parse; keeping one hash here keeps the totals
// comparable.
continue;
}
let store = FsStore::open_or_init(&mirror, Kind::Sha1).expect("open");
if store
.repack(&RepackOptions::new())
.expect("repack")
.bitmap
.is_none()
{
eprintln!("{name}: no bitmap");
continue;
}
let tip = store
.refs()
.iter(Some("refs/heads/"))
.expect("refs")
.into_iter()
.find_map(|(_, t)| match t {
Target::Object(id) => Some(id),
_ => None,
});
drop(store);
let Some(tip) = tip else { continue };
let history: Vec<ObjectId> = git(&mirror, &["rev-list", &tip.to_string()])
.lines()
.filter_map(|line| ObjectId::from_hex(line.trim().as_bytes()).ok())
.collect();
if history.len() < 200 {
continue;
}
let have = vec![history[history.len() / 2]];
let edges = touches(&mirror, tip, &have, false, "edges");
let full = touches(&mirror, tip, &have, false, "full");
let bits = touches(&mirror, tip, &have, true, "edges");
eprintln!(
"{name}: {} commits, client half behind — walk/edges {edges}, walk/full {full}, \
bitmap {bits} ({:.3}x exact, {:.3}x shipping)",
history.len(),
bits as f64 / full as f64,
bits as f64 / edges as f64,
);
total_bitmap += bits;
total_full += full;
total_edges += edges;
measured += 1;
}
assert!(measured > 0, "no repository in the list was measurable");
eprintln!(
"TOTAL over {measured} real repositories: bitmap {total_bitmap}, exact walk {total_full}, \
shipping walk {total_edges} — {:.3}x exact, {:.3}x shipping",
total_bitmap as f64 / total_full as f64,
total_bitmap as f64 / total_edges as f64,
);
}