Module oid_index 

__gunnar_oid__ — the reserved oid index.

A raw (non-Arrow) section holding an stree keyspace over the first eight bytes of every object id, plus, per entry, the full oid, the first lookup row of that object’s chunk run, and its object ordinal.

Why stree and not the stock fst trie

Git oids are fixed-width and uniformly random, so they share no prefixes: an fst gets no prefix compression, still walks its automaton byte by byte, and has no batch path. stree (znippy-zoomies/src/stree.rs) is built for sorted fixed-width keys — one cache-line node, branchless AVX2 compare, and a software-pipelined batch traversal. Serving one git pack is thousands of lookups, so the batch path is the whole point.

The 8-byte prefix is NOT a key — it is a filter

Two distinct oids can share their first eight bytes. It is vanishingly unlikely and it is not impossible, so the key is treated as what it is: a filter that narrows to a short candidate run, after which the full oid is compared. lookup is only ever correct because of that comparison; GitOidIndex::candidate_run exposes the unverified run precisely so a test can prove the verify step is load-bearing rather than decoration.

Section layout (little-endian)

  0  magic  b"ZNPYGOID"                8
  8  u32 version                       4
 12  u8  hash code (1=sha1, 2=sha256)  1
 13  u8  oid_len (20 or 32)            1
 14  u16 header_len (24 or 64)         2   ← was `reserved`, see OidLayout
 16  u64 count                         8
 24  u8  pad [header_len - 24]             ← zero, only when header_len > 24
 HL  i64 keys   [count]                8*count   ← sorted ascending, the stree keyspace
     u64 rows   [count]                8*count   ← first lookup row of that oid
     u32 ords   [count]                4*count   ← object ordinal (oid-lexicographic)
     u8  oids   [count * oid_len]                ← full oid, for the verify step

Where the keyspace sits against the cache line — OidLayout

header_len exists because the header offset decides the cache-line phase of the key array, and the key array is what stree’s leaf scan reads. See OidLayout for what each value means, what it costs, and — importantly — what it cannot reach.

Measured: alignment buys 5% fewer cache misses and no time at all

oden, 32-core Threadripper PRO 3975WX, 2026-08-07, --release --no-default-features, sha1 oids, examples/oid_align_bench.rs, three arms, arm order rotated so each is timed first exactly once, /proc/loadavg 1-min 0.58–1.30 throughout.

The hypothesis this tested was half right, and the half that was right does not pay. The prediction was that a 24-byte header makes every stree node straddle two lines, “two misses per level instead of one”. Two corrections fell out of reading the source before measuring:

1. The internal nodes are not in this section. STree64Mmap builds them into its own Vec<[i64; 8]>; the section holds only the leaf layer. So the header can move one access per lookup, not one per level.
2. A 64-byte header alone does nothing. Vec<u8> is align-1 by type. Measured Compact phases at 4e6 objects were 40 and 56 on different runs — glibc’s 16-mod-64 chunk base plus the header. The allocation has to move too, which is why OidLayout::Compact64Alloc exists as the control.

Counters attributable to the ordinals_batch loop alone (a dry run with only the lookup call removed is subtracted, so query construction and chunk iteration cancel), 4e6 objects, 6e6 lookups per run, median of four passes, per 1e6 lookups:

counter	compact24	compact24+align	aligned64	aligned/compact
instructions	838 617 005	838 610 396	838 561 628	1.000
cache-references	31 853 436	32 191 979	31 976 234	1.004
cache-misses	14 981 126	14 752 419	14 206 088	0.948
dTLB-load-misses	4 624 378	4 620 465	4 615 620	0.998
cycles	1 390 271 493	1 286 488 175	1 280 146 067	0.921

The identical instructions count is the guard that the three arms really are one code path. The 5.2% cache-miss reduction reproduced in all four passes (0.944 / 0.947 / 0.953 / 0.956) and the three arms order themselves by phase — 40 → 24 → 0 — exactly as the mechanism predicts. dTLB does not move, which it should not: alignment changes lines, not pages. cycles points the same way but its per-pass ratios scatter 0.849–0.998, so it is reported and not claimed.

And none of it is visible in time. 24 cells (4 sizes × 2 hit mixes × 3 batch sizes), 100 000 queries, 5 runs, 3 rotations: noise band median 8.2%, p90 30.2%, and aligned/compact geomean 0.998, range 0.855–1.109 — 0 of 24 cells clear their own band. Re-run at 4e6 with 1 000 000 queries and 9 runs to tighten the band to median 5.0%, p90 8.5%: ratios 0.999–1.052, still 0 of 6 clearing, and the direction is now consistently against the aligned arm by ~1%.

The 0.77-fewer-misses-per-lookup is real and is worth about 60 ns if it were ever exposed. It is not exposed, and the reason is the thing stree was chosen for: lookup_batch_pipeline keeps eight queries in flight and prefetches the next level, so the leaf touch overlaps with seven others. A miss that the machine was already hiding does not become time when you remove it.

So the default stays OidLayout::Compact — the 40 extra bytes per section and the parse-time copy into an aligned buffer buy a counter, not a latency. The apparatus stays because it is cheap, guarded, and the answer would otherwise have to be re-derived. What this does settle is that the 72–91% of a full-row lookup that crate::index_layout attributes to the oid step is not the header offset, and the next attempt on that step has to look elsewhere — STree64Mmap’s own internal-node Vec<[i64; 8]> is at glibc’s mercy exactly the way this section was, and that one is a node per level rather than one leaf touch. It lives in znippy-zoomies and is not answerable from this crate.

The key is order-preserving, and the sign bit is why

i64::from_be_bytes(oid[..8]) — the literal reading of “the first eight bytes as an i64” — is not order-preserving over oid bytes: an oid whose first byte is 0x80 or higher goes negative and sorts before every oid starting 0x00..0x7f, which is roughly half the keyspace on the wrong side. The key here therefore flips the top bit, (u64::from_be_bytes(first8) ^ (1 << 63)) as i64, which maps unsigned order onto signed order exactly. Key rank is then oid-lexicographic rank.

…and the parallel arrays are still not redundant

With an order-preserving key it is tempting to drop both parallel arrays and read them off the rank. Only one of the two can go:

• ords equals the rank for every index crate::sections::GitIndexBuilder builds, because that is where the ordinal is defined and it numbers the same oid-lexicographic sequence. It is still stored, because build_section is the lower-level API and its contract does not require the caller’s ordinal to be a rank — the ordinal is the __gunnar_reach__ bitmap space, and a caller indexing a subset of a larger archive has ordinals from the larger space. Dropping the array is 4 bytes per object and a narrower contract; it is not free, and it is not done here.
• rows is not the rank and cannot become it. A lookup row is a chunk row: an object above file_split_block_size occupies several consecutive rows, and the lookup covers every path in the archive, not only git objects — an archive holding anything besides the object store has git rows that are not contiguous at all. rows is monotonic in rank and equal to it only in the special case of a single-chunk, git-only archive.

Structs

GitOidIndex

Reader over a __gunnar_oid__ section.

OidEntry

One object as the index records it.

OidHit

What a successful lookup resolved to.

Enums

OidLayout

Where the key array starts, and therefore how the stree keyspace sits against the 64-byte cache line.

Constants

GIT_OID_MAGIC

GIT_OID_VERSION

Bumped 1 → 2 when the key became order-preserving. A v1 section holds the same bytes in the same places but sorted on a different key, so a v2 reader walking it would return wrong rows rather than fail — which is why the reader below requires an exact match instead of <=.

Functions

build_section

Serialize the __gunnar_oid__ section in the default layout. entries may be in any order; they are sorted by key here, which is what stree requires.

build_section_with_layout

build_section with the header offset chosen explicitly. The only thing layout changes is header_len and the zero padding after it — the key, row, ordinal and oid arrays are byte-identical in every layout, which is what makes the arms comparable and what aligned_and_compact_are_the_same_index_byte_for_byte asserts.

key_for_oid

The key an oid maps into: its first eight bytes as a big-endian unsigned integer, with the top bit flipped so that unsigned order becomes signed order.