nordisk/edda

Deltifying for the transfer, and the gc that was undoing it

MEASURED on oden, 2026-08-04. Subject gunnar built from this branch, /home/rickard/scratch/cargo/gunnar-xfer/release/gunnar, 26 379 264 B, mtime 22:07:17Z. Client is stock git 2.53.0. Corpus is the 19 real workspace_nordisk repositories, 18 sha1 and one sha256 (tunnr), pushed into a gunnar store by stock git — never clone --bared, which silently repacks. Every byte below is counted by one relay (cargo xtask wireproxy) in front of one server, server→client direction, and every relay row was ok.

The four scripts that produced every number here are in .nornir/bench/: transfer-setup.sh builds the corpus, transfer-arm.sh runs one arm end to end, transfer-ceiling.sh produces stock git's two reference packs and transfer-basedist.py classifies where a fetch's delta bases live. Each arm prints its subject binary's path, size and mtime before it runs anything.

1. The finding, which is a regression and not an optimisation

gunnar gc roughly doubles a shallow fetch.

19 clones, 16 fetches at depth 50, 12 at depth 200 (the rest have shorter histories). The default gc is not even re-encoding — DeltaPolicy::Auto declined on all 19, the delta fractions being 41.0%–72.3% against its 20% threshold — so this is consolidation alone doing it.

It is not that gc loses deltas. korp's delta fraction moves 67.3% → 66.0%. It is that gc turns them round.

1a. And on the bake-off fixtures it is a different answer, said by the log

"gunnar gc --aggressive produced no smaller pack on the bake-off corpus" has three possible causes and they are not distinguishable from the output size. With store.repack.delta_policy in place, the fixtures answer for themselves — small.git and large.git, pushed into a fresh store, RUST_LOG=gunnar=info:

Both candidate causes are real, on different flags. The default declined because the fixtures sit far above the 20% threshold; --aggressive ran and its ordering was genuinely worse than the one already in the pack, by 8.4% and 12.5%, and the monotone rule kept the original. transfer-v2 loses there too and leaves the same pack.

That is the opposite of what the same flag does to the 19-repository corpus above, where it wins on all 19 at 0.8105×, and the difference is entirely the input: the bake-off fixtures are git repack -adfq'd single packs, so gunnar's search is being asked to beat git's own best effort with nothing left to consolidate. The 19-repository corpus is push residue — three packs per repository, with the thin bases index-pack --fix-thin appended sitting in it twice. A repacker measured only on already-optimally-repacked fixtures is being measured on the one input where it has nothing to do.

2. The mechanism

For each repository and each cut, take the objects a fetch would send and ask where each one's delta base lives. korp, 50 commits behind, 294 objects sent:

Every delta whose base sat behind the negotiation cut was destroyed: the object became a base and now travels whole. The same shape on nornir (144 → 28), holger (138 → 59) and facett (144 → 77).

The cause is the sort key. gunnar-delta's window sorted (kind, name_hash desc, size desc, id) — git's type_size_sort — and a base must be an object earlier in that order. Size descending is blind to time, so whether the newest revision of a file ends up as the base or as a delta is decided by whether it happens to be the larger one. git can afford that because a git server re-runs pack-objects --thin over the transfer set at serve time. gunnar's serve path copies pack entries verbatim (P-001): the direction the repacker chose is the direction on the wire, for every fetch, until the next gc.

3. Why "make the fetch self-contained" is the wrong fix

The obvious reading of "deltify for the transfer" is to choose bases inside the object set a fetch sends, so no thin pack and no voucher are needed. That direction is refuted by construction. Three packs over the identical object set, all produced by stock git from the source repository, summed over the corpus:

2.06× at depth 50. A fetch's object set contains at most one or two revisions of each changed file; there is nothing inside it worth deltifying against. The good base is always the previous revision, which is exactly the object the client already has.

The census's "client_has refuses 75.8% of gix's thin offers" is therefore not a reason to stop offering thin deltas. It is a reason to widen the voucher — which is another lane, on the read side — and, here on the write side, to stop the repacker destroying the offers before they are ever made.

There is also nothing for a nearer base to buy. Across ten repositories and two depths, not one sent object had a base outside both the sent set and the client's history (absent = 0), and none had a base more than ~200 commits behind the cut. The bases were never far away; they were pointing the wrong way.

For the same reason a --depth/--window knob does not reach this. A wider window searches further and a deeper chain links further, and neither can turn a chain round.

4. DeltaOrder::TransferV2

One term in the sort key: (kind, name_hash desc, **epoch ascending**, size desc, id), where epoch is a dense rank over the repository's commits, larger being newer. Inside a group of like-named objects the oldest revision now sorts first, and since a base must be earlier in the order, a base is always at least as old as its target.

The epoch comes from the walk that already computes the name hash (gunnar-store/src/pathwalk.rs), which is first-path-wins; descending the root trees in ascending committer time therefore stamps every object with the oldest commit that contains it, at the cost of one commit decode and one sort of the root trees. epoch == 0 is "no information" and reduces the key to exactly what it was, which is why every other ordering is untouched — and is asserted, not assumed, by only_the_transfer_order_dates_anything.

5. What it is worth, and what it costs

gc --aggressive --delta-order transfer-v2 against gc --aggressive (the default name-hash-v2), same store, same clients, same relay:

--delta-order path-walk is in the same table for the ordering question the brief asked, and it answers it: clone 93 042 058, fetch@50 12 052 684, fetch@200 42 559 356 — statistically the same fetch as name-hash-v2's 12 053 912 and 42 103 400. Path-walk changes which objects share a window; it does not change which way the chain inside that window points, and the direction is the whole of this.

All 16 repositories improve at depth 50 against name-hash-v2; the per-repo range is 0.303× (korp) to 0.850× (ordning).

Against the never-repacked store the aggregate also improves — 0.952× at depth 50 and 0.904× at depth 200 — but not on every repository, and that has to be said rather than averaged away. Eight of the sixteen are still slightly worse than never running gc at all: Skidbladnir 1.014×, korp-collectors 1.010×, knut 1.014×, dwarves 1.037×, facett 1.044×, modgunn 1.101×, and nornir 1.480×. The aggregate is carried by korp (0.524× against the un-repacked store) and workspace_nordisk (0.601×). What nornir does that the others do not was not determined; it is the largest member and the only one with a substantial LFS-pointer population, and the arm was not re-run to isolate it.

Against stock git's own thin pack of the identical object set, the transfer ordering lands at 1.0075× at depth 50 and 1.0238× at depth 200. There is essentially nothing left on the table.

The clone and the archive are 6.1% worse, and that is the whole of the trade. Dropping size-descending inside a group is a real loss to whole-history compression. In absolute bytes on this corpus one clone costs +296 148 B and one 50-commit fetch saves +346 105 B, so the ordering pays from roughly one fetch per clone onwards — which is why it is a flag and not the default. A repository that is mostly cloned should not use it.

Three repositories (bifrost, draupnir, funnel-core — all under 50 commits) declined: the re-encode lost to the copy and the monotone rule kept the copy, which is that rule working.

There is a third cost, and it is the one nobody would look for. Over the whole corpus, 65 157 objects, from git verify-pack -v:

More deltas and 1.35× deeper chains for a 6.1% larger pack: ordering by time finds a base for more objects, and each base is worth less. A reader pays that depth per object reconstructed. gunnar's serve path does not — it copies pack entries (P-001) and never applies a delta — so the bill lands on cat-file, on index-pack at the receiving client, and nowhere on the fetch this ordering exists to make cheap.

6. The suite, and the guard

cargo test --workspace --features gunnar-store/fs --no-fail-fast --release: 1111 passed, 0 failed, 6 ignored, 145 binaries, cargo's own exit status 0 (not a pipeline's). That is the 1107 baseline plus this change's four new tests. cargo xtask guard: dependency guard PASS, 7 tracked deviations, 0 violations; pack-pipeline guard PASS, 0 undeclared call sites; 280 crates on the appliance graph. cargo clippy --workspace --all-targets adds no warning this change did not already find in the tree (bitmap/write.rs, fanout.rs, tests/repack.rs, all unchanged here).

Correctness across the five arms: 95 clones and 140 negotiated fetches, each git fsck --full --strict and each object set compared against the source repository's own rev-list --objects. Zero failures. Every client genuinely lacked the bases — it was cloned when the server held only the old cut — so a thin delta naming a base the receiver did not have would have failed there. Both columns were seen red: a corrupted pack makes the fsck column read FAIL, and a revision the clone does not hold makes the two digests differ.

7. What was seen red

• the_older_revision_is_the_base_even_when_it_is_the_smaller_one — deleting the epoch term from sorted_order fails it, and it carries its own negative control: the epoch-0 case asserts the pre-change answer, so a fixture that could not express the wrong direction would fail there first.
• the_epoch_sorts_inside_a_group_and_not_across_groups — moving the epoch above the name hash fails it.
• the_transfer_order_dates_the_older_revision_first — deleting roots.sort_by_key in pathwalk::group fails it, and only it.
• A TransferV2 repack whose walk dated nothing is a refusal, not a warning: the epoch key would be 0 everywhere, the search would silently run under the size ordering, and every other number in the log line would look healthy.

8. Two instrument faults found on the way

• There was no applied output for "the policy declined." gc --aggressive producing no smaller pack has three different causes — the policy never ran, the search ran and lost to the copy, the search ran and won by nothing — and only the last two had an event. store.repack.delta_policy now says which, before anything acts on it.
• cargo test -p gunnar-store --features repack-delta silently runs none of pathwalk's tests. The module is gated all(feature = "fs", feature = "repack-delta"), so the seven tests there need --features fs,repack-delta (or --workspace, where unification supplies both). Seven green tests that were not being compiled.

9. It is idempotent, and it is deterministic

Two independent transfer-v2 repacks of the same store produce byte-identical packs. A second transfer-v2 gc over an already-transfer-v2 store produces exactly the same total, 98 022 952 B — so a forge that runs this weekly does not walk its packs anywhere.

10. Which build measured what

The no gc / gc / gc --aggressive arms ran on the pre-change binary (26 370 384 B, 21:47:16Z); transfer-v2 on 26 379 264 B, 22:07:17Z; path-walk on 26 381 208 B, 22:18:53Z. That the plumbing added between them is a no-op for the existing orderings is asserted, not assumed: gc --aggressive run on the post-change binary produces a pack of exactly the same size for all 19 repositories as the pre-change arm recorded, and two independent transfer-v2 repacks of the same store produce byte-identical packs.

Every arm starts from the identical store — the four pack-before.tsv files have one md5 between them — and from identical client copies.

11. What this does not answer

• Whether a repository's real clone-to-fetch ratio makes the 6.1% clone cost worth paying is a per-repository fact this measurement cannot supply.
• The depth-200 win (0.907×) is much smaller than the depth-50 one (0.541×), because the deeper the cut the more of each file's history is inside the sent set and the less the direction matters. Follow that line and it crosses: a client far enough behind is fetching most of the history, which is a clone, where this ordering costs 1.061×. So transfer-v2 is a bet that clients are usually close to the tip. Where the crossover sits was not measured — depths beyond 200 were not run, and three of the corpus's repositories are shorter than 200 commits.
• Box load at the time of the gc timings was 51.64 / 62.68 / 50.41 on 32 CPUs, with the workspace test suite running. The gc arms were pinned with taskset -c 0-15. 23.67 s against 24.03 s on one sample each, on that box, is not a difference; treat the two as the same cost and the byte columns as the result.
• gc wall clock is one sample per arm on a box whose load ran 8–197 today; 23.67 s against 24.03 s is not a difference this measurement can resolve. The byte counts are counted rather than sampled, and two independent repacks of the same store produced byte-identical packs.