Skip to main content

scanline_simd/
lib.rs

1//! Vectorised scan predicates.
2//!
3//! Every public entry point here is safe and dispatches at runtime to the widest
4//! instruction set the host actually supports, falling back to a portable
5//! implementation. The `unsafe` surface is confined to the per-backend modules.
6//!
7//! # Correctness invariant
8//!
9//! Each backend must return exactly what the scalar oracle returns, for every
10//! input length — including lengths that are not a multiple of the vector width.
11//! Handling that tail is the single easiest thing to get wrong here: an
12//! implementation built only from `chunks_exact(N)` silently undercounts, since
13//! `chunks_exact` discards the remainder. Every backend below therefore pairs its
14//! vector loop with an explicit scalar pass over `chunks_exact(..).remainder()`.
15
16#[cfg(target_arch = "x86_64")]
17pub mod x86;
18
19pub mod portable;
20
21/// Which backend a scan actually executed on.
22///
23/// Exposed so benchmarks and the CLI can report the path taken rather than
24/// assuming it — on a Zen 4 part the AVX-512 and AVX2 paths perform almost
25/// identically, and knowing which ran is the difference between a meaningful and
26/// a misleading measurement.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
28pub enum Backend {
29    /// AVX-512F: 8 x i64 per vector.
30    Avx512,
31    /// AVX2: 4 x i64 per vector.
32    Avx2,
33    /// Scalar / autovectorised fallback.
34    Portable,
35}
36
37impl Backend {
38    /// Elements of 64-bit width processed per vector operation.
39    #[must_use]
40    pub const fn lanes_64bit(self) -> usize {
41        match self {
42            Self::Avx512 => 8,
43            Self::Avx2 => 4,
44            Self::Portable => 1,
45        }
46    }
47
48    /// A short, stable identifier for use in benchmark result records.
49    #[must_use]
50    pub const fn as_str(self) -> &'static str {
51        match self {
52            Self::Avx512 => "avx512",
53            Self::Avx2 => "avx2",
54            Self::Portable => "portable",
55        }
56    }
57}
58
59/// The widest backend supported by the host CPU.
60#[must_use]
61pub fn detect_backend() -> Backend {
62    #[cfg(target_arch = "x86_64")]
63    {
64        if std::arch::is_x86_feature_detected!("avx512f") {
65            return Backend::Avx512;
66        }
67        if std::arch::is_x86_feature_detected!("avx2") {
68            return Backend::Avx2;
69        }
70    }
71    Backend::Portable
72}
73
74/// Counts elements of `data` strictly greater than `target`.
75///
76/// Dispatches to the widest available backend. For an explicit backend — which
77/// is how the test suite exercises every path on one machine — use
78/// [`scan_greater_than_i64_with`].
79#[must_use]
80pub fn scan_greater_than_i64(data: &[i64], target: i64) -> usize {
81    scan_greater_than_i64_with(data, target, detect_backend())
82}
83
84/// Counts elements of `data` strictly greater than `target` using a specific
85/// backend.
86///
87/// Requesting a backend the host does not support falls back to
88/// [`Backend::Portable`] rather than executing an illegal instruction, so this is
89/// safe to call unconditionally.
90#[must_use]
91pub fn scan_greater_than_i64_with(data: &[i64], target: i64, backend: Backend) -> usize {
92    match backend {
93        #[cfg(target_arch = "x86_64")]
94        Backend::Avx512 if std::arch::is_x86_feature_detected!("avx512f") => {
95            // SAFETY: guarded by the `avx512f` runtime feature check in this
96            // match arm's guard, which is the precondition of the callee.
97            unsafe { x86::scan_gt_i64_avx512(data, target) }
98        }
99        #[cfg(target_arch = "x86_64")]
100        Backend::Avx2 if std::arch::is_x86_feature_detected!("avx2") => {
101            // SAFETY: guarded by the `avx2` runtime feature check in this match
102            // arm's guard, which is the precondition of the callee.
103            unsafe { x86::scan_gt_i64_avx2(data, target) }
104        }
105        _ => portable::scan_gt_i64(data, target),
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112
113    /// The oracle every backend is checked against.
114    fn oracle(data: &[i64], target: i64) -> usize {
115        data.iter().filter(|&&x| x > target).count()
116    }
117
118    fn all_backends() -> Vec<Backend> {
119        let mut v = vec![Backend::Portable];
120        #[cfg(target_arch = "x86_64")]
121        {
122            if std::arch::is_x86_feature_detected!("avx2") {
123                v.push(Backend::Avx2);
124            }
125            if std::arch::is_x86_feature_detected!("avx512f") {
126                v.push(Backend::Avx512);
127            }
128        }
129        v
130    }
131
132    /// Lengths 0..=257 cover every remainder class for widths 4 and 8, both
133    /// sides of a 256-element boundary, and the empty case. This is the test
134    /// that catches a missing tail pass.
135    #[test]
136    fn matches_oracle_across_all_lengths_and_backends() {
137        for backend in all_backends() {
138            for len in 0..=257_usize {
139                let data: Vec<i64> = (0..len).map(|i| (i % 50) as i64).collect();
140                let target = 24;
141                let expected = oracle(&data, target);
142                let got = scan_greater_than_i64_with(&data, target, backend);
143                assert_eq!(
144                    got, expected,
145                    "backend {backend:?} disagreed at len {len}: got {got}, want {expected}",
146                );
147            }
148        }
149    }
150
151    #[test]
152    fn all_match_and_no_match_boundaries() {
153        for backend in all_backends() {
154            for len in [0_usize, 1, 7, 8, 9, 63, 64, 65, 257] {
155                let data = vec![10_i64; len];
156
157                assert_eq!(
158                    scan_greater_than_i64_with(&data, 9, backend),
159                    len,
160                    "backend {backend:?}: all elements should match at len {len}",
161                );
162                // Strictly greater, so an equal target matches nothing.
163                assert_eq!(
164                    scan_greater_than_i64_with(&data, 10, backend),
165                    0,
166                    "backend {backend:?}: equal target must not match at len {len}",
167                );
168                assert_eq!(
169                    scan_greater_than_i64_with(&data, 11, backend),
170                    0,
171                    "backend {backend:?}: larger target must not match at len {len}",
172                );
173            }
174        }
175    }
176
177    #[test]
178    fn handles_extremes_without_overflow() {
179        let data = [i64::MIN, -1, 0, 1, i64::MAX];
180        for backend in all_backends() {
181            for target in [i64::MIN, -1, 0, 1, i64::MAX] {
182                assert_eq!(
183                    scan_greater_than_i64_with(&data, target, backend),
184                    oracle(&data, target),
185                    "backend {backend:?} disagreed for target {target}",
186                );
187            }
188        }
189    }
190
191    #[test]
192    fn backends_agree_with_each_other() {
193        // A small LCG rather than a rand dependency — deterministic, and the
194        // core crates stay dependency-free.
195        let mut state: i64 = 0x2545_F491;
196        let data: Vec<i64> = (0..10_000)
197            .map(|_| {
198                state = state
199                    .wrapping_mul(6_364_136_223_846_793_005)
200                    .wrapping_add(1_442_695_040_888_963_407);
201                state.rem_euclid(1000)
202            })
203            .collect();
204        let reference = portable::scan_gt_i64(&data, 500);
205        for backend in all_backends() {
206            assert_eq!(
207                scan_greater_than_i64_with(&data, 500, backend),
208                reference,
209                "backend {backend:?} disagreed with the portable reference",
210            );
211        }
212    }
213}