crates/storage-git-gix/src/fanout.rs
//! A **16-bit fanout** in front of a pack index's binary search.
//!
//! # What this is, and what it deliberately is not
//!
//! A `.idx` v2 is a sorted oid table behind a 256-entry fanout on the oid's
//! first byte: `packfile.c::bsearch_hash` indexes the fanout, then bisects a
//! ~1/256 slice. Widening that fanout to the first **two** bytes narrows the
//! slice to ~1/65 536 before the bisection starts, which is eight fewer probes
//! at every corpus size — for 65 536 `u32`s, 256 KiB, and about forty lines.
//!
//! **It changes nothing on disk.** The `.idx` is read exactly as git wrote it;
//! this is a derived table built in memory over
//! [`gix_pack::index::File::oid_at_index`], and it returns the same
//! `EntryIndex` into the same file that [`gix_pack::index::File::lookup`]
//! returns. A caller can drop it and lose only time. That is a deliberate
//! constraint, not an oversight: a sidecar file would be a second thing to
//! invalidate when a repack rewrites the pack, and the failure mode of a stale
//! oid index is a *wrong* offset, which is silent.
//!
//! # Why the binary search is written here rather than reused
//!
//! `gix_pack::index::access::lookup` is `pub(crate)` and takes `fan: &[u32; 256]`
//! by type, so it cannot be handed a different fanout's bounds. Twelve lines is
//! under LAW 5's duplication bar and there is no seam to route through; the one
//! thing that *is* shared is the oid accessor, so both searches read the same
//! bytes out of the same mapping and cannot disagree about what the table holds.
//!
//! `gix`'s version reaches the table through a `&dyn Fn(EntryIndex) -> &oid`,
//! which is an indirect call per probe. This one calls
//! [`gix_pack::index::File::oid_at_index`] directly, so part of any measured
//! difference is that and not the fanout — [`equivalent`] exists so the two are
//! held to the same answers regardless.
//!
//! # The size floor
//!
//! The table is 256 KiB **whatever `n` is**, so on `bifrost` (83 objects) it
//! would be 3 KiB per object to save probes from a bisection that is already
//! zero deep: git's 8-bit fanout leaves `n/256` entries, which is under one
//! below 256 objects. [`Fanout16::MIN_OBJECTS`] is 4 096, chosen from that
//! arithmetic rather than from a sweep — no floor other than this one was
//! measured — and below it [`Fanout16::build`] returns `None` and the caller
//! uses git's own lookup. Twelve of the nineteen `workspace_nordisk`
//! repositories are under it.
//!
//! # ⚠ This is OFF by default, and that is the finding
//!
//! [`crate::packs::PackSet`] builds one only when asked — `PackSet::load_with`,
//! or `GIX_FANOUT16=on` in the environment. The structure works —
//! `pack_position` was 3.9–4.4x faster on hits and 8.6–9.2x on misses over the
//! seven corpus repositories above the floor (MEASURED **on oden**, 2026-08-04,
//! release, shuffled query order, by the code this module was lifted from) —
//! and a negotiated fetch moved **1.0016–1.0076x**, every run of it smaller
//! than that run's own noise band.
//!
//! Off by *design*, not by omission. **Nothing in this crate has re-measured
//! either figure**: the numbers above are oden's, this is t14s, and §7 of
//! `locked_on_target.md` forbids comparing across machines. Treat the micro-win
//! as history and the end-to-end null as the operative fact until an arm on
//! this box says otherwise.
//!
//! # Why it earns a filesystem, when the znippy arm may not have one
//!
//! It reads a `.idx`, which the filesystem rule strikes from the *znippy*
//! implementation's advice. This is the gix arm: a `.idx` on disk **is** its
//! storage format, so a structure over one is not a coupling it could shed.
/// Entries in the table: one per value of the oid's first two bytes.
const WIDTH: usize = 65_536;
/// A cumulative histogram of the first **two** bytes of every oid in a pack
/// index, in the same shape as the `.idx`'s own 256-entry fanout.
///
/// `table[b]` is the number of oids whose first two bytes are `<= b`, so the
/// slice for `b` is `table[b-1]..table[b]` — identical to how git reads its own
/// fanout, one byte wider.
pub struct Fanout16 {
table: Box<[u32]>,
/// Lookups answered through this table, **debug builds only**.
///
/// The one thing about this structure that is not observable from its
/// answers. Both searches return the same entry index by definition, so a
/// `PackBitmap` that builds a `Fanout16` and then never consults it is
/// indistinguishable from one that does — MEASURED, not supposed: with
/// `entry_index` changed to ignore the field, all seven tests in
/// `tests/fanout16_finds_what_git_finds.rs` stayed green, including the one
/// whose whole job is to assert the A/B arms differ. That is the identity
/// trap in its purest form, and it would have made the end-to-end
/// measurement report a null result for a disconnected wire.
///
/// `#[cfg(debug_assertions)]` because the counter sits in the hot path this
/// type exists to shorten: a relaxed `fetch_add` is on the order of a
/// nanosecond against a lookup of fifteen. The wiring it proves is one
/// source line, shared by both builds, which is the same ground
/// `debug_assert!` stands on — and the release build's wiring is asserted
/// instead by the A/B run, which must move.
#[cfg(debug_assertions)]
probes: std::sync::atomic::AtomicU64,
}
impl std::fmt::Debug for Fanout16 {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Fanout16")
.field("objects", &self.table[WIDTH - 1])
.field("resident_bytes", &self.resident_bytes())
.finish()
}
}
impl Fanout16 {
/// Below this many objects the 256 KiB is not worth paying.
///
/// At `n` objects git's own fanout leaves a slice of about `n/256`, so the
/// bisection it still has to do is `log2(n/256)` probes — which is **zero**
/// below 512 objects and three at 2048. There is nothing for a wider fanout
/// to remove down there, and 256 KiB is more than the whole `.idx`.
pub const MIN_OBJECTS: u32 = 4096;
/// Build the table over `idx`, or `None` if it holds fewer than
/// [`Fanout16::MIN_OBJECTS`] objects.
///
/// One linear pass to count and one over the 65 536 buckets to accumulate.
pub fn build<T: gix_pack::FileData>(idx: &gix_pack::index::File<T>) -> Option<Self> {
(idx.num_objects() >= Self::MIN_OBJECTS).then(|| Self::build_unfloored(idx))
}
/// The table over `idx` whatever its size, floor ignored.
///
/// [`Fanout16::MIN_OBJECTS`] is an economics decision — 256 KiB is not worth
/// paying for a pack of eighty objects — and correctness is not a property
/// the small packs get to skip because of it. A conformance sweep that only
/// ever built tables over the packs production would build them over would
/// leave the narrow-slice arithmetic untested at exactly the sizes where
/// `lo == hi` on nearly every query.
pub fn build_unfloored<T: gix_pack::FileData>(idx: &gix_pack::index::File<T>) -> Self {
let n = idx.num_objects();
let mut table = vec![0u32; WIDTH];
for i in 0..n {
let bytes = idx.oid_at_index(i).as_bytes();
table[(usize::from(bytes[0]) << 8) | usize::from(bytes[1])] += 1;
}
let mut acc = 0u32;
for c in table.iter_mut() {
acc += *c;
*c = acc;
}
debug_assert_eq!(acc, n, "the fanout must account for every object");
Fanout16::from_table(table)
}
/// A table this module did not build, for a test that needs a **wrong** one.
///
/// The alternative is an env switch inside [`Fanout16::build`], and a red
/// that lives in the shipping path is a branch production can take. This
/// keeps the corruption in the test file, where it can only be reached by a
/// caller that wrote it out.
///
/// # Panics
///
/// If `table` is not 65 536 entries.
#[doc(hidden)]
pub fn from_table_for_tests(table: Vec<u32>) -> Self {
assert_eq!(table.len(), WIDTH, "a fanout16 has {WIDTH} entries");
Fanout16::from_table(table)
}
fn from_table(table: Vec<u32>) -> Self {
Fanout16 {
table: table.into_boxed_slice(),
#[cfg(debug_assertions)]
probes: std::sync::atomic::AtomicU64::new(0),
}
}
/// Lookups this table has answered. Always `0` in a release build; see the
/// field.
pub fn probes(&self) -> u64 {
#[cfg(debug_assertions)]
{
self.probes.load(std::sync::atomic::Ordering::Relaxed)
}
#[cfg(not(debug_assertions))]
{
0
}
}
/// Bytes this table occupies. 256 KiB, per open pack, whatever `n` is.
pub fn resident_bytes(&self) -> usize {
self.table.len() * std::mem::size_of::<u32>()
}
/// The `[lo, hi)` entry range the first two bytes of `id` narrow to.
#[inline]
fn bounds(&self, id: &gix_hash::oid) -> (u32, u32) {
let bytes = id.as_bytes();
let b = (usize::from(bytes[0]) << 8) | usize::from(bytes[1]);
(if b == 0 { 0 } else { self.table[b - 1] }, self.table[b])
}
/// The entry index of `id` in `idx`, or `None`.
///
/// Answers exactly what [`gix_pack::index::File::lookup`] answers; see
/// [`equivalent`].
#[inline]
pub fn lookup<T: gix_pack::FileData>(
&self,
idx: &gix_pack::index::File<T>,
id: &gix_hash::oid,
) -> Option<u32> {
#[cfg(debug_assertions)]
self.probes
.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let (mut lo, mut hi) = self.bounds(id);
while lo < hi {
let mid = u32::midpoint(lo, hi);
match id.cmp(idx.oid_at_index(mid)) {
std::cmp::Ordering::Less => hi = mid,
std::cmp::Ordering::Greater => lo = mid + 1,
std::cmp::Ordering::Equal => return Some(mid),
}
}
None
}
}
/// **Every** oid in `idx` resolves to the same entry index through both
/// searches, and a one-byte mutation of each resolves to `None` through both.
///
/// A lookup structure that silently misses is catastrophic and looks fast, and
/// a spot check over sampled ids cannot see a single displaced bucket boundary.
/// This is `O(n)` and is meant to be run over a whole corpus by a test, not per
/// open.
///
/// The mutation is of the **second** byte, deliberately: that is the byte the
/// wider fanout added, so a table built with the two bytes swapped, or
/// accumulated off by one, sends the query to the wrong slice and the search
/// finds nothing where git's still finds something. Mutating the first byte
/// would be answered identically by both fanouts and would prove nothing about
/// the eight new bits.
///
/// `Err` names the first disagreement rather than counting them: one is already
/// a wrong pack offset.
pub fn equivalent<T: gix_pack::FileData>(
idx: &gix_pack::index::File<T>,
fanout: &Fanout16,
) -> std::result::Result<u32, String> {
let n = idx.num_objects();
for i in 0..n {
let id = idx.oid_at_index(i).to_owned();
let mine = fanout.lookup(idx, &id);
let theirs = idx.lookup(id);
if mine != theirs {
return Err(format!(
"{id}: fanout16 says {mine:?}, .idx says {theirs:?}"
));
}
if mine != Some(i) {
return Err(format!("{id} is entry {i} but resolved to {mine:?}"));
}
let mut bytes = id.as_bytes().to_vec();
bytes[1] ^= 0xff;
let absent = gix_hash::oid::try_from_bytes(&bytes).expect("the same hash width");
// A mutation can legitimately land on another object in the pack; only
// an id the `.idx` itself does not hold is a miss worth comparing.
if idx.lookup(absent).is_none() && fanout.lookup(idx, absent).is_some() {
return Err(format!(
"{absent} is not in the .idx but fanout16 resolved it to {:?}",
fanout.lookup(idx, absent)
));
}
}
Ok(n)
}