crates/gunnar-bitmap/src/words.rs
//! Elementwise set algebra over `u64` lanes — and the AVX2 backend that was
//! written, measured, and thrown away.
//!
//! A fetch answered from a bitmap is `OR` then `AND NOT` (see
//! [`crate::reachability`]), and both reduce to the same primitive: walk two
//! `u64` arrays and combine them lane by lane. EWAH is word-aligned by
//! construction — literal words and run words are both 64 bits — so a literal
//! run arrives as a contiguous `&[u64]` needing no shifting and no masking.
//! That is the textbook shape for a vector unit, and it is why this was tried.
//!
//! # It does not pay, and here is the measurement
//!
//! An AVX2 backend was implemented behind runtime detection in the shape
//! `gunnar-delta`'s `scan.rs` uses: `is_x86_feature_detected!` resolved once
//! into a `OnceLock`, four `u64` lanes per instruction, portable tail. It was
//! A/B'd against the portable loop on the real path and **reverted**.
//!
//! **The corpus decides it before any timing does.** Over the 53 real `.bitmap`
//! files on oden, 2026-08-04 — 4 824 commit bitmaps, 28 001 EWAH literal runs,
//! `examples/bench.rs`:
//!
//! | literal-run length, `u64` lanes | share of runs | share of lanes |
//! |---|---|---|
//! | exactly 1 | 69.6% | 36.1% |
//! | 2 | 16.3% | 16.9% |
//! | 3..=4 | 9.0% | 15.4% |
//! | 5..=8 | 3.4% | 10.8% |
//! | 9..=32 | 1.3% | 8.7% |
//! | 33..=128 | 0.3% | 11.5% |
//! | 129..=1024 | 0.0% | 0.5% |
//!
//! **95.0% of literal runs are shorter than the four lanes of one AVX2
//! register**, and they carry 68.5% of all literal lanes. A run that cannot fill
//! one register cannot be helped by any vector unit, and it still pays the
//! dispatch: a `#[target_feature]` function cannot be inlined into a caller
//! without the feature, so every call is a real call with a real prologue.
//! Measured on oden (Threadripper PRO 3975WX, 32 cores, AVX2, no AVX-512), both
//! backends in one process, best-of-5:
//!
//! | lanes | 1 | 2 | 4 | 8 | 16 | 64 | 256 | 1024 | 8192 | 65536 |
//! |---|---|---|---|---|---|---|---|---|---|---|
//! | avx2 ÷ portable | 0.58× | 0.52× | 0.59× | 0.53× | 0.87× | 1.44× | 1.30× | 1.40× | 1.14× | 1.08× |
//!
//! The crossover is between 16 and 64 lanes, and the gain decays above 1024 as
//! the loop becomes memory-bandwidth-bound rather than instruction-bound. The
//! literal-run arm lives almost entirely in the losing half of that table.
//!
//! **The dense pair looked like the place it would pay, and it did not.** Whole
//! bitmaps are wider than literal runs — p50 83 words, p90 566, p99 1165 — so
//! `Bitmap::or_with` and `and_not_with` sit in the 1.30–1.44× region. A build
//! that dispatched *only* those and left the literal arm portable was still
//! **slower on the real path, 7 of 8 alternating pairs**, pinned to one core
//! with `taskset` to get under the box's load of 82–122:
//!
//! | pair | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
//! |---|---|---|---|---|---|---|---|---|
//! | portable, µs/query | 4.107 | 4.100 | 4.147 | 4.095 | **4.372** | 3.996 | 4.026 | 4.021 |
//! | dense-only AVX2 | 4.237 | 4.154 | 4.197 | 4.138 | **4.192** | 4.159 | 4.096 | 4.120 |
//!
//! About 1.5%, seven times out of eight. Dispatching *everywhere* was worse
//! still: 4/4 against, 23–52% slower. All three builds selected the identical
//! 417 075 objects over 9 542 queries, so this is the same work three ways and
//! not a faster build that did less.
//!
//! The reason is the one `scan.rs` names, and this is a second, independent
//! confirmation of it: the portable loop below is a bounds-check-free counted
//! loop that **LLVM auto-vectorises after inlining it into the caller**, where
//! the hand-written backend cannot inline at all. Three dense operations per
//! query at ~4 ns saved each cannot repay a call barrier on a 4 µs query, and
//! the arithmetic never favoured it — only the intuition did.
//!
//! Recorded here rather than in a commit message because the repair is obvious
//! enough that somebody will write it again. `P-022` in
//! `.nornir/performance-design.md` carries the same numbers.
//!
//! # What is kept
//!
//! [`Op`] — the scalar meaning of each operation, written once. It is the only
//! definition, so `and_not` cannot mean one thing in one loop and another
//! somewhere else, and `tests/words.rs` pins each variant against a hand-written
//! expectation. That is worth having on its own, and it is what the reverted
//! backend was routed through while it existed.
/// Which combination to apply.
///
/// The single definition of what each operation means. Every loop in this crate
/// routes through [`Op::apply`], so there is one writer and nothing to keep in
/// sync.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Op {
/// `dst |= src`.
Or,
/// `dst &= !src` — the exclusion half of a fetch.
AndNot,
/// `dst &= src`.
And,
/// `dst ^= src` — what resolves an XOR-compressed entry against its base.
Xor,
}
impl Op {
/// The operation on one lane.
#[inline(always)]
pub fn apply(self, dst: u64, src: u64) -> u64 {
match self {
Op::Or => dst | src,
Op::AndNot => dst & !src,
Op::And => dst & src,
Op::Xor => dst ^ src,
}
}
}
/// Apply `op` lane by lane over `dst[..n]` and `src[..n]`, `n` the shorter.
///
/// Truncating to the shorter length rather than growing is deliberate: growth is
/// a decision about the *set* that only [`crate::Bitmap`] can make, and making
/// it here would put two different answers in two places.
///
/// Written as a slice `zip` rather than an index loop, which is what makes it
/// worth having: it hands LLVM a bounds-check-free counted loop, the form it
/// will auto-vectorise, and it inlines into its caller so the vectoriser sees
/// the surrounding context. The version this replaced indexed with `get_mut` and
/// `break`, and a loop with an early exit cannot be vectorised at all.
#[inline]
pub fn apply(op: Op, dst: &mut [u64], src: &[u64]) {
let n = dst.len().min(src.len());
for (d, s) in dst[..n].iter_mut().zip(&src[..n]) {
*d = op.apply(*d, *s);
}
}