nordisk/edda

What a delta chain costs gunnar, and where

Delta chain lane, 2026-08-04, host oden. Every figure below was taken on that host that day. Claims are tagged MEASURED (a command was run and its output is quoted) or INFERRED (read out of source without a measurement).

The question this lane was given: resolving a git delta chain — what does it cost gunnar, and on which path? Nobody had measured it on gunnar's own paths.

0. The answer, before the evidence

Chain depth costs gunnar essentially nothing, on every path it has, and the two places it was expected to be expensive are both the other way round.

And the reason is not subtle once the corpus is weighted by bytes rather than counted: deep chains sit on tiny objects. Across 19 real repositories, objects at depth ≥ 5 are 26.2% of objects and 0.70% of raw bytes. The largest object at depth ≥ 25 anywhere in 60 739 objects is 4 716 bytes.

The 12.4× that znippy's DeltaEntry pays at depth 50 was measured on a 256 kB entry. That is 54× larger than the largest object at depth ≥ 25 in the entire corpus, and 137× the depth-≥5 median of 36 bytes. The 12.4× is a real property of that encoder; it is not a cost gunnar's repositories can present to it.

1. Depth across 19 repositories, counted and weighted

MEASURED: git verify-pack -v over the single pack in each workspace_nordisk member's checkout at /home/rickard/git/<repo>, 60 739 objects. The parse (NF==5 whole, NF==7 delta with depth in $6) was checked against git's own chain length = N: histogram on the same command and agrees on the whole count and on every bucket — that check is what makes these numbers usable, and two lanes got all-zeros from a bad awk today without it.

meanD is over all objects. meanD_w weights each object's depth by its raw (inflated) size — what a reconstructor actually has to move.

Five of nineteen sit on git's default cap of 50. Count-weighted that reads as "chains are deep in real repositories", which is true and is what the earlier six-repo table said. Byte-weighted the same corpus has a mean depth of 0.250 — an order of magnitude below the count-weighted 4.32 — and that gap is the whole finding.

Where the bytes actually are

Size distribution, MEASURED: at depth ≥ 5 the raw size is p50 36 B, p90 145 B, p99 1 867 B, max 39 414 B. At depth 0 it is p50 649 B, p90 12 350 B, p99 102 734 B, max 17 722 289 B.

By type, the deep tail is trees: 1 758 of the 2 242 objects at depth ≥ 25 are trees, mean 53 bytes. These are the one-entry directory nodes a nested crate layout produces (crates/, crates/x/, crates/x/src/), each a near-copy of its neighbour, which is exactly what a delta chain is for.

The one number this table does not contain

The base is not small. MEASURED on nornir: the whole object at the bottom of a chain has mean raw size 51 739 B for objects at depth 8, 57 489 B at depth 16 and 69 871 B at depth 32. Reconstruction cost tracks the root's size, not the depth — see §2.

Caveat, stated because it bounds everything above. These are developer checkouts: one pack plus loose objects (gunnar's own has 565 packed objects and 6 137 loose). A forge repository is fully packed. The packed portion is the part that has chains at all, so it is the right corpus for this question, but the per-repo object counts are not the repositories' sizes.

2. Cost per path, per depth, on real chains

MEASURED with bench/examples/deltachain-probe.rs against a bare repo holding nornir's own pack copied byte-for-byte (never git clone --bare, which silently repacks). Objects are bucketed by exact depth; each timed sweep reads every object in the bucket once on a handle whose cache starts empty. taskset -c 2, load average 6.8–8.8.

Read the read column against mean root, not against depth: depth 50 (root 11.9 kB) costs 39.6 µs while depth 2 (root 37 kB) costs 62.6 µs and depth 32 (root 70 kB) costs 141.7 µs. Cost is ~1.5–2 µs per kilobyte of chain root plus ~0.25–0.35 µs per link. Fifty links is ~15 µs; one 64 kB root is ~95 µs.

• entry_copy is flat and the deep end is cheaper, 0.034 µs at depth 0 down to 0.022 µs at depth 50, because a deep entry has fewer bytes to copy. This is the clone/fetch path (P-001, write_pack_copy_thin), and it confirms by measurement what the code says: iter_from_counts in Mode::PackCopyAndBaseObjects ships delta bytes verbatim and resolves nothing.
• header is ~10× a whole object's for any delta and then flat, 1.50 µs at depth 1 against 1.18 µs at depth 50. decode_header walks entry headers, so a link costs ~20 ns and fifty of them are ~1 µs. The fix that moved ObjectStore::header off full inflation is worth 6–140 µs per call and the residual depth term is noise.

The one exception on the copy path

write_pack_copy_thin has a veto at crates/gunnar-pack/src/copy.rs:441-462: a DeltaOid entry whose base the client cannot vouch for is written whole, which means a full try_find_cached(..., cache::Never) — one chain resolution per vetoed object. INFERRED, not measured: a clone passes client_has = None, so allow_thin_pack is false and gix emits no DeltaOid at all; the veto count is therefore zero on clone and bounded by the fetch's external-base count otherwise. Worth counting if a fetch ever looks slow.

3. Push verification: deeper is faster

MEASURED with bench/examples/indexdepth-probe.rs. A ladder: the same 13 431 nornir objects, packed by stock git pack-objects --delta-base-offset --window=10 at --depth=1,2,4,8,16,32,50, plus one pack of the same objects with no deltas. iter is BytesToEntriesIter in Mode::Verify — the front half of index_pack, which decompresses and CRC32s every entry and applies no deltas. resolve is the remainder: delta tree, delta application, and hashing every resolved object. Best of 5, two independent passes, taskset -c 2-5.

Second pass agrees within 2–12%; the ordering does not change.

The resolve column is the answer. It is 0.47–0.64 s across the entire ladder including the pack with zero deltas in it. A phase that costs the same whether there are 10 147 deltas at depth 50 or none at all is not delta application; it is the SHA-1 of 351 MiB of resolved object data, which every pack pays identically. Delta application is buried inside that and is not separable from it at this resolution — which is itself the finding.

The depth-dependent term lives in iter, and it runs the helpful way: 0.895 s with no deltas down to 0.227 s at depth 50, 3.9×, because a deeper chain is fewer bytes to inflate and CRC. Net, index_pack of depth 50 is 1.24× faster than depth 1 and 1.78× faster than no deltas.

This is gix's inverse traversal doing what git's does: the delta tree is walked from bases outward, so each delta is applied exactly once onto a parent already in memory. Depth is O(1) amortised there, not O(depth). gunnar's strongest arm is not at risk from chain depth, and a repacker that shortened chains to protect it would slow push verification down while making the wire 1.82× larger.

MEASURED on the same day, one real push through the real ReceivePack (3 362 objects, bench/examples/pushstage-probe.rs, reusing gunnar_bench::stages::push): pack_ingest 93.6% of push wall clock, connectivity 6.3%, everything else 0.2%. That is consistent with the 74.6–90.9% already on record.

4. The gix-pack cache gap: real, measured, and on the wrong path to matter much

The research lane INFERRED from source that gix-pack issues exactly one cache.put against git's every-intermediate insertion. The situation in gunnar was worse than that and nobody had looked: 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). crates/gunnar-store/src/odb.rs never called set_pack_cache, so every ObjectStore::read through the fs backend re-resolved its chain from the root, with no cache of any kind.

MEASURED, bench/examples/deltachain-probe.rs, whole pack read once per object on a cold handle:

Narrowest form of the same statement — one 51-link chain, base to tip, once each: 6.4× / 7.6× / 7.4×. That is the O(depth²) git's packfile.c:1715-1719 exists to remove.

Cache size sweep, nornir, pack order:

What it is worth end to end, which is the part that matters

Clone and fetch answer from the .bitmap and copy pack entries verbatim. Neither touches this path at all. The one hot path that does is receive-pack's connectivity walk. MEASURED, interleaved A/B on two builds of the same binary differing only in the cache cap, one real 3 362-object push, three passes each:

Non-overlapping across passes, so 1.6% is real — and it is 1.6%. A correct fix worth about a percent and a half of a push today.

Why it was still worth landing, and why it did not cost a crate

gix-pack's MemoryCappedHashmap is behind pack-cache-lru-dynamic, which pulls clru → hashbrown, allocator-api2, equivalent, foldhash. MEASURED with cargo xtask guard: the appliance graph goes 280 → 283 crates (267 → 270 third-party) and S:gunnar-store 103 → 107. That is a bad trade for a bounded map against a §2 guard the project treats as law.

crates/gunnar-store/src/delta_cache.rs is std-only, FIFO rather than LRU, and has the admission control git lacks (git adds an entry's size before evicting, packfile.c:1303-1311, so an over-sized entry is admitted and then evicts everything else). Guard after: 280 crates / 267 third-party, 7 tracked, 0 violations — the baseline exactly.

FIFO against gix-pack's real LRU at the same 4 MiB cap, whole-pack sweep: nornir 0.350 s LRU / 0.340 s FIFO, facett 0.085 / 0.085, knut 0.022 / 0.022 — 0.995× to 1.027×. On a walk, recency and insertion order coincide, and the LRU's bookkeeping costs slightly more than the extra hits it buys.

5. Whether gunnar gc's re-encoding changes depths

MEASURED, same host and day, on copies of the same three corpora.

The default gc changes nothing on any of the three. All three are 59–76% deltified, far above DeltaPolicy::Auto's 0.20 threshold (repack.rs:273-279), so the re-encode declines outright. --aggressive runs the full search on all three (1.0–16.9 s) and then discards it on knut and nornir because the recoded pack came out larger than the copy — the size guard at repack.rs:1010, and the already-consolidated guard at :1123.

Where it does land (facett, --aggressive, default name-hash-v2 order), it makes chains deeper: mean depth over deltas 6.92 → 9.51, objects at d≥5 1 786 → 2 150 (+20%), pack 16 135 329 → 15 940 403 B (−1.2%). Against stock git repack -adfk --depth=50 on the same object set, gunnar's re-encode runs +34% to +81% mean depth and +14% to +92% more objects at d≥5.

Byte-weighted, that is a much smaller thing than it sounds. Raw bytes at depth ≥ 5:

So gc's extra depth lands on the same small objects everything else does, and §§2–3 say the paths that would pay for it either do not resolve chains or get faster when chains get deeper. The trade is fine. Size-wise gunnar's encoder is at rough parity with git's full -f repack, beating it by 1–3% on all three, and size ordering is 1.7–1.9× worse than name-hash-v2 everywhere.

Two things this turned up that are not this lane's to fix:

• There is no knob for window or chain depth. repack.rs:744-752 overrides only thread_limit on gunnar_pack::DeltaOptions::default(), so 10/50 are hardcoded and an operator has no lever short of a code change.
• --aggressive on nornir costs 16 s against the default gc's 2.75 s to produce a byte-identical pack. The size guard is doing its job; the work in front of it is not free.

6. What went red

• The verify-pack parse. Cross-checked against git's own chain length = N: histogram, and broken deliberately two ways — reading $5 (offset) as depth, and treating every line as five fields, the shape two lanes hit today. Both produced a loud mismatch rather than a plausible table.
• The cache-liveness guard in deltachain-probe. set_pack_cache is a setter; nothing about calling it proves the cache is reached, and a handle that ignored it would make every lru column a second copy of the never column — matching numbers that read as agreement. The probe requires the cached handle's second read of the deepest object to be at least 2× faster than its first, and refuses to print a table otherwise.
• The fixture-trap guard. deltachain-probe bails unless the corpus's max depth is ≥ 25, because a repacked fixture answers every question 1.0× and looks clean doing it.
• The ladder's object-set guard. indexdepth-probe fails if two packs in the ladder index different object counts, because otherwise two workloads would be compared under one axis label.
• All five delta_cache tests, individually. Admission control removed → only the over-size test fails. Key reduced to the offset → only the two-packs test fails. Eviction loop removed → only the byte-bound test fails. order.push_back on the replace path → only the duplicate-queue test fails. Four independent breakages, four single-test failures, then green again.
• The A/B binaries. cmp between the cache and no-cache builds, so an A/B that had accidentally shipped one binary twice would say so.

A blind wrapper still in the tree, not mine to fix

bench/src/readside.rs's Counting ObjectStore does not forward bitmap(), so it inherits the trait default of None and gunnar.fetch_readside measures the walk while production takes the bitmap. This is the same defect the decomp lane fixed in bench/src/stages.rs on origin/main (1074100); the readside copy was not part of that commit. Flagged rather than edited — three lanes are in that file.

7. What I could not determine

• A repository big enough to matter. The largest corpus here is 13 431 objects and 38 MB. Every ratio above is from a pack that fits in page cache.
• Concurrency. Every read measurement is single-threaded on one pinned core. The delta base cache is per pooled handle and POOL_CAPACITY is 64, so its behaviour at 64 concurrent readers over one repository is unmeasured — the memory ceiling is arithmetic (256 MiB), the hit rate is not.
• Whether the copy path's thin-pack veto ever fires in practice. Reasoned from the code, never counted.
• The suite baseline. cargo test --workspace on this branch gives 1 092 passed / 0 failed / 6 ignored at origin/master+origin/main, and 1 107 / 0 / 6 once origin/master's later lanes are merged in. Five of those are this lane's. The 1 132 quoted in the brief is from a different tree or feature set and I did not reproduce it.