nordisk/edda

oid → pack offset: does a ragnar static tree beat git's .idx? — reasoning

Class: reasoning. The measurement behind gunnar.oid_index, and the decision it produced: do not adopt znippy-zoomies' stree for oid → pack offset. Widen the fanout instead. Measured 2026-08-04 on oden.

The question, and why the usual framing of it is wrong

znippy-zoomies ships stree/stree32, an implicit S(+)-tree derived from Ragnar Groot Koerkamp's static-search-tree, advertised at "up to ~40× vs binary search" and getting faster with many keys requested at once (.nornir/stree-reasoning.md in that repo). gunnar's hottest structural question is oid → pack offset. So: adopt it?

The 40× is against the wrong opponent. git's .idx v2 is not a binary tree. It is a sorted oid array behind a 256-entry fanout indexed by the oid's first byte, binary-searched from inside a ~1/256 slice, on an mmap — one radix step and no syscall before the search even starts. Against that, most of the tree's structural advantage is already spent, and the only honest measurement is against packfile.c's bsearch_hash as git actually writes it.

There is a second wrong-opponent trap one level down, and it is the one that decided this. If the tree's advantage is "narrow the slice before you search it", then git's fanout is the version of that idea git already ships, and it can be widened without a new data structure. So the suite also races a 65 536-entry fanout on the oid's first two bytes (fanout16_bsearch, ~40 lines, 256 KiB flat per pack) and that same fanout with a u64-prefix compare and 16 searches in flight (fanout16_pipe16).

Which stree variant, and why there is a variant question at all

Neither tree can hold an oid. STree32's key is a u32, STree64's is an i64, and an oid is 160 or 256 bits. Every stree over oids is therefore a tree over a prefix, plus a verification of the full oid at the position the tree lands on — which is the last step the binary search does anyway, so both structures answer the same question and return the same index into the same sorted table.

The prefix width is then the whole design choice, and it is a collision question. A priori it favours 64 bits: expected colliding pairs are n²/2^(w+1), so ~14.5 pairs at 352 396 oids for a 32-bit prefix against ~3·10⁻⁹ for a 64-bit one. The measurement went the other way. Real collision counts were 10 (of 352 396) and 129 (of 1 000 000) — the expected extra comparisons per query are n/2^32, i.e. 2·10⁻⁴ at a million objects, which is nothing — and STree32 (B=16, log₁₇ levels, 4.25 B/oid) beat STree64 (B=8, log₉, 9.00 B/oid) on every cell of the matrix, on hits and misses, at every corpus size, while costing half the memory. So the measured answer is STree32 over the top 4 bytes, and the a-priori answer was wrong. Both are reported.

What was measured

Nine arms over four real .idx files, taskset-pinned to one core, min-of-N with the within-arm max/min spread published beside every number.

Plus the 19 mirrored workspace_nordisk repositories (65 737 oids, 83 to 12 328 each) for the rebuild economics.

The corpora are real .idx files and the oids are real hashes. No id in this measurement was invented; the two large fixtures are generated histories, so their oids are genuine sha1/sha256 of genuine objects, which is what makes their distribution the same as any other repository's.

What the instrument had to survive first

• The .idx reader is checked against git, object by object, by oid_index::oracle against git verify-pack -v: 1 371 161 oid → offset pairs across six packs, every one agreeing. This is the only check in the area that does not go through the reader, and it earned its place — it caught a real bug where the hash width was solved from the file length, which admits sha1 for a sha256 index (8 + 1024 + n·28 + 40 fits inside a sha256 file and leaves a multiple of 8 over). Every arm then agreed beautifully about garbage. The width is now decided structurally, off the fanout's 256 boundaries.
• Every structure resolves 4 096 evenly-spaced oids to their exact index, and a one-byte mutation of each to None, before any timing.
• All arms must agree on the wrapping sum of resolved pack offsets and the hit count. That sum is also what stops the lookup being optimised away.
• Both red switches were blind on their first version. GUNNAR_BENCH_OIDINDEX_RED=hitmiss also adjusted the expected hit count, so it passed; a red probe that moves with the bug is not a red probe. …=agree displaced exactly one stree key, and 2 000 random probes over 12 328 oids simply never asked for it. Both now fire deterministically.

The result

Nanoseconds per lookup, batch 1 000, stock x86-64 codegen (what gunnar ships), min of 11. The within-arm max/min band over those 11 was ≤ 1.09 on every miss column and on the 1 000 000-oid hit column; on the two smaller hit columns it reached 1.26–1.30 for the stree arms and 1.61 for fanout16_pipe16, so no ratio below ~1.3 is claimed there and every such cell is called a tie below.

Against git, the tree wins and wins clearly: 2.0–4.1× on hits and 3.1–11.8× on misses. Rickard's claim survives contact with the right baseline in the sense that mattered — it is not 40×, but it is real.

Against a wider fanout, it does not win anywhere gunnar lives. At real repository size (12 328 oids, and eighteen of the nineteen nordisk repos are smaller) a forty-line 16-bit fanout is 2.0× the tree on hits and 3.0× on misses, and the tree's batch machinery is pure overhead. At 352 396 it is a tie on hits and the tree is 1.26× on misses. Only at a million objects does the tree win anything decisive, and only on the miss path — 1.78× stock, 3.6× native, both far outside the band. On hits at a million it loses, by 1.22× stock and 1.06× native; the second of those is inside the noise band, so the honest reading of the hit path at every size is the fanout is at least as good as the tree.

The batch axis, which is the claim that was actually being tested

"Gets faster with many ids at once" is true, and it saturates and then reverses. stree32_batch16 on xl, hits, ns/lookup:

2.7× from batch 1 to batch 1 000, flat to 10 000, and 37 % worse by 200 000 because the query and result arrays stop fitting beside the tree. The right batch is ~10³, not "as many as you have". gunnar-pack's vouching closure and select_objects both chunk naturally at that size, so this is not a constraint — but "bigger is better" is wrong and would have been designed in.

Misses are where the tree is structurally different, and it is not a small thing

A miss costs git exactly what a hit costs (316.6 vs 309.5 at a million): the binary search runs to exhaustion either way. The tree refutes a miss at the prefix level, without touching the oid table at all — 26.8 ns against a 38 MiB table it never reads. That is a genuine structural property and it is the negotiation workload, where every have from every client is a question about an object the server may not hold.

It is also the only property the tree has that the fanout cannot copy.

The codegen dependency, which is load-bearing and was nearly missed

The same code, same corpus, same core, with only -C target-cpu=native removed:

The baselines are codegen-insensitive and the tree is not. Its miss advantage halves on a portable build. MEASURED; the mechanism — that the AVX2 count_lt inlines into the batch driver only when the whole crate is compiled for the target — is INFERRED and was not confirmed by reading codegen. gunnar ships a distributable appliance binary, so the stock column is the one that applies, and the native column is what a -march=native rebuild on the serving host would buy back.

Sizing it against gunnar's real lookup cost, which is what settles it

gunnar.lookup_1m measures the same 1 000 000-object sha256 fixture through FsStore, and on 2026-08-03 reported lookups_per_sec_hit 1 384 680 (722 ns) and lookups_per_sec_miss 370 068 (2 702 ns). The .idx probe inside those is 310 ns and 317 ns. So the index structure is 43 % of a hit and 12 % of a miss; the rest is gix-odb handle, snapshot and dispatch (P-012).

Holding that overhead constant and swapping only the structure:

The two candidates are within 3 % of each other on gunnar's actual call path. A 1.78× on the miss structure is 1 % end to end, because the structure is one-eighth of a miss. The larger win in this area is not the index at all — it is the 57 % of a hit and 88 % of a miss that is per-call overhead.

And a clone does not look anything up

pack-objects orders the pack the way a client consumes it, so a clone copies a contiguous byte range — the xl corpus's 352 396 oids are written, not resolved. Only fetch scatters: every have, every selected object, and every delta base against client_has in write_pack_copy_thin's vouching closure. So even the full 1.5× above lands on one arm of one operation, and the arm it lands on is the one this repository already serves fastest.

Per-repo trees, not one global tree

Rickard's instinct — "would that mean it must be regenerated all the time? it's better to have many small ragnars" — is right, and here is the number rather than the agreement. Build is a linear pack over an already-sorted array; measured between 3.3 and 5.3 ns/oid for STree32 across three decades of n (the extrapolations below use the pessimistic 5), and 4.25 B/oid resident.

† EXTRAPOLATED from the measured 5 ns/oid and 4.25 B/oid; no 35 M-key build was run. The three measured points (12 328 / 352 396 / 1 000 000) are linear to within 20 %.

A global tree pays ~176 ms and re-materialises 143 MiB on every push to any repository in the forge; per-repo trees pay 1.8 ms and only the repository that changed pays it. That is ~100× less rebuild work per push, and it is local. Many small ragnars, confirmed.

There is one legitimate global index — "which repository holds this oid", which is how forges do cross-repo dedup and alternates. That is a different feature with a different key and a different payload, and it is not this one.

The decision

Do not adopt stree for oid → pack offset. If this area is worked, widen the fanout: fanout16_bsearch is forty lines, 256 KiB per pack, no dependency, no codegen requirement, and it is 2.0–4.1× git at every corpus size gunnar actually serves, beating the tree outright below ~350 000 objects. fanout16_pipe16 adds the pipeline where a caller already has its oids in bulk.

Revisit only if all three hold at once: a repository beyond ~10⁶ objects, a miss-dominated workload (deep negotiation against a divergent client), and a serving binary built for its host. Until then the tree is a dependency, 4.25 B per oid, and a 3 % difference.

What was not determined

• Whether a batch API would amortise gunnar's own per-call overhead. The 1.5× ceiling above assumes that overhead is constant, which a real batch seam (P-003) would not leave constant. Nobody built one, so nobody knows.
• Concurrency. Every number here is one pinned core. A shared tree read by 32 workers is a different memory-system question and was not measured.
• Multi-pack. One pack per corpus throughout. P-012's multi-pack index is a different structure with a different fanout and was not raced.
• The codegen mechanism, as noted above: the effect is measured, the explanation is not.

The follow-up, which was run and answered

.nornir/fanout16-reasoning.md, 2026-08-04. The recommendation above — widen the fanout — was built (gunnar_store::fanout::Fanout16), held to git verify-pack -v object by object, and measured through gunnar rather than through a microbenchmark. It confirms the structure and declines to ship it:

• the seam moves 3.9–4.4× on hits and 8.6–9.2× on misses, which is this note's fanout16_bsearch column arriving at the same place from a second implementation on a second harness;
• a negotiated fetch over all 19 nordisk mirrors moves 1.0016–1.0076×, every run of it inside that run's own noise;
• a fetch makes 5.45 oid → offset resolutions per object served, and only 66.9% of them are gunnar's to front — the rest are inside gix-odb;
• the ceiling on this whole area, gix fork included, is ~1% of a fetch's CPU;
• 256 KiB per open pack is 140% of the .idx it accelerates on this corpus.

So Fanout16 exists, is correct, and is off unless GUNNAR_FANOUT16=on.

Not the same question as __gunnar_oid__

A backend lane declined to emit a __gunnar_oid__ section, and that verdict was about the schema — that section maps oid → archive entry row, and a pack tier has only two entries, so the column has nothing to address. This note is about oid → pack offset, which was untested until now. The two conclusions happen to point the same way and they are not the same finding; neither supports the other.

Follow-up: ragnar on the haves (2026-08-04, same day)

The question the note above left open, asked properly. Same answer, and now with the end-to-end number attached: the structure is not the term that matters. Arm: gunnar.have_lookup.

Why this shape was worth a second measurement

Everything above says the tree loses to a wider fanout — except on misses, where it refutes at the 32-bit prefix without reading the oid table. A fetch's negotiation is a batch membership test, and a divergent client's haves are mostly absent. That is the tree's best case and it is a real workload, so it got its own arm rather than an inference.

The shape, measured off real fetches

18 mirrored workspace_nordisk repositories, real git fetch over file://, haves taken off the wire with GIT_TRACE_PACKET, each one asked of the server with git cat-file --batch-check. The client is made genuinely behind — reset, remote-tracking ref dropped, reflog expired, gc --prune=now — because a client that merely reset still holds every object, git says "up to date", and the trace contains no have at all. That is what the first version of this script measured: zero.

Two corrections to the sizing this arm was commissioned with, both of which lower the ceiling.

• The window is 16 and doubles — 16, 32, 64, 128 — not 32. fetch-pack.c's INITIAL_FLUSH is 16 and next_flush doubles it. The 256 is MAX_IN_VAIN, how many unproductive haves git tolerates before giving up, and no round of 256 was observed at any divergence up to 200 commits.
• A protocol-v2 client re-sends its whole have list every round, and HaveMemo answers each distinct have from the store exactly once per connection. So contains is called for 16 distinct haves in the common case and ~128 at a 200-commit divergence — not the 4 298 have lines that crossed the wire in the deepest sweep.

And the case that dominates real traffic — a client merely behind, at every depth from 1 to 400 — is 100 % hits in one round of 16, which is the mix the tree is worst at.

The probe

nornir's mirror, 12 455 oids, one pack, min of 15, taskset-pinned. ns per lookup:

The band on this table is 1.646, so the only claim it supports is the large one: the 16-bit fanout is 3.7–5.3× the tree on every shape, including the all-miss one the tree was supposed to own. stree32 against git's binary search runs 0.83–1.34×, entirely inside the band, and is not claimed.

The tree does behave as predicted relatively — it improves as the mix gets missier (27.47 → 20.69 ns from all-hit to all-miss) while git's search gets slightly worse (22.86 → 27.71). It just starts too far behind to matter, because at real repository size the whole index is 338 KiB and a 65 536-entry fanout lands on ~0.2 oids per bucket.

End to end, which is the half that was actually commissioned

The same fetch served out of a private mirror four times per repetition — contains answered by gunnar-as-it-ships, by git's algorithm over the mapped .idx, by the 16-bit fanout, and by the tree — interleaved, nine repetitions, gunnar-stage decomposing each one. Two client shapes, because they have very different denominators and quoting one would be choosing the answer.

Both end-to-end ratios are inside their own noise bands. The end-to-end effect of putting ragnar on the haves is unmeasurable, and that is the result.

The three things this found that the probe could not

1. The dominant term is not the index, it is gix-odb's miss path. On the all-miss shape, gunnar as it ships spends 641.4 µs on 257 contains calls — 2.50 µs each — where the same work read straight off the same .idx is 0.302 µs and a 16-bit fanout is 0.181 µs. That is 13.8× between the shipping path and the cheapest candidate, and 1.13× between the two candidates. On the all-hit shape the gap disappears (184.0 vs 182.2 µs), which is the signature of RefreshMode::AfterAllIndicesLoaded — P-012 measured the same asymmetry from the other side (866 518 misses/s with RefreshMode::Never against 78 603 without). The lever here is not a new structure; it is the refresh a miss triggers, and P-012 already names it.

2. The warm-loop probe overstates all three by about 10×. The probe reports 22.86 ns for git's search; in a real negotiation, where each structure is touched once rather than 20 000 times, the same search costs 302 ns. Every ratio narrows with it: the fanout's advantage over the tree drops from 3.7× to 1.13×. A lookup microbenchmark measures the loop, not the negotiation, and both numbers are published here for exactly that reason.

3. Even a 13.8× on the negotiate stage cannot be seen in a fetch, because on the shape where it exists the stage is 641 µs of a 121 986 µs request — 0.53 % — and on the shape where the stage is a real 7.8 % of the request, the haves are all hits and there is nothing to win. The two conditions do not co-occur.

Recommendation

Do not put ragnar on the haves. It loses the probe to a forty-line fanout at every measured mix, its end-to-end effect is inside the noise band on both client shapes, and the term that actually costs — 2.50 µs per missing have through gix-odb — is not an index-structure problem.

If this path is worked, the order is: RefreshMode on the miss path (P-012, 13.8× available and already diagnosed), then a wider fanout if anything, then nothing. The tree is a dependency and 4.25 B per oid for a difference of 1.13× on 0.53 % of one arm of one operation.

What was seen red

• GUNNAR_BENCH_HAVE_RED=mix makes the "absent" haves present without adjusting the expected count → the probe-set assertion fires.
• GUNNAR_BENCH_HAVE_RED=noswitch reroutes the tree's answers through the plain binary search. The call count stays correct and the wire bytes stay identical — both obvious checks stay green, because the intervention is not supposed to change either — so the arm counts answers inside the named structure's own match arm and asserts that separately. It fires.
• The decorator refuses to open a repository with a second pack or any loose object, either of which would make it answer false for an object the repository holds: a wrong answer shaped exactly like a fast one.
• Every candidate must serve a byte-identical response, and negotiate must have been entered, or the share is a share of a stage that never ran.

What could not be determined

• Concurrency. One pinned core throughout. 32 workers sharing one tree is a different memory-system question.
• Whether the RefreshMode win is real end to end. It is 13.8× on a stage worth 0.53 %, so the arithmetic says no — but it was not measured, and this arm cannot measure it because it bypasses the path in question by construction.
• Repositories past ~12 k objects on this shape. The have arm runs on one real mirror; the size sweep lives in the section above.