scanline-simd 0.1.0-alpha.0

Vectorised scan predicates for Scanline — AVX-512, AVX2, NEON, and a portable fallback behind one safe API.
Documentation
//! Vectorised scan predicates.
//!
//! Every public entry point here is safe and dispatches at runtime to the widest
//! instruction set the host actually supports, falling back to a portable
//! implementation. The `unsafe` surface is confined to the per-backend modules.
//!
//! # Correctness invariant
//!
//! Each backend must return exactly what the scalar oracle returns, for every
//! input length — including lengths that are not a multiple of the vector width.
//! Handling that tail is the single easiest thing to get wrong here: an
//! implementation built only from `chunks_exact(N)` silently undercounts, since
//! `chunks_exact` discards the remainder. Every backend below therefore pairs its
//! vector loop with an explicit scalar pass over `chunks_exact(..).remainder()`.

#[cfg(target_arch = "x86_64")]
pub mod x86;

pub mod portable;

/// Which backend a scan actually executed on.
///
/// Exposed so benchmarks and the CLI can report the path taken rather than
/// assuming it — on a Zen 4 part the AVX-512 and AVX2 paths perform almost
/// identically, and knowing which ran is the difference between a meaningful and
/// a misleading measurement.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Backend {
    /// AVX-512F: 8 x i64 per vector.
    Avx512,
    /// AVX2: 4 x i64 per vector.
    Avx2,
    /// Scalar / autovectorised fallback.
    Portable,
}

impl Backend {
    /// Elements of 64-bit width processed per vector operation.
    #[must_use]
    pub const fn lanes_64bit(self) -> usize {
        match self {
            Self::Avx512 => 8,
            Self::Avx2 => 4,
            Self::Portable => 1,
        }
    }

    /// A short, stable identifier for use in benchmark result records.
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::Avx512 => "avx512",
            Self::Avx2 => "avx2",
            Self::Portable => "portable",
        }
    }
}

/// The widest backend supported by the host CPU.
#[must_use]
pub fn detect_backend() -> Backend {
    #[cfg(target_arch = "x86_64")]
    {
        if std::arch::is_x86_feature_detected!("avx512f") {
            return Backend::Avx512;
        }
        if std::arch::is_x86_feature_detected!("avx2") {
            return Backend::Avx2;
        }
    }
    Backend::Portable
}

/// Counts elements of `data` strictly greater than `target`.
///
/// Dispatches to the widest available backend. For an explicit backend — which
/// is how the test suite exercises every path on one machine — use
/// [`scan_greater_than_i64_with`].
#[must_use]
pub fn scan_greater_than_i64(data: &[i64], target: i64) -> usize {
    scan_greater_than_i64_with(data, target, detect_backend())
}

/// Counts elements of `data` strictly greater than `target` using a specific
/// backend.
///
/// Requesting a backend the host does not support falls back to
/// [`Backend::Portable`] rather than executing an illegal instruction, so this is
/// safe to call unconditionally.
#[must_use]
pub fn scan_greater_than_i64_with(data: &[i64], target: i64, backend: Backend) -> usize {
    match backend {
        #[cfg(target_arch = "x86_64")]
        Backend::Avx512 if std::arch::is_x86_feature_detected!("avx512f") => {
            // SAFETY: guarded by the `avx512f` runtime feature check in this
            // match arm's guard, which is the precondition of the callee.
            unsafe { x86::scan_gt_i64_avx512(data, target) }
        }
        #[cfg(target_arch = "x86_64")]
        Backend::Avx2 if std::arch::is_x86_feature_detected!("avx2") => {
            // SAFETY: guarded by the `avx2` runtime feature check in this match
            // arm's guard, which is the precondition of the callee.
            unsafe { x86::scan_gt_i64_avx2(data, target) }
        }
        _ => portable::scan_gt_i64(data, target),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The oracle every backend is checked against.
    fn oracle(data: &[i64], target: i64) -> usize {
        data.iter().filter(|&&x| x > target).count()
    }

    fn all_backends() -> Vec<Backend> {
        let mut v = vec![Backend::Portable];
        #[cfg(target_arch = "x86_64")]
        {
            if std::arch::is_x86_feature_detected!("avx2") {
                v.push(Backend::Avx2);
            }
            if std::arch::is_x86_feature_detected!("avx512f") {
                v.push(Backend::Avx512);
            }
        }
        v
    }

    /// Lengths 0..=257 cover every remainder class for widths 4 and 8, both
    /// sides of a 256-element boundary, and the empty case. This is the test
    /// that catches a missing tail pass.
    #[test]
    fn matches_oracle_across_all_lengths_and_backends() {
        for backend in all_backends() {
            for len in 0..=257_usize {
                let data: Vec<i64> = (0..len).map(|i| (i % 50) as i64).collect();
                let target = 24;
                let expected = oracle(&data, target);
                let got = scan_greater_than_i64_with(&data, target, backend);
                assert_eq!(
                    got, expected,
                    "backend {backend:?} disagreed at len {len}: got {got}, want {expected}",
                );
            }
        }
    }

    #[test]
    fn all_match_and_no_match_boundaries() {
        for backend in all_backends() {
            for len in [0_usize, 1, 7, 8, 9, 63, 64, 65, 257] {
                let data = vec![10_i64; len];

                assert_eq!(
                    scan_greater_than_i64_with(&data, 9, backend),
                    len,
                    "backend {backend:?}: all elements should match at len {len}",
                );
                // Strictly greater, so an equal target matches nothing.
                assert_eq!(
                    scan_greater_than_i64_with(&data, 10, backend),
                    0,
                    "backend {backend:?}: equal target must not match at len {len}",
                );
                assert_eq!(
                    scan_greater_than_i64_with(&data, 11, backend),
                    0,
                    "backend {backend:?}: larger target must not match at len {len}",
                );
            }
        }
    }

    #[test]
    fn handles_extremes_without_overflow() {
        let data = [i64::MIN, -1, 0, 1, i64::MAX];
        for backend in all_backends() {
            for target in [i64::MIN, -1, 0, 1, i64::MAX] {
                assert_eq!(
                    scan_greater_than_i64_with(&data, target, backend),
                    oracle(&data, target),
                    "backend {backend:?} disagreed for target {target}",
                );
            }
        }
    }

    #[test]
    fn backends_agree_with_each_other() {
        // A small LCG rather than a rand dependency — deterministic, and the
        // core crates stay dependency-free.
        let mut state: i64 = 0x2545_F491;
        let data: Vec<i64> = (0..10_000)
            .map(|_| {
                state = state
                    .wrapping_mul(6_364_136_223_846_793_005)
                    .wrapping_add(1_442_695_040_888_963_407);
                state.rem_euclid(1000)
            })
            .collect();
        let reference = portable::scan_gt_i64(&data, 500);
        for backend in all_backends() {
            assert_eq!(
                scan_greater_than_i64_with(&data, 500, backend),
                reference,
                "backend {backend:?} disagreed with the portable reference",
            );
        }
    }
}