bench/src/oid_index.rs
//! **oid → pack offset**: git's `.idx` fanout+binary-search against a ragnar
//! static tree (`znippy_zoomies::stree::STree64`), point and batched.
//!
//! Self-contained on purpose — `memmap2`, `std`, and the tree. It reads real
//! `.idx` v2 files off disk and never synthesises an oid, because a hash of a
//! generated blob is a real hash but a made-up 20-byte string is not an oid.
//!
//! ## Why `STree64` and not `STree32`
//!
//! Neither tree can hold an oid: `STree32`'s key is a `u32` and `STree64`'s is
//! an `i64`, and an oid is 160 or 256 bits. So *any* stree over oids is a tree
//! over a **prefix**, plus a verification of the full oid at the position the
//! tree lands on — which is exactly the last step `.idx`'s binary search does
//! anyway, so the two structures answer the same question and return the same
//! index.
//!
//! The prefix width is then the whole design choice, and it is a collision
//! question. Over `n` oids the expected number of colliding prefix pairs is
//! `n²/2^(w+1)`:
//!
//! | n | 32-bit prefix | 64-bit prefix |
//! |---|---|---|
//! | 352 396 | ~14.5 pairs | ~3.4e-9 |
//! | 1 000 000 | ~116 pairs | ~2.7e-8 |
//!
//! A collision is not a correctness bug either way (both widths fall through to
//! a forward scan over equal prefixes), but at 32 bits the scan is on the hot
//! path for a measurable fraction of queries and its length is data-dependent.
//! At 64 bits it is one comparison, always, on every corpus that fits in a
//! forge. Both are measured here — [`OidStree32`] exists so the choice is a
//! number rather than an assertion — and the 64-bit width is the one the
//! verdict is written against.
use std::path::Path;
use znippy_zoomies::stree::STree64;
use znippy_zoomies::stree32::STree32;
// ───────────────────────────────────────────────────────────────────────────
// git's `.idx` v2, as git implements it
// ───────────────────────────────────────────────────────────────────────────
/// `\377tOc` + version 2.
const IDX_MAGIC: [u8; 8] = [0xff, b't', b'O', b'c', 0, 0, 0, 2];
/// Byte offset of the 256-entry fanout table.
const FANOUT_AT: usize = 8;
/// Byte offset of the sorted oid table.
const OIDS_AT: usize = FANOUT_AT + 256 * 4;
/// A memory-mapped pack index, read exactly the way `packfile.c` reads one.
pub struct PackIdx {
map: memmap2::Mmap,
/// `fanout[255]`.
pub n: usize,
/// 20 for sha1, 32 for sha256.
pub hashlen: usize,
/// Byte offset of the 4-byte offset table.
off_at: usize,
/// Byte offset of the 8-byte large-offset table.
large_at: usize,
}
impl PackIdx {
pub fn open(path: &Path) -> anyhow::Result<Self> {
let file = std::fs::File::open(path)?;
// SAFETY: the fixture packs are not written while a bench runs; the
// corpus is built once and repacked before any arm opens it.
let map = unsafe { memmap2::Mmap::map(&file)? };
anyhow::ensure!(
map.len() > OIDS_AT && map[..8] == IDX_MAGIC,
"{} is not a v2 pack index",
path.display()
);
let n = u32::from_be_bytes(map[OIDS_AT - 4..OIDS_AT].try_into().unwrap()) as usize;
anyhow::ensure!(n > 0, "{} indexes zero objects", path.display());
// Two hash widths are possible and a `.idx` v2 does not say which; git
// gets it from the repository's `extensions.objectFormat`, which a
// standalone reader has not got.
//
// The file length ALONE does not decide it, and believing it does was a
// real bug in this reader: for the 1 000 000-object sha256 fixture,
// `8 + 1024 + n*(20+8) + 40` fits inside the file and leaves a multiple
// of 8 over, so a length test picks sha1 and every oid read after that is
// garbage — and garbage that all eight arms then agree about, because
// they all read it through here. It was caught by the `git verify-pack`
// oracle finding zero objects it could match, which is the only check in
// this file that does not go through this function.
//
// So the width is decided STRUCTURALLY: the fanout table is a cumulative
// histogram of first bytes, so at the right width every one of its 256
// boundaries lands exactly where the first byte changes. At the wrong
// width it does not.
let fits = |h: usize| -> bool {
let fixed = OIDS_AT + n * (h + 8) + 2 * h;
if map.len() < fixed || (map.len() - fixed) % 8 != 0 {
return false;
}
for b in 0..256usize {
let at = FANOUT_AT + b * 4;
let c = u32::from_be_bytes(map[at..at + 4].try_into().unwrap()) as usize;
if c > n {
return false;
}
if c > 0 && map[OIDS_AT + (c - 1) * h] as usize > b {
return false;
}
if c < n && (map[OIDS_AT + c * h] as usize) <= b {
return false;
}
}
true
};
let hashlen = [20usize, 32]
.into_iter()
.find(|&h| fits(h))
.ok_or_else(|| anyhow::anyhow!("{}: no hash width fits the fanout", path.display()))?;
let off_at = OIDS_AT + n * hashlen + n * 4;
let large_at = off_at + n * 4;
Ok(Self {
map,
n,
hashlen,
off_at,
large_at,
})
}
#[inline]
fn fanout(&self, b: usize) -> usize {
let at = FANOUT_AT + b * 4;
u32::from_be_bytes(self.map[at..at + 4].try_into().unwrap()) as usize
}
/// The `i`-th oid in sorted order.
#[inline]
pub fn oid(&self, i: usize) -> &[u8] {
let at = OIDS_AT + i * self.hashlen;
&self.map[at..at + self.hashlen]
}
/// The whole sorted oid table, as raw bytes.
pub fn oid_table(&self) -> &[u8] {
&self.map[OIDS_AT..OIDS_AT + self.n * self.hashlen]
}
/// The pack offset of the `i`-th object, large-offset indirection included.
#[inline]
pub fn offset(&self, i: usize) -> u64 {
let at = self.off_at + i * 4;
let raw = u32::from_be_bytes(self.map[at..at + 4].try_into().unwrap());
if raw & 0x8000_0000 == 0 {
raw as u64
} else {
let j = (raw & 0x7fff_ffff) as usize;
let at = self.large_at + j * 8;
u64::from_be_bytes(self.map[at..at + 8].try_into().unwrap())
}
}
/// **git's algorithm**: index the 256-entry fanout on the oid's first byte,
/// then binary-search the ~1/256 slice. `packfile.c::bsearch_hash`.
#[inline]
pub fn find(&self, oid: &[u8]) -> Option<usize> {
let b = oid[0] as usize;
let mut lo = if b == 0 { 0 } else { self.fanout(b - 1) };
let mut hi = self.fanout(b);
while lo < hi {
let mid = (lo + hi) / 2;
match self.oid(mid).cmp(oid) {
std::cmp::Ordering::Less => lo = mid + 1,
std::cmp::Ordering::Greater => hi = mid,
std::cmp::Ordering::Equal => return Some(mid),
}
}
None
}
/// The same fanout, then a binary search that compares only the **leading 8
/// bytes** as a big-endian `u64`, verifying the full oid once at the end.
///
/// The second control. It is git's structure, git's memory, and git's fanout,
/// with the tree's *key* — one integer compare per probe instead of a
/// `memcmp` of 20 or 32 bytes. If this closes most of the gap, the win is the
/// key width and not the layout.
#[inline]
pub fn find_u64key(&self, oid: &[u8]) -> Option<usize> {
let q = u64::from_be_bytes(oid[..8].try_into().unwrap());
let b = oid[0] as usize;
let mut lo = if b == 0 { 0 } else { self.fanout(b - 1) };
let mut hi = self.fanout(b);
// lower_bound on the prefix, because equal prefixes are legal.
while lo < hi {
let mid = (lo + hi) / 2;
let at = OIDS_AT + mid * self.hashlen;
let k = u64::from_be_bytes(self.map[at..at + 8].try_into().unwrap());
if k < q {
lo = mid + 1;
} else {
hi = mid;
}
}
while lo < self.n {
let at = OIDS_AT + lo * self.hashlen;
if u64::from_be_bytes(self.map[at..at + 8].try_into().unwrap()) != q {
return None;
}
if &self.map[at..at + self.hashlen] == oid {
return Some(lo);
}
lo += 1;
}
None
}
/// The same search with `P` queries in flight, each prefetching the cache
/// line its next probe will read.
///
/// **This is the control that decides whether a batch win belongs to the
/// tree or to the batching.** git does not do this; nothing stops it. If a
/// pipelined binary search closes most of the gap to the tree, then the
/// finding is "resolve oids in bulk", not "use a static tree".
pub fn find_batch_pipelined<const P: usize>(
&self,
oids: &[&[u8]],
out: &mut Vec<Option<usize>>,
) {
self.pipelined::<P, _>(oids, |o| self.byte_bounds(o), false, out)
}
/// The `[lo, hi)` slice git's 256-entry fanout narrows an oid to.
#[inline]
pub fn byte_bounds(&self, oid: &[u8]) -> (usize, usize) {
let b = oid[0] as usize;
(if b == 0 { 0 } else { self.fanout(b - 1) }, self.fanout(b))
}
/// `P` binary searches in flight over the `.idx` oid table.
///
/// `bounds` supplies each query's starting slice, so the same pipeline serves
/// git's 8-bit fanout and the 16-bit one — the alternative is two copies of
/// this loop, which is exactly the twin to avoid.
///
/// `u64key` picks the comparison: `false` is git's `memcmp` of the whole oid,
/// `true` is a `lower_bound` on the leading big-endian `u64` followed by one
/// full-oid verification. The strongest cheap baseline is `bounds` = 16-bit
/// fanout and `u64key` = true, and it exists so the verdict is not decided by
/// a weak opponent.
pub fn pipelined<const P: usize, F: Fn(&[u8]) -> (usize, usize)>(
&self,
oids: &[&[u8]],
bounds: F,
u64key: bool,
out: &mut Vec<Option<usize>>,
) {
out.clear();
out.resize(oids.len(), None);
let h = self.hashlen;
let table = self.oid_table();
let key = |i: usize| -> u64 {
let at = i * h;
u64::from_be_bytes(table[at..at + 8].try_into().unwrap())
};
#[derive(Clone, Copy)]
struct Q {
slot: usize,
lo: usize,
hi: usize,
live: bool,
}
let mut lanes = [Q {
slot: 0,
lo: 0,
hi: 0,
live: false,
}; P];
let mut next = 0usize;
let mut live = 0usize;
// The lower_bound tail: `lo` is the first index whose prefix is >= the
// query, so walk equal prefixes until the full oid matches.
let verify = |slot: usize, mut lo: usize| -> Option<usize> {
let q = u64::from_be_bytes(oids[slot][..8].try_into().unwrap());
while lo < self.n && key(lo) == q {
let at = lo * h;
if &table[at..at + h] == oids[slot] {
return Some(lo);
}
lo += 1;
}
None
};
macro_rules! refill {
($lane:expr) => {
if next < oids.len() {
let (lo, hi) = bounds(oids[next]);
$lane = Q {
slot: next,
lo,
hi,
live: true,
};
next += 1;
live += 1;
if lo < hi {
prefetch(table, ((lo + hi) / 2) * h);
}
}
};
}
for lane in lanes.iter_mut() {
refill!(*lane);
}
while live > 0 {
for lane in lanes.iter_mut() {
if !lane.live {
continue;
}
if lane.lo >= lane.hi {
if u64key {
out[lane.slot] = verify(lane.slot, lane.lo);
}
lane.live = false;
live -= 1;
} else {
let mid = (lane.lo + lane.hi) / 2;
if u64key {
let q = u64::from_be_bytes(oids[lane.slot][..8].try_into().unwrap());
if key(mid) < q {
lane.lo = mid + 1;
} else {
lane.hi = mid;
}
} else {
let at = mid * h;
match table[at..at + h].cmp(oids[lane.slot]) {
std::cmp::Ordering::Less => lane.lo = mid + 1,
std::cmp::Ordering::Greater => lane.hi = mid,
std::cmp::Ordering::Equal => {
out[lane.slot] = Some(mid);
lane.live = false;
live -= 1;
}
}
}
if lane.live {
prefetch(table, ((lane.lo + lane.hi) / 2) * h);
continue;
}
}
refill!(*lane);
}
}
}
}
#[inline(always)]
fn prefetch(buf: &[u8], at: usize) {
#[cfg(target_arch = "x86_64")]
unsafe {
if at < buf.len() {
std::arch::x86_64::_mm_prefetch(
buf.as_ptr().add(at) as *const i8,
std::arch::x86_64::_MM_HINT_T0,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
let _ = (buf, at);
}
// ───────────────────────────────────────────────────────────────────────────
// A wider fanout, which is the cheap thing git could do instead
// ───────────────────────────────────────────────────────────────────────────
/// A 65 536-entry fanout on the oid's first **two** bytes, over the same sorted
/// oid table.
///
/// Eight more radix bits, 256 KiB, and about forty lines. It is here because a
/// comparison of a tree against a 256-entry fanout that ignores the 65 536-entry
/// one is a comparison that has already chosen its answer: if the win is "narrow
/// the slice before you search it", the fanout is the version of that idea git
/// already ships and can extend without a new data structure.
pub struct Fanout16 {
table: Vec<u32>,
}
impl Fanout16 {
pub fn build(idx: &PackIdx) -> Self {
let mut table = vec![0u32; 65_536];
for i in 0..idx.n {
let o = idx.oid(i);
let b = ((o[0] as usize) << 8) | o[1] as usize;
table[b] += 1;
}
let mut acc = 0u32;
for c in table.iter_mut() {
acc += *c;
*c = acc;
}
Self { table }
}
pub fn resident_bytes(&self) -> usize {
self.table.len() * 4
}
/// The `[lo, hi)` slice the 16-bit fanout narrows an oid to.
#[inline]
pub fn bounds(&self, oid: &[u8]) -> (usize, usize) {
let b = ((oid[0] as usize) << 8) | oid[1] as usize;
(
if b == 0 {
0
} else {
self.table[b - 1] as usize
},
self.table[b] as usize,
)
}
#[inline]
pub fn find(&self, idx: &PackIdx, oid: &[u8]) -> Option<usize> {
let (mut lo, mut hi) = self.bounds(oid);
while lo < hi {
let mid = (lo + hi) / 2;
match idx.oid(mid).cmp(oid) {
std::cmp::Ordering::Less => lo = mid + 1,
std::cmp::Ordering::Greater => hi = mid,
std::cmp::Ordering::Equal => return Some(mid),
}
}
None
}
}
// ───────────────────────────────────────────────────────────────────────────
// the ragnar tree over an oid prefix
// ───────────────────────────────────────────────────────────────────────────
/// The top 8 bytes of an oid as an **order-preserving** `i64`.
///
/// oids are sorted lexicographically, so their leading bytes read big-endian are
/// a non-decreasing `u64` sequence. `STree64`'s key is signed, and AVX2 only has
/// a signed 64-bit compare, so the unsigned order is mapped onto the signed one
/// by flipping the sign bit — the same trick `stree32::count_lt` applies per lane
/// for `u32`.
#[inline]
pub fn key64(oid: &[u8]) -> i64 {
(u64::from_be_bytes(oid[..8].try_into().unwrap()) ^ (1u64 << 63)) as i64
}
/// The top 4 bytes, big-endian. `STree32`'s key is already `u32`.
#[inline]
pub fn key32(oid: &[u8]) -> u32 {
u32::from_be_bytes(oid[..4].try_into().unwrap())
}
/// `STree64` over the 64-bit oid prefix, verifying the full oid at the position
/// the tree lands on.
pub struct OidStree {
tree: STree64,
/// Bytes the tree itself occupies (`Vec<[i64; 8]>` plus the offsets vector).
pub resident_bytes: usize,
/// How many oids share their 64-bit prefix with the one before them. The
/// number that says whether the forward scan below is ever entered.
pub prefix_dups: usize,
}
impl OidStree {
pub fn build(idx: &PackIdx) -> Self {
let mut keys = Vec::with_capacity(idx.n);
let mut dups = 0usize;
for i in 0..idx.n {
let k = key64(idx.oid(i));
if i > 0 && keys[i - 1] == k {
dups += 1;
}
keys.push(k);
}
// RED, on demand. A contiguous band of keys in the middle of the corpus
// is flattened onto one value, so every oid in that band routes to the
// wrong leaf and the tree answers `None` where the `.idx` answers
// `Some(i)`.
//
// The first version of this switch displaced exactly ONE key, and it
// passed: 2 000 random probes over 12 328 oids simply never asked for
// that one. A red probe that fires with probability 0.16 is not a red
// probe, so the corruption is now a band the deterministic sweep in
// `verify_against_idx` is guaranteed to walk into.
if std::env::var("GUNNAR_BENCH_OIDINDEX_RED").as_deref() == Ok("agree") && idx.n > 16 {
let lo = idx.n / 4;
let hi = idx.n - idx.n / 4;
let v = keys[lo];
for k in keys[lo..hi].iter_mut() {
*k = v;
}
eprintln!("RED[agree]: stree64 keys {lo}..{hi} flattened onto one value");
}
let tree = STree64::new(&keys);
// `Vec<[i64; 8]>` of `n_blocks`, plus one `usize` per level. The block
// count is not exposed, so it is recomputed the way `new` computes it:
// ceil(n/8) leaves and a 1/9-geometric tail of internal layers.
let mut blocks = 0usize;
let mut layer = idx.n.div_ceil(8);
loop {
blocks += layer;
if layer == 1 {
break;
}
layer = layer.div_ceil(9);
}
Self {
tree,
resident_bytes: blocks * 64,
prefix_dups: dups,
}
}
/// One lookup. `find_exact` returns the **first** index whose prefix equals
/// the query (it is a `count_lt` lower bound), so equal prefixes are walked
/// forward until the full oid matches or the prefix changes.
#[inline]
pub fn find(&self, idx: &PackIdx, oid: &[u8]) -> Option<usize> {
let q = key64(oid);
let mut p = self.tree.find_exact(q)?;
while p < idx.n && key64(idx.oid(p)) == q {
if idx.oid(p) == oid {
return Some(p);
}
p += 1;
}
None
}
/// `P` queries in flight through `batch_stream`, then the same verification.
pub fn find_batch<const P: usize>(
&self,
idx: &PackIdx,
oids: &[&[u8]],
keys: &mut Vec<i64>,
out: &mut Vec<Option<usize>>,
) {
keys.clear();
keys.extend(oids.iter().map(|o| key64(o)));
let raw = self.tree.batch_stream::<P>(keys);
out.clear();
out.reserve(oids.len());
for (slot, hit) in raw.into_iter().enumerate() {
let mut ans = None;
if let Some(mut p) = hit {
let q = keys[slot];
while p < idx.n && key64(idx.oid(p)) == q {
if idx.oid(p) == oids[slot] {
ans = Some(p);
break;
}
p += 1;
}
}
out.push(ans);
}
}
}
/// A plain sorted `Vec<i64>` of **exactly the keys the tree is built from**,
/// searched with `slice::partition_point`.
///
/// **The decisive control.** Same key, same width, same memory (8 bytes per oid
/// against the tree's ~9), same verification step, same corpus — only the layout
/// differs: a sorted array binary-searched, against an implicit S+tree with a
/// branchless SIMD node compare and a prefetched pipeline. Whatever separates
/// `stree64_*` from this arm is the S+tree, and nothing else is.
pub struct KeyColumn {
keys: Vec<i64>,
}
impl KeyColumn {
pub fn build(idx: &PackIdx) -> Self {
Self {
keys: (0..idx.n).map(|i| key64(idx.oid(i))).collect(),
}
}
pub fn resident_bytes(&self) -> usize {
self.keys.len() * 8
}
#[inline]
pub fn find(&self, idx: &PackIdx, oid: &[u8]) -> Option<usize> {
let q = key64(oid);
let mut p = self.keys.partition_point(|&k| k < q);
while p < idx.n && self.keys[p] == q {
if idx.oid(p) == oid {
return Some(p);
}
p += 1;
}
None
}
}
/// `STree32` over the 32-bit oid prefix. The same shape, a narrower key, and a
/// forward scan that is entered far more often.
pub struct OidStree32 {
tree: STree32,
pub resident_bytes: usize,
pub prefix_dups: usize,
}
impl OidStree32 {
pub fn build(idx: &PackIdx) -> Self {
let mut keys = Vec::with_capacity(idx.n);
let mut dups = 0usize;
for i in 0..idx.n {
let k = key32(idx.oid(i));
if i > 0 && keys[i - 1] == k {
dups += 1;
}
keys.push(k);
}
let tree = STree32::new(&keys);
let mut blocks = 0usize;
let mut layer = idx.n.div_ceil(16);
loop {
blocks += layer;
if layer == 1 {
break;
}
layer = layer.div_ceil(17);
}
Self {
tree,
resident_bytes: blocks * 64,
prefix_dups: dups,
}
}
#[inline]
pub fn find(&self, idx: &PackIdx, oid: &[u8]) -> Option<usize> {
let q = key32(oid);
let mut p = self.tree.find_exact(q)?;
while p < idx.n && key32(idx.oid(p)) == q {
if idx.oid(p) == oid {
return Some(p);
}
p += 1;
}
None
}
pub fn find_batch<const P: usize>(
&self,
idx: &PackIdx,
oids: &[&[u8]],
keys: &mut Vec<u32>,
out: &mut Vec<Option<usize>>,
) {
keys.clear();
keys.extend(oids.iter().map(|o| key32(o)));
let raw = self.tree.batch_stream::<P>(keys);
out.clear();
out.reserve(oids.len());
for (slot, hit) in raw.into_iter().enumerate() {
let mut ans = None;
if let Some(mut p) = hit {
let q = keys[slot];
while p < idx.n && key32(idx.oid(p)) == q {
if idx.oid(p) == oids[slot] {
ans = Some(p);
break;
}
p += 1;
}
}
out.push(ans);
}
}
}