crates/gunnar-delta/src/scan.rs
//! Match extension: the one place SIMD earns its keep, and the measurement.
//!
//! # What is and is not vectorisable here
//!
//! The encoder has two inner loops. The **rolling hash** is not a candidate: it
//! is a serial recurrence, each byte's state depending on the previous byte's,
//! and a vector unit cannot break that dependency. The **match scan** is: once a
//! 16-byte anchor has hashed equal, extending the match is a plain byte-wise
//! comparison of two slices, and that is a 32-bytes-per-instruction operation on
//! any machine made since 2013.
//!
//! So this module vectorises the extension and leaves the hash alone. Measured
//! figures come from `examples/bench.rs`, and the honest summary is that the win
//! is large on long matches — which is where the time goes on a repository with
//! real revision churn — and *negative* on short ones. The section below is that
//! second half, and what happened when it was fixed.
//!
//! # Runtime detection, not `target-cpu`
//!
//! The dispatch is `is_x86_feature_detected!`, resolved once into a `OnceLock`.
//! A crate that requires `-C target-cpu=native` is a crate that silently runs
//! its slow path in every distribution build, and the caller never finds out.
//!
//! # The dispatch overhead, and the fix that was measured and thrown away
//!
//! A `#[target_feature]` function cannot be inlined into a caller that does not
//! itself carry the feature, so every call below is a real call with a real
//! prologue, and at a 16-byte answer the AVX2 path cannot even enter its vector
//! loop, so that prologue buys nothing. Measured on a Threadripper PRO 3975WX
//! (32 cores, AVX2) on an otherwise idle machine, three repetitions:
//!
//! | match length | 16 | 32 | 64 | 256 | 1024 | 8192 | 65536 |
//! |---|---|---|---|---|---|---|---|
//! | dispatched ÷ portable | 0.62–0.74× | 0.75–0.79× | 0.99–1.00× | 1.57–1.58× | 3.38–3.42× | 2.28–2.42× | 2.01–2.02× |
//!
//! The crossover is at 64 bytes and it reproduces. **Below it, turning the
//! `simd` feature on makes this primitive slower.**
//!
//! The obvious repair is to compare the first 32 bytes inline and dispatch only
//! the remainder. It was written, and it does exactly what the microbenchmark
//! asks: the 16-byte row goes from losing to winning, reproducibly.
//!
//! **It was reverted, because on the encoder's real work it is slower.** Four
//! A/B pairs of the single-threaded window search over 384 near-duplicate
//! 192 KiB objects, alternating builds back to back under the same cgroup:
//!
//! | | inline head | straight dispatch |
//! |---|---|---|
//! | pair 1 | 139.89 ms | 134.17 ms |
//! | pair 2 | 138.67 ms | 136.99 ms |
//! | pair 3 | 136.22 ms | 135.13 ms |
//! | pair 4 | 139.08 ms | 136.82 ms |
//!
//! Four out of four, about 2% — small, but never once the other way. The
//! microbenchmark was measuring a case the encoder does not have. A candidate
//! only reaches this function after its 16-byte anchor hash matched *and* its
//! stored 32-bit filter matched, so a call with a short answer means a hash
//! collision, and those are rare by construction. Nearly every real call carries
//! a long match, where the head split is pure added work.
//!
//! The lesson lives in the module docs rather than in a commit message because the
//! repair is obvious enough that somebody will write it again.
//!
//! # The guard
//!
//! `simd_and_portable_agree_at_every_alignment_and_length` in `tests/scan.rs`
//! runs both implementations over every alignment and every match length in a
//! range and asserts byte-equal answers. The SIMD path is not permitted to change the output of this crate at
//! all, not the delta bytes and not their length. That property is what makes
//! `--no-default-features` a supported configuration rather than a second
//! encoder to keep in sync.
use std::sync::OnceLock;
/// Which implementation [`common_prefix_len`] and [`common_suffix_len`] resolved to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Backend {
/// Word-at-a-time, portable, no target feature required.
Portable,
/// 32 bytes per compare via AVX2, chosen at runtime.
Avx2,
}
fn detect() -> Backend {
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
{
if std::arch::is_x86_feature_detected!("avx2") {
return Backend::Avx2;
}
}
Backend::Portable
}
static BACKEND: OnceLock<Backend> = OnceLock::new();
/// The implementation this process resolved to. Stable for the process lifetime.
pub fn backend() -> Backend {
*BACKEND.get_or_init(detect)
}
/// Length of the longest common prefix of `a` and `b`.
#[inline]
pub fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
match backend() {
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
Backend::Avx2 => {
// SAFETY: `backend()` only ever returns `Avx2` after
// `is_x86_feature_detected!("avx2")` returned true in `detect`, and
// the answer is memoised, so this arm is unreachable without AVX2.
unsafe { avx2::common_prefix_len(a, b) }
}
_ => portable::common_prefix_len(a, b),
}
}
/// Length of the longest common suffix of `a` and `b`.
#[inline]
pub fn common_suffix_len(a: &[u8], b: &[u8]) -> usize {
match backend() {
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
Backend::Avx2 => {
// SAFETY: see `common_prefix_len`.
unsafe { avx2::common_suffix_len(a, b) }
}
_ => portable::common_suffix_len(a, b),
}
}
/// The portable implementations, public so a differential test and a bench can
/// reach them without a feature flag.
pub mod portable {
const W: usize = std::mem::size_of::<u64>();
#[inline]
fn first_differing_byte(xor: u64) -> usize {
if cfg!(target_endian = "little") {
xor.trailing_zeros() as usize / 8
} else {
xor.leading_zeros() as usize / 8
}
}
#[inline]
fn last_differing_byte(xor: u64) -> usize {
if cfg!(target_endian = "little") {
xor.leading_zeros() as usize / 8
} else {
xor.trailing_zeros() as usize / 8
}
}
/// Word-at-a-time longest common prefix.
#[inline]
pub fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let mut i = 0;
while i + W <= n {
let x = u64::from_ne_bytes(a[i..i + W].try_into().expect("W bytes"));
let y = u64::from_ne_bytes(b[i..i + W].try_into().expect("W bytes"));
if x != y {
return i + first_differing_byte(x ^ y);
}
i += W;
}
while i < n && a[i] == b[i] {
i += 1;
}
i
}
/// Word-at-a-time longest common suffix.
#[inline]
pub fn common_suffix_len(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let (a, b) = (&a[a.len() - n..], &b[b.len() - n..]);
let mut i = 0;
while i + W <= n {
let at = n - i - W;
let x = u64::from_ne_bytes(a[at..at + W].try_into().expect("W bytes"));
let y = u64::from_ne_bytes(b[at..at + W].try_into().expect("W bytes"));
if x != y {
return i + last_differing_byte(x ^ y);
}
i += W;
}
while i < n && a[n - i - 1] == b[n - i - 1] {
i += 1;
}
i
}
}
/// AVX2, chosen at runtime by [`backend`].
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
pub mod avx2 {
use std::arch::x86_64::{__m256i, _mm256_cmpeq_epi8, _mm256_loadu_si256, _mm256_movemask_epi8};
const V: usize = 32;
/// # Safety
/// The caller must have established that AVX2 is available.
#[target_feature(enable = "avx2")]
pub unsafe fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let mut i = 0;
while i + V <= n {
// SAFETY: `i + V <= n <= a.len().min(b.len())`, so both 32-byte
// reads are in bounds of their slice; `loadu` needs no alignment;
// AVX2 is a precondition of this function.
let mask = unsafe {
let x = _mm256_loadu_si256(a.as_ptr().add(i) as *const __m256i);
let y = _mm256_loadu_si256(b.as_ptr().add(i) as *const __m256i);
_mm256_movemask_epi8(_mm256_cmpeq_epi8(x, y)) as u32
};
if mask != u32::MAX {
return i + (!mask).trailing_zeros() as usize;
}
i += V;
}
i + super::portable::common_prefix_len(&a[i..n], &b[i..n])
}
/// # Safety
/// The caller must have established that AVX2 is available.
#[target_feature(enable = "avx2")]
pub unsafe fn common_suffix_len(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let (a, b) = (&a[a.len() - n..], &b[b.len() - n..]);
let mut i = 0;
while i + V <= n {
let at = n - i - V;
// SAFETY: `at + V == n - i <= n`, and both slices were trimmed to
// their trailing `n` bytes above, so both reads are in bounds;
// `loadu` needs no alignment; AVX2 is a precondition.
let mask = unsafe {
let x = _mm256_loadu_si256(a.as_ptr().add(at) as *const __m256i);
let y = _mm256_loadu_si256(b.as_ptr().add(at) as *const __m256i);
_mm256_movemask_epi8(_mm256_cmpeq_epi8(x, y)) as u32
};
if mask != u32::MAX {
return i + (!mask).leading_zeros() as usize;
}
i += V;
}
i + super::portable::common_suffix_len(&a[..n - i], &b[..n - i])
}
}