nordisk/edda

A 16-bit fanout in front of the .idx: 4× on the seam, 1.003× on the request — reasoning

Class: reasoning. The measurement behind gunnar_store::fanout::Fanout16 and the decision it produced: built, tested, correct, and off by default, because the request does not move. Measured 2026-08-04 on oden.

What this lane was asked, and what bounded it before it started

.nornir/oid-index-reasoning.md raced a znippy-zoomies static tree against git's .idx and found something better than either: widening git's own fanout from 8 bits to 16 costs ~40 lines and 256 KiB and beats both. Its verdict was "do not adopt the tree; widen the fanout instead", measured in a self-contained microbenchmark over four .idx files.

This lane asks the next question — does that win survive contact with gunnar? — and its own sizing already said the answer was small: the .idx probe is 43% of gunnar.lookup_1m's 722 ns hit, but a request is not a lookup, and two other lanes measured pack_write at 75.7–97.5% of a fetch's CPU (median 88.6%).

1. Where gunnar resolves an oid to a pack offset, and how often

MEASURED, bench/examples/oidlookup-probe.rs (the oidprobe feature counts each call site), all 19 mirrored workspace_nordisk repositories, oden 2026-08-04. One clone and one negotiated fetch 200 commits behind, per repository, summed:

Two facts decide the shape of everything below.

• The count is not small. 5.45 oid → offset resolutions per object on a fetch. location_by_oid is exactly 1.000 per object — iter_from_counts' first phase — and the bitmap's position lookups are 3.59 per object, because Positions::intern asks once for every object the selection touches, not once for every object it sends. On the merge-heavy members it is far more: nornir 12.1 per object, workspace_nordisk 15.0.
• Two thirds of them are gunnar's own, and one third is not. PackBitmap holds a gix_pack::index::File this repository opened, so a wider fanout can sit in front of it. Everything through FsStore and PackedObjects enters gix-odb, which does its own 8-bit fanout and bisection inside a crate gunnar does not fork. 66.9% of a fetch's lookups are frontable; 33.1% are not, at any price short of a gix fork.

gix_pack::Find::entry_by_location is called 27 489 times on a fetch too and is excluded from every count here: it is keyed by offset and does no oid search at all.

What that costs, by perf

perf record -F 4999 over the same 19-repository clone+fetch sweep, 8 238 samples, taskset-pinned:

Against the same sweep's 1 651 ms of process CPU that is 15.4 ms over 316 167 lookups — 47 ns each, which is the independent cross-check that matters: the stree lane measured git's bsearch_hash at 59.8 ns on a 12 328-object sha1 index, and eighteen of the nineteen members are smaller than that.

For scale, the same profile: 24.6% inflate_fast, 16.2% longest_match, 13.4% deflate_medium. The pack writer's zlib is fifty times the index.

2. The structure, and where it was put

crates/gunnar-store/src/fanout.rs — 65 536 u32s, a cumulative histogram of each oid's first two bytes, plus a twelve-line bounded bisection over gix_pack::index::File::oid_at_index. It returns the same EntryIndex the .idx's own lookup returns.

Nothing on disk changes. It is derived, in memory, and a caller that drops it loses only time. That is deliberate: a sidecar file needs its own invalidation rule, and a stale oid index answers with a wrong pack offset, which is silent.

Built at open, cached with the bitmap. BitmapCache already re-stats the .bitmap on every call and rebuilds the whole PackBitmap when path, mtime or length move, so the table inherits an invalidation rule already known to be right. Build is 2.4–5.6 ns/oid plus a fixed 65 536-entry prefix sum:

A floor at 4 096 objects. The table is 256 KiB whatever n is. On bifrost (83 objects) that is 3 KiB per object to remove probes from a bisection that is already zero deep — git's 8-bit fanout leaves n/256 entries, so below 512 objects there is nothing left to narrow. Under the floor build returns None and git's own lookup is used; 12 of the 19 members are under it.

2b. Correctness, over the whole corpus, before any clock started

65 737 oids across all 19 repositories, sha1 and sha256, every one agreeing with git verify-pack -v. Two checks per oid, and the second one is the one that earns its cost:

• fanout::equivalent — each oid resolves to the same entry index through both searches, and a second-byte mutation of each resolves to None through both. The second byte is the one the wider fanout added, so a table built with the bytes swapped or accumulated off by one sends the query to a slice its oid is not in; mutating the first byte would be answered identically by both fanouts and would prove nothing about the eight new bits.
• git verify-pack -v's own oid → offset table, against pack_offset_at_index(fanout.lookup(oid)), with the object count asserted equal to num_objects() because an unparsed listing and a clean one look the same downstream. This is the only check in the area that does not go through gunnar's reader.

The floor is bypassed here on purpose (Fanout16::build_unfloored): Fanout16::MIN_OBJECTS is an economics decision and correctness is not a property the small packs get to skip because of it — bifrost's 83 objects are exactly where lo == hi on nearly every query.

Both halves were seen red on the real corpus, not only on a fixture:

3. What it is worth — the seam

PackBitmap::pack_position over every oid in each pack, release profile (stock x86-64, no target-cpu=native — gunnar ships a portable appliance binary), taskset -c 8, min of 11, shuffled query order.

The shuffle is load-bearing and was wrong first. Walking a pack's oids in .idx order asks a sequence of queries whose slices are adjacent, so almost every probe is already in L1: it measured the 1 000 000-object index as faster per lookup than the 352 396-object one, which is not a property any search has. A fetch asks in graph order, uncorrelated with oid order.

ns/lookup. The off column is not a straw man: it is gix_pack::index::File::lookup, git's algorithm as gitoxide ships it, reached through the same PackBitmap call. Part of the ratio is that gix's version routes every probe through a &dyn Fn(EntryIndex) -> &oid and this one calls oid_at_index directly; the fanout is the rest.

And beyond the corpus, straight through Fanout16::lookup against index::File::lookup (SCALE_IDX=…), same conditions:

The stree lane's stock-codegen table, on the same three scales, has fanout16_bsearch at 4.07×, 3.29× and 2.33× on hits. Two independent implementations, two independent harnesses, agreeing to within ~25%. The structure does what that lane said it does.

4. What it is worth — the request, which is the number that decides

One negotiated fetch per corpus repository, 200 commits behind, all 19, both arms in one process in one sitting, arm order alternating by repetition, min of 11, process CPU (RUSAGE_SELF) rather than wall, because oden carried other lanes at load 20–69 throughout.

Two shapes, because the answer depends on who owns the open:

Eight full A/B runs, six of which measured both shapes. The effect is 0.16–0.76% in the shape a server runs in, against a within-arm spread of 0.7–5.2%. Every run's ratio is smaller than that run's own noise, so no ratio is claimed for it.

The projection agrees, which is what says the null is a real null and not a disconnected wire: 74 695 of a fetch's 98 775 bitmap lookups fall on repositories over the floor, at ~40 ns saved each, is 2.1 ms out of ~750 ms — 0.28%.

Wire bytes are byte-identical, asserted rather than assumed: 27 489 objects, 56 985 358 bytes and one FNV-1a digest of the whole v2 response — advertisement, acknowledgments, sidebands, packfile and all — identical across both arms, both shapes and all 44 timed sweeps, over all 19 repositories including the sha256 member. And on a clone as well, which is a different arm of select_objects — no excludes, no negotiation, every delta base in the transfer — 60 887 objects, 92 226 528 bytes, one digest, both arms.

The ceiling on this whole area

Fronting every lookup a fetch makes, including the 33.1% inside gix-odb, and with no floor: 149 833 × ~54 ns is 8.1 ms of ~750 ms, 1.07% of a fetch's CPU, of which perhaps 60% is removable. The most this area can ever be worth on the nordisk corpus is well under one percent, and the part that is buildable without forking gix is a third of that.

5. Memory

256 KiB per open pack over the floor, flat, resident, for the life of the PackBitmap:

On this corpus the tables are 140% of the .idx files they accelerate, and 98% of every .idx in the constellation put together. A forge holding a thousand active repositories pays a quarter of a gigabyte of anonymous memory — which does not page out, unlike the mapped .idx it fronts — for under a percent of a fetch. That is the argument against, and it is a stronger one than the CPU.

6. What was seen red, and why each fired

Seven tests in crates/gunnar-store/tests/fanout16_finds_what_git_finds.rs. The bar is stock git, not gunnar's reader: git verify-pack -v's own oid → offset table, compared against pack_offset_at_index(fanout.lookup(oid)) for every object in the pack, both hash kinds. That is the check the stree lane's reader bug was found by, and gunnar's reader appears on one side of it only.

That last row is the finding inside the finding. Both searches return the same entry index by definition, so a PackBitmap that builds a 256 KiB table and never reads it is invisible to every wire byte, object count, position and fidelity check in the tree — and would have made this lane's end-to-end measurement report a null result for a disconnected wire, which is exactly the answer it was expecting. The guard that closes it is a probe counter on Fanout16 asserting pack_position over n objects went through the table n times; it is #[cfg(debug_assertions)], because a relaxed fetch_add is ~1 ns against a 15 ns lookup, and the release build's wiring is instead proven by the seam table above moving 4×.

7. Three wrappers that turn the bitmap OFF, and two of them were still live

ObjectStore::bitmap's trait default is None, so any wrapper that forwards every other method and omits this one does not fail to observe the bitmap — it disables it. Another lane found and fixed this in gunnar_bench::stages::StageCounting on 2026-08-04 (468db46). Two more instances were still in the tree and are fixed here:

• gunnar_store::NoPackCopy — the shipping type that is the BEFORE column of every P-001 pack-copy measurement and the red switch in crates/gunnar-wire/tests/pack_copy.rs, gunnar.vs_git_* and GUNNAR_BENCH_NO_PACK_COPY=1. Every arm wrapped in it served on the walk path with bitmaps off while the arm it is the control for served with them on, so the difference measured was pack-copy plus bitmap.
• gunnar_bench::readside::Counting — gunnar.fetch_readside and examples/readside-probe.rs.

Nothing could catch either: the bitmap path is defined to select the same object set as the walk, so the wire bytes agree across all 19 repositories, which is the fidelity check both instruments rest on.

The decision

Keep the structure. Do not turn it on.

GUNNAR_FANOUT16=on builds it; the default does not. That is off by design, not by omission — the distinction ObjectStore::packed's own documentation draws — and the reasons are recorded rather than assumed:

• the seam is genuinely 3.9–4.4× on hits and 8.6–9.2× on misses, and that is real;
• the request moves 1.0016–1.0076×, and every one of those figures is inside that run's own noise;
• the ceiling on the whole area, gix fork included, is ~1% of a fetch;
• 256 KiB per open pack is 140% of the .idx it accelerates on this corpus, and a quarter of a gigabyte of anonymous memory at a thousand packs.

Turning it on is one environment variable, so the day one of the three conditions below holds, the measurement is one command and not a day:

1. a repository past ~350 000 objects. At xl the baseline is 236 ns and at a million 486 ns, against 12 328's 71 — the seam grows with log n while the rest of a request does not.
2. a miss-dominated workload. Misses are where the ratio is 8.6–9.2×, and negotiation against a divergent client is nothing but misses.
3. a batch seam. P-003. The 33.1% of lookups inside gix-odb are not frontable at all today, and the 66.9% that are, are answered one at a time.

The larger prize in this area was never the index. It is the 88.6% of a fetch that is pack_write, and within the read side the per-call overhead P-012 names — 57% of a hit and 88% of a miss in gunnar.lookup_1m is neither the .idx nor anything a wider fanout can reach.

Re-taking it

Everything above is one command each, which is the point of committing the instruments rather than only the numbers.

cd bench
CARGO_TARGET_DIR=/home/rickard/scratch/cargo/gunnar-fanout-bench   cargo build --release --example fanout16-ab --example oidlookup-probe
cd ..
B=/home/rickard/scratch/cargo/gunnar-fanout-bench/release/examples

# §1, the call-site census. Needs `gunnar-pack/oidprobe`, which `bench/` turns on.
taskset -c 8 $B/oidlookup-probe 200

# §3 the seam, §4 the request, §5 the memory. Both arms, interleaved.
taskset -c 8 $B/fanout16-ab

# §3's scale rows, over indexes the corpus does not contain.
F=/home/rickard/scratch/gunnar-bench-fixtures
SCALE_IDX="$(ls $F/h2h-linear-sha1-20480c-1024f-16k/objects/pack/*.idx):$(ls $F/packed-1000000o-1p-v2/objects/pack/*.idx)" taskset -c 8 $B/fanout16-ab

# §6, the guards, including the four reds.
cargo test -p gunnar-store --features fs,conformance   --test fanout16_finds_what_git_finds

A probe rather than a persisted nornir bench run arm, deliberately and for the reason bench/Cargo.toml already gives readside-probe, stage-probe and stomach-probe: this answers how many and whether at all, which is a diagnostic a human reads once, and the answer is a null. A persisted arm over a structure that is off by default would record the baseline against itself. If one of the three reopening conditions above ever holds, the arm to add is the A/B — seam_hit_x, e2e_warm_x — not the on-path alone.

What was not determined

• Concurrency. Every number here is one pinned core. A 256 KiB table read by 32 workers is a different memory-system question; at a thousand open packs the aggregate is 250 MiB of anonymous memory whose access pattern was not measured.
• Multi-pack. One pack per corpus repository throughout. gunnar-store's midx.rs is a different structure with a different fanout and was not raced.
• gunnar-coldtier. The znippy backend resolves oids through its own index and was not counted; every figure here is FsStore.
• Push. receive_pack's connectivity check resolves oids too, and only the serve path was counted.
• Whether the two bitmap() fixes in §7 move any published number. They should: every NoPackCopy arm's BEFORE column was measured with bitmaps off. Re-measuring them is the pack-copy lane's, not this one's.