Skip to main content

linkcell/
simd.rs

1//! Runtime SIMD path for the mesh fold, the k-nearest scan, and cutoff pairs.
2//!
3//! `LINKCELL_SIMD` forces `scalar`, `avx2`, `avx512`, or `neon`.
4//! An unknown name is ignored. A name this CPU cannot run selects
5//! the scalar path. Unset, the widest usable path is used: AVX-512,
6//! then AVX2 with FMA, then NEON, then scalar.
7//!
8//! AVX-512 is taken only when AVX-512F, AVX-512VL, POPCNT, and FMA are
9//! all present. A CPU with AVX-512F but not VL uses AVX2. AVX2 is taken
10//! only when FMA is present too, so Zen 2/3 and Haswell use it and
11//! Sandy Bridge stays on the scalar path. FMA is a selection gate for
12//! the fold and the scan: those kernels multiply and add separately.
13//! Pair screening may use FMA inside the margin test. No fused
14//! multiply-add reaches a stored value. The floor in the fold is
15//! minimage's `floor_fast`: truncation on every architecture.
16
17use std::cell::Cell;
18use std::sync::OnceLock;
19
20/// Width of the mesh fold, the SoA distance scan, and the pair tile.
21#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22pub(crate) enum Path {
23    /// One point at a time.
24    Scalar,
25    /// Four f64 lanes. Requires AVX2 and FMA.
26    Avx2,
27    /// Eight f64 lanes. Requires AVX-512F, AVX-512VL, POPCNT, and FMA.
28    Avx512,
29    /// Two f64 lanes. Requires NEON.
30    Neon,
31}
32
33impl Path {
34    /// Stable name for logs and [`crate::simd_path`].
35    pub(crate) fn name(self) -> &'static str {
36        match self {
37            Path::Scalar => "scalar",
38            Path::Avx2 => "avx2",
39            Path::Avx512 => "avx512",
40            Path::Neon => "neon",
41        }
42    }
43
44    /// This build contains the kernel and this CPU can run it.
45    pub(crate) fn usable(self) -> bool {
46        match self {
47            Path::Scalar => true,
48            Path::Avx2 => avx2_ready(),
49            Path::Avx512 => avx512_ready(),
50            Path::Neon => neon_ready(),
51        }
52    }
53}
54
55thread_local! {
56    // `const { ... }` is newer than this crate's 1.70 floor.
57    #[allow(clippy::missing_const_for_thread_local)]
58    static FORCE: Cell<Option<Path>> = Cell::new(None);
59}
60
61/// Path for the next fold or scan.
62///
63/// A test override wins, then `LINKCELL_SIMD`, then [`native`].
64pub(crate) fn select() -> Path {
65    if let Some(path) = FORCE.with(|slot| slot.get()) {
66        return if path.usable() { path } else { Path::Scalar };
67    }
68    if let Some(path) = env_path() {
69        return path;
70    }
71    native()
72}
73
74/// Widest path this CPU can run. Ignores `LINKCELL_SIMD`.
75pub(crate) fn native() -> Path {
76    if avx512_ready() {
77        Path::Avx512
78    } else if avx2_ready() {
79        Path::Avx2
80    } else if neon_ready() {
81        Path::Neon
82    } else {
83        Path::Scalar
84    }
85}
86
87fn env_path() -> Option<Path> {
88    static CACHED: OnceLock<Option<Path>> = OnceLock::new();
89    *CACHED.get_or_init(|| {
90        let raw = std::env::var("LINKCELL_SIMD").ok()?;
91        let path = parse(raw.trim())?;
92        Some(if path.usable() { path } else { Path::Scalar })
93    })
94}
95
96pub(crate) fn parse(name: &str) -> Option<Path> {
97    match name {
98        "scalar" | "0" => Some(Path::Scalar),
99        "avx2" | "avx2fma" => Some(Path::Avx2),
100        "avx512" | "avx512f" => Some(Path::Avx512),
101        "neon" => Some(Path::Neon),
102        _ => None,
103    }
104}
105
106fn avx2_ready() -> bool {
107    #[cfg(target_arch = "x86_64")]
108    {
109        std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma")
110    }
111    #[cfg(not(target_arch = "x86_64"))]
112    {
113        false
114    }
115}
116
117fn avx512_ready() -> bool {
118    #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
119    {
120        // Pair kernels enable every one of these. Fold and scan need
121        // only AVX-512F, and they follow this gate so one path is shared.
122        std::is_x86_feature_detected!("avx512f")
123            && std::is_x86_feature_detected!("avx512vl")
124            && std::is_x86_feature_detected!("popcnt")
125            && std::is_x86_feature_detected!("fma")
126    }
127    #[cfg(not(all(target_arch = "x86_64", linkcell_avx512)))]
128    {
129        false
130    }
131}
132
133fn neon_ready() -> bool {
134    // NEON is baseline on aarch64. A runtime check would not change the answer.
135    cfg!(target_feature = "neon")
136}
137
138/// Name of the path the next fold or scan takes: `LINKCELL_SIMD` when it
139/// is set, otherwise the widest path this CPU runs.
140pub fn simd_path() -> &'static str {
141    select().name()
142}
143
144#[cfg(feature = "timing")]
145static SCAN_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
146#[cfg(feature = "timing")]
147static KNN_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
148#[cfg(feature = "timing")]
149static MESH_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
150
151/// `LINKCELL_SCAN_TIME` is set. Read once.
152///
153/// This arms a timer around each source's SoA scan.
154#[cfg(feature = "timing")]
155pub(crate) fn scan_timing_enabled() -> bool {
156    static ON: OnceLock<bool> = OnceLock::new();
157    *ON.get_or_init(|| std::env::var_os("LINKCELL_SCAN_TIME").is_some())
158}
159
160/// `LINKCELL_COARSE_TIME` is set. Read once.
161///
162/// This arms one timer around [`crate::knearest_into`] and one around
163/// the mesh build. It does not time each source.
164#[cfg(feature = "timing")]
165pub(crate) fn coarse_timing_enabled() -> bool {
166    static ON: OnceLock<bool> = OnceLock::new();
167    *ON.get_or_init(|| std::env::var_os("LINKCELL_COARSE_TIME").is_some())
168}
169
170#[cfg(feature = "timing")]
171pub(crate) fn add_scan_ns(ns: u128) {
172    SCAN_NS.fetch_add(ns as u64, std::sync::atomic::Ordering::Relaxed);
173}
174
175#[cfg(feature = "timing")]
176pub(crate) fn add_knn_ns(ns: u128) {
177    KNN_NS.fetch_add(ns as u64, std::sync::atomic::Ordering::Relaxed);
178}
179
180#[cfg(feature = "timing")]
181pub(crate) fn add_mesh_ns(ns: u128) {
182    MESH_NS.fetch_add(ns as u64, std::sync::atomic::Ordering::Relaxed);
183}
184
185/// Nanoseconds accumulated since process start.
186///
187/// `mesh_ns` is the calling thread's wait for the mesh build inside
188/// [`crate::knearest_into`]. `knn_ns` is that search after the output
189/// buffers are filled, on the calling thread. `scan_ns` is the SoA
190/// distance scan. With one thread the scan total is a slice of the
191/// search total. With more threads the scan total sums every worker,
192/// so it can exceed the wall time.
193///
194/// All three stay zero unless the matching variable is set before the
195/// first search. `LINKCELL_SCAN_TIME` counts the scan.
196/// `LINKCELL_COARSE_TIME` counts the search and the mesh build.
197#[cfg(feature = "timing")]
198#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
199pub struct SimdTiming {
200    /// Mesh build inside [`crate::knearest_into`], on the calling thread.
201    pub mesh_ns: u64,
202    /// SoA distance scan. Sums every worker when the search is parallel.
203    pub scan_ns: u64,
204    /// [`crate::knearest_into`] after the output buffers are filled.
205    pub knn_ns: u64,
206}
207
208/// Current [`SimdTiming`] counters.
209#[cfg(feature = "timing")]
210pub fn simd_timing() -> SimdTiming {
211    SimdTiming {
212        mesh_ns: MESH_NS.load(std::sync::atomic::Ordering::Relaxed),
213        scan_ns: SCAN_NS.load(std::sync::atomic::Ordering::Relaxed),
214        knn_ns: KNN_NS.load(std::sync::atomic::Ordering::Relaxed),
215    }
216}
217
218/// Restores the previous test override, including on panic.
219#[cfg(test)]
220pub(crate) struct ForceGuard {
221    prev: Option<Path>,
222}
223
224/// Force [`select`] on this thread until the guard drops.
225///
226/// Rayon jobs must capture [`select`] on the calling thread. Workers
227/// do not see this thread's override.
228#[cfg(test)]
229pub(crate) fn force(path: Path) -> ForceGuard {
230    let prev = FORCE.with(|slot| slot.replace(Some(path)));
231    ForceGuard { prev }
232}
233
234#[cfg(test)]
235impl Drop for ForceGuard {
236    fn drop(&mut self) {
237        let prev = self.prev;
238        FORCE.with(|slot| slot.set(prev));
239    }
240}
241
242/// Scalar plus every wide path this CPU can run.
243#[cfg(test)]
244pub(crate) fn paths_to_compare() -> Vec<Path> {
245    let mut out = vec![Path::Scalar];
246    for path in [Path::Avx2, Path::Avx512, Path::Neon] {
247        if path.usable() {
248            out.push(path);
249        }
250    }
251    out
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257
258    #[test]
259    fn parse_names() {
260        assert_eq!(parse("scalar"), Some(Path::Scalar));
261        assert_eq!(parse("0"), Some(Path::Scalar));
262        assert_eq!(parse("avx2"), Some(Path::Avx2));
263        assert_eq!(parse("avx2fma"), Some(Path::Avx2));
264        assert_eq!(parse("avx512"), Some(Path::Avx512));
265        assert_eq!(parse("avx512f"), Some(Path::Avx512));
266        assert_eq!(parse("neon"), Some(Path::Neon));
267        assert_eq!(parse("avx"), None);
268        assert_eq!(parse(""), None);
269    }
270
271    #[test]
272    fn native_path_is_usable() {
273        let path = native();
274        assert!(path.usable());
275        assert_eq!(path.name(), simd_path());
276    }
277
278    #[cfg(feature = "timing")]
279    #[test]
280    fn simd_timing_names_mesh_scan_and_search() {
281        assert!(std::env::var_os("LINKCELL_SCAN_TIME").is_none());
282        assert!(std::env::var_os("LINKCELL_COARSE_TIME").is_none());
283        let t = simd_timing();
284        assert_eq!(
285            t,
286            SimdTiming {
287                mesh_ns: 0,
288                scan_ns: 0,
289                knn_ns: 0,
290            }
291        );
292    }
293}