Skip to main content

linkcell/
knearest.rs

1//! Linked-cell k-nearest search (Allen and Tildesley).
2//!
3//! Fold into the primary cell, bin on the fractional mesh in cell-major
4//! order, then grow the index box until the k-th neighbour lies inside
5//! the perpendicular distance to the unvisited frontier. An orthorhombic
6//! box is walked as stored. A restricted triclinic box is tilt-reduced
7//! first. A general orientation is Minkowski-reduced. Distances are
8//! [`crate::Cell::dist2_shifted`]
9//! plus [`crate::Cell::lattice_shift`]. The walk keys on the integer
10//! stencil, not a unique-cell stamp: occupants of one bin can need
11//! different lattice images of the same source.
12//!
13//! [`knearest`] returns one [`Neighbors`] row per point. [`knearest_into`]
14//! writes packed `n * k` indices (`-1` unused). [`knearest_into_d2`]
15//! also writes the matching squared distances (`NaN` unused). With the
16//! `parallel` feature (the default) an unmasked query of at least 8192
17//! points runs on one linkcell thread team on Linux: bin, count, scan, fill,
18//! and select, each thread with its own histogram and scratch. Masked queries,
19//! smaller queries, and builds without that region still walk under rayon.
20//! `--no-default-features` serializes the walk. The per-source `KHeap` stays
21//! on the stack for `k <= 16`.
22
23use crate::bins::{self, axis_gap, for_new_layer, slab_dist2, Mesh};
24use crate::cell::Cell;
25use crate::team::Stage;
26use crate::Error;
27use std::sync::atomic::{AtomicBool, AtomicPtr, AtomicU32, Ordering};
28use std::sync::Mutex;
29
30fn pair_dist2(simbox: &Cell, p: [f64; 3], q: [f64; 3]) -> f64 {
31    simbox.dist2_euclidean(p, q)
32}
33
34/// Orthorhombic MIC for every candidate, via minimage's Highway kernel.
35fn ortho_highway_dist2(
36    p: [f64; 3],
37    others: &[usize],
38    xyz: &[[f64; 3]],
39    widths: [f64; 3],
40) -> Result<Vec<f64>, Error> {
41    let n = others.len();
42    let mut dx = Vec::with_capacity(n);
43    let mut dy = Vec::with_capacity(n);
44    let mut dz = Vec::with_capacity(n);
45    for &j in others {
46        let q = xyz[j];
47        dx.push(q[0] - p[0]);
48        dy.push(q[1] - p[1]);
49        dz.push(q[2] - p[2]);
50    }
51    let mut out = vec![0.0; n];
52    crate::dist2_ortho_diffs(&dx, &dy, &dz, widths[0], widths[1], widths[2], &mut out)?;
53    Ok(out)
54}
55
56fn box_diameter(cell: &Cell) -> f64 {
57    let a = cell.a();
58    let b = cell.b();
59    let c = cell.c();
60    let mut best = 0.0_f64;
61    for &sa in &[-1.0, 1.0] {
62        for &sb in &[-1.0, 1.0] {
63            for &sc in &[-1.0, 1.0] {
64                let x = sa * a[0] + sb * b[0] + sc * c[0];
65                let y = sa * a[1] + sb * b[1] + sc * c[1];
66                let z = sa * a[2] + sb * b[2] + sc * c[2];
67                best = best.max(x * x + y * y + z * z);
68            }
69        }
70    }
71    best.sqrt()
72}
73
74/// Bounded max-heap of `(dist2, index)`. `k <= 16` stays in
75/// `[f64; 16]` / `[usize; 16]` so the pair loop does not allocate;
76/// larger `k` uses `extra_*` vectors.
77#[derive(Clone)]
78struct KHeap {
79    d2: [f64; 16],
80    idx: [usize; 16],
81    extra_d2: Vec<f64>,
82    extra_idx: Vec<usize>,
83    n: usize,
84    k: usize,
85    /// Slot of the lexicographic maximum `(dist2, index)`.
86    worst_at: usize,
87}
88
89impl KHeap {
90    fn new(k: usize) -> Self {
91        let mut extra_d2 = Vec::new();
92        let mut extra_idx = Vec::new();
93        if k > 16 {
94            extra_d2.resize(k, 0.0);
95            extra_idx.resize(k, 0);
96        }
97        Self {
98            d2: [0.0; 16],
99            idx: [0; 16],
100            extra_d2,
101            extra_idx,
102            n: 0,
103            k,
104            worst_at: 0,
105        }
106    }
107
108    /// Empty again, for the next source.
109    fn clear(&mut self) {
110        self.n = 0;
111        self.worst_at = 0;
112    }
113
114    fn d2_at(&self, t: usize) -> f64 {
115        if self.k <= 16 {
116            self.d2[t]
117        } else {
118            self.extra_d2[t]
119        }
120    }
121
122    fn set(&mut self, t: usize, d2: f64, j: usize) {
123        if self.k <= 16 {
124            self.d2[t] = d2;
125            self.idx[t] = j;
126        } else {
127            self.extra_d2[t] = d2;
128            self.extra_idx[t] = j;
129        }
130    }
131
132    fn idx_at(&self, t: usize) -> usize {
133        if self.k <= 16 {
134            self.idx[t]
135        } else {
136            self.extra_idx[t]
137        }
138    }
139
140    fn worse_than(&self, d2: f64, j: usize, other: usize) -> bool {
141        let od = self.d2_at(other);
142        let oj = self.idx_at(other);
143        d2 > od || (d2 == od && j > oj)
144    }
145
146    fn recompute_worst(&mut self) {
147        let mut w = 0;
148        for t in 1..self.n {
149            if self.worse_than(self.d2_at(t), self.idx_at(t), w) {
150                w = t;
151            }
152        }
153        self.worst_at = w;
154    }
155
156    /// Insert the nearest image of `j`. Equal distances keep the smaller index.
157    fn push(&mut self, d2: f64, j: usize) {
158        if self.n == self.k {
159            let wd = self.d2_at(self.worst_at);
160            let wj = self.idx_at(self.worst_at);
161            // A candidate that does not beat the worst cannot improve any
162            // stored image either: those distances are at most the worst.
163            if d2 > wd || (d2 == wd && j >= wj) {
164                return;
165            }
166        }
167        for t in 0..self.n {
168            if self.idx_at(t) == j {
169                if d2 < self.d2_at(t) {
170                    self.set(t, d2, j);
171                    if t == self.worst_at {
172                        self.recompute_worst();
173                    }
174                }
175                return;
176            }
177        }
178        if self.n < self.k {
179            let slot = self.n;
180            self.set(slot, d2, j);
181            if slot == 0 || self.worse_than(d2, j, self.worst_at) {
182                self.worst_at = slot;
183            }
184            self.n += 1;
185            return;
186        }
187        self.set(self.worst_at, d2, j);
188        self.recompute_worst();
189    }
190
191    fn full(&self) -> bool {
192        self.n >= self.k
193    }
194
195    fn worst(&self) -> f64 {
196        self.d2_at(self.worst_at)
197    }
198
199    /// Write nearest-first into caller slots. Unused tail stays as the caller left it.
200    fn write_sorted(&self, nn: &mut [i32], mut d2: Option<&mut [f64]>) {
201        if self.k <= 16 {
202            let n = self.n;
203            let mut order = [0u8; 16];
204            for (t, slot) in order.iter_mut().enumerate().take(n) {
205                *slot = t as u8;
206            }
207            // Insertion sort: a handful of entries.
208            let before = |a: u8, b: u8| {
209                let (a, b) = (a as usize, b as usize);
210                self.d2[a]
211                    .total_cmp(&self.d2[b])
212                    .then(self.idx[a].cmp(&self.idx[b]))
213                    .is_lt()
214            };
215            for t in 1..n {
216                let x = order[t];
217                let mut u = t;
218                while u > 0 && before(x, order[u - 1]) {
219                    order[u] = order[u - 1];
220                    u -= 1;
221                }
222                order[u] = x;
223            }
224            for (t, &slot) in order[..n].iter().enumerate() {
225                let s = slot as usize;
226                nn[t] = self.idx[s] as i32;
227                if let Some(buf) = d2.as_mut() {
228                    buf[t] = self.d2[s];
229                }
230            }
231        } else {
232            let mut order: Vec<usize> = (0..self.n).collect();
233            order.sort_by(|&a, &b| {
234                self.extra_d2[a]
235                    .total_cmp(&self.extra_d2[b])
236                    .then(self.extra_idx[a].cmp(&self.extra_idx[b]))
237            });
238            for (t, &s) in order.iter().enumerate() {
239                nn[t] = self.extra_idx[s] as i32;
240                if let Some(buf) = d2.as_mut() {
241                    buf[t] = self.extra_d2[s];
242                }
243            }
244        }
245    }
246}
247
248/// One source's k nearest neighbours, nearest first.
249///
250/// Empty `indices` / `dist2` when the point is masked or isolated.
251/// Length is `min(k, n_active - 1)` for an active source.
252#[derive(Clone, Debug, Default, PartialEq)]
253pub struct Neighbors {
254    /// Candidate indices into the input point list.
255    pub indices: Vec<usize>,
256    /// Squared minimum-image distances, parallel to [`Self::indices`].
257    pub dist2: Vec<f64>,
258}
259
260/// Write k-nearest indices, nearest first, into caller storage.
261///
262/// `out` has length `n * k` ([`Error::BufferSize`] otherwise). Unused
263/// slots are `-1`. Neighbours of source `i` occupy `out[i * k ..]`.
264/// `mask` is `None` or length `n` ([`Error::MaskLen`] otherwise).
265///
266/// ```
267/// use linkcell::{knearest_into, Cell};
268///
269/// # fn main() -> Result<(), linkcell::Error> {
270/// let sim = Cell::ortho(10.0, 10.0, 10.0)?;
271/// let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
272/// let mut out = [0; 4];
273/// knearest_into(&xyz, &sim, 2, None, None, &mut out)?;
274/// assert_eq!(out, [1, -1, 0, -1]);
275/// # Ok(())
276/// # }
277/// ```
278pub fn knearest_into(
279    xyz: &[[f64; 3]],
280    simbox: &Cell,
281    k: usize,
282    mask: Option<&[bool]>,
283    cell_hint: Option<f64>,
284    out: &mut [i32],
285) -> Result<(), Error> {
286    let n = xyz.len();
287    if n.checked_mul(k) != Some(out.len()) {
288        return Err(Error::BufferSize);
289    }
290    knearest_into_d2(xyz, simbox, k, mask, cell_hint, out, None)
291}
292
293/// Write k-nearest indices and squared distances, nearest first.
294///
295/// `out_nn` has length `n * k`. Unused index slots are `-1`.
296/// `out_d2`, when `Some`, has the same length; unused slots are `NaN`.
297pub fn knearest_into_d2(
298    xyz: &[[f64; 3]],
299    simbox: &Cell,
300    k: usize,
301    mask: Option<&[bool]>,
302    cell_hint: Option<f64>,
303    out_nn: &mut [i32],
304    out_d2: Option<&mut [f64]>,
305) -> Result<(), Error> {
306    write_one(xyz, simbox, k, mask, cell_hint, out_nn, out_d2)
307}
308
309/// Frame-major batch: `xyz` is `n_frames * n` points, `out_*` are
310/// `n_frames * n * k`. One shared cell. `mask` is length `n` or `None`.
311#[allow(clippy::too_many_arguments)]
312pub fn knearest_into_many(
313    xyz: &[[f64; 3]],
314    n: usize,
315    n_frames: usize,
316    simbox: &Cell,
317    k: usize,
318    mask: Option<&[bool]>,
319    cell_hint: Option<f64>,
320    out_nn: &mut [i32],
321    mut out_d2: Option<&mut [f64]>,
322) -> Result<(), Error> {
323    if n_frames == 0 {
324        return Err(Error::Empty);
325    }
326    let Some(n_pts) = n.checked_mul(n_frames) else {
327        return Err(Error::Overflow);
328    };
329    if xyz.len() != n_pts {
330        return Err(Error::BufferSize);
331    }
332    let Some(need) = n_pts.checked_mul(k) else {
333        return Err(Error::Overflow);
334    };
335    if out_nn.len() != need {
336        return Err(Error::BufferSize);
337    }
338    if let Some(d2) = out_d2.as_ref() {
339        if d2.len() != need {
340            return Err(Error::BufferSize);
341        }
342    }
343    for f in 0..n_frames {
344        let lo = f * n;
345        let hi = lo + n;
346        let nn_lo = f * n * k;
347        let nn_hi = nn_lo + n * k;
348        let frame_d2 = out_d2.as_mut().map(|d| &mut d[nn_lo..nn_hi]);
349        write_one(
350            &xyz[lo..hi],
351            simbox,
352            k,
353            mask,
354            cell_hint,
355            &mut out_nn[nn_lo..nn_hi],
356            frame_d2,
357        )?;
358    }
359    Ok(())
360}
361
362fn write_one(
363    xyz: &[[f64; 3]],
364    simbox: &Cell,
365    k: usize,
366    mask: Option<&[bool]>,
367    cell_hint: Option<f64>,
368    out_nn: &mut [i32],
369    mut out_d2: Option<&mut [f64]>,
370) -> Result<(), Error> {
371    let n = xyz.len();
372    if n.checked_mul(k) != Some(out_nn.len()) {
373        return Err(Error::BufferSize);
374    }
375    if let Some(d2) = out_d2.as_ref() {
376        if d2.len() != out_nn.len() {
377            return Err(Error::BufferSize);
378        }
379    }
380    #[cfg(feature = "timing")]
381    let started = std::time::Instant::now();
382    let found = execute(
383        xyz,
384        simbox,
385        k,
386        mask,
387        cell_hint,
388        out_nn,
389        out_d2.as_deref_mut(),
390        None,
391        &[],
392    );
393    #[cfg(feature = "timing")]
394    if crate::simd::coarse_timing_enabled() {
395        crate::simd::add_knn_ns(started.elapsed().as_nanos());
396    }
397    if found.is_err() {
398        out_nn.fill(-1);
399        if let Some(d2) = out_d2.as_mut() {
400            d2.fill(f64::NAN);
401        }
402    }
403    found
404}
405
406/// A pointer the chunks of one region share; each chunk writes slots no
407/// other chunk of its stage writes.
408#[derive(Clone, Copy)]
409struct Shared<T>(*mut T);
410unsafe impl<T> Send for Shared<T> {}
411unsafe impl<T> Sync for Shared<T> {}
412
413impl<T> Shared<T> {
414    fn get(self) -> *mut T {
415        self.0
416    }
417}
418
419/// Rows of the graph stages per chunk.
420const GRAPH_ROWS: usize = 2048;
421
422/// Buffers of [`knearest_graph`], kept for the next call.
423#[derive(Default)]
424struct GraphBufs {
425    nom: Vec<i32>,
426    accepted: Vec<u8>,
427    lo: Vec<AtomicU32>,
428    hi: Vec<AtomicU32>,
429    left: Vec<AtomicU32>,
430    start: Vec<u32>,
431}
432
433static GRAPH_POOL: Mutex<Option<GraphBufs>> = Mutex::new(None);
434
435/// `true` when row `j` of the packed nominations lists `i`.
436#[inline(always)]
437fn lists(nom: &[i32], k: usize, j: usize, i: i32) -> bool {
438    nom[j * k..(j + 1) * k].contains(&i)
439}
440
441/// The k-nearest graph as CSR, built in the search's region.
442///
443/// Row `i` of the nominations is its `k` nearest, nearest first. With
444/// `mutual`, row `i` holds every `j` that row `i` lists and that lists
445/// `i`: the lower indices ascending, then the higher ones nearest first.
446/// Otherwise an edge comes from the nomination slot `s = i * k + t` of
447/// the lower index when both rows list each other, and from the only
448/// slot that names it when one does; row `i` holds its edges in slot
449/// order: the edges from lower rows ascending, then its own nearest
450/// first, then the edges from higher rows ascending.
451///
452/// `offsets` has `n + 1` entries. `alloc(total)` is called once, from
453/// any worker, and returns `total` writable ints for the columns, or
454/// null ([`Error::BufferSize`]).
455#[allow(clippy::too_many_arguments)]
456pub(crate) fn knearest_graph(
457    xyz: &[[f64; 3]],
458    simbox: &Cell,
459    k: usize,
460    mask: Option<&[bool]>,
461    cell_hint: Option<f64>,
462    mutual: bool,
463    offsets: &mut [i32],
464    alloc: &(dyn Fn(usize) -> *mut i32 + Sync),
465) -> Result<(), Error> {
466    let n = xyz.len();
467    if offsets.len() != n + 1 {
468        return Err(Error::BufferSize);
469    }
470    let Some(nk) = n.checked_mul(k) else {
471        return Err(Error::Overflow);
472    };
473    if n > i32::MAX as usize {
474        return Err(Error::Overflow);
475    }
476    let mut bufs = GRAPH_POOL
477        .lock()
478        .unwrap_or_else(|err| err.into_inner())
479        .take()
480        .unwrap_or_default();
481    bufs.nom.resize(nk, -1);
482    bufs.accepted.resize(nk, 0);
483    bufs.start.resize(n, 0);
484    for v in [&mut bufs.lo, &mut bufs.hi, &mut bufs.left] {
485        v.truncate(n);
486        v.resize_with(n, || AtomicU32::new(0));
487    }
488    let failed = AtomicBool::new(false);
489    let overflow = AtomicBool::new(false);
490    let cols = AtomicPtr::new(std::ptr::null_mut::<i32>());
491    let result = {
492        let GraphBufs {
493            nom,
494            accepted,
495            lo,
496            hi,
497            left,
498            start,
499        } = &mut bufs;
500        let nom_p = Shared(nom.as_mut_ptr());
501        let acc_p = Shared(accepted.as_mut_ptr());
502        let start_p = Shared(start.as_mut_ptr());
503        let off_p = Shared(offsets.as_mut_ptr());
504        let (lo, hi, left) = (&lo[..], &hi[..], &left[..]);
505        // SAFETY (every stage below): the scan has written every row of
506        // `nom` before the first graph stage starts, and chunk `c` owns
507        // rows `c * GRAPH_ROWS ..` of `accepted`, `start`, and `offsets`.
508        let nom_ro = move || unsafe { std::slice::from_raw_parts(nom_p.get(), nk) };
509        let rows = |c: usize| c * GRAPH_ROWS..((c + 1) * GRAPH_ROWS).min(n);
510        let chunks = (n + GRAPH_ROWS - 1) / GRAPH_ROWS;
511        let prep = |r: std::ops::Range<usize>| {
512            for i in r {
513                lo[i].store(0, Ordering::Relaxed);
514                hi[i].store(0, Ordering::Relaxed);
515            }
516        };
517        let degree = |_: &mut Scratch, c: usize| {
518            let nom = nom_ro();
519            for i in rows(c) {
520                let row = &nom[i * k..(i + 1) * k];
521                let mut own = 0u32;
522                for (t, &j) in row.iter().enumerate() {
523                    let take = j >= 0
524                        && (j as usize) < n
525                        && j as usize != i
526                        && if mutual {
527                            lists(nom, k, j as usize, i as i32)
528                        } else {
529                            (i as i32) < j || !lists(nom, k, j as usize, i as i32)
530                        };
531                    if !mutual {
532                        unsafe { acc_p.get().add(i * k + t).write(u8::from(take)) };
533                    }
534                    if !take {
535                        continue;
536                    }
537                    own += 1;
538                    if !mutual {
539                        if (i as i32) < j {
540                            lo[j as usize].fetch_add(1, Ordering::Relaxed);
541                        } else {
542                            hi[j as usize].fetch_add(1, Ordering::Relaxed);
543                        }
544                    }
545                }
546                unsafe { start_p.get().add(i).write(own) };
547            }
548        };
549        let prefix = |_: &mut Scratch, _: usize| {
550            // SAFETY: one chunk; the degree stage has finished.
551            let (off, start) = unsafe {
552                (
553                    std::slice::from_raw_parts_mut(off_p.get(), n + 1),
554                    std::slice::from_raw_parts_mut(start_p.get(), n),
555                )
556            };
557            let mut acc = 0u64;
558            for i in 0..n {
559                off[i] = acc as i32;
560                let own = u64::from(start[i]);
561                if mutual {
562                    acc += own;
563                } else {
564                    let l = lo[i].load(Ordering::Relaxed);
565                    let h = hi[i].load(Ordering::Relaxed);
566                    start[i] = (acc + u64::from(l)) as u32;
567                    left[i].store(l + h, Ordering::Relaxed);
568                    acc += u64::from(l) + own + u64::from(h);
569                }
570                if acc > i32::MAX as u64 {
571                    overflow.store(true, Ordering::Relaxed);
572                    return;
573                }
574            }
575            off[n] = acc as i32;
576            let p = alloc(acc as usize);
577            if p.is_null() && acc > 0 {
578                failed.store(true, Ordering::Relaxed);
579                return;
580            }
581            cols.store(p, Ordering::Relaxed);
582        };
583        let fill = |s: &mut Scratch, c: usize| {
584            let out = cols.load(Ordering::Relaxed);
585            if out.is_null() {
586                return;
587            }
588            let nom = nom_ro();
589            // SAFETY: the prefix stage has finished; `out` holds
590            // `offsets[n]` ints and each write below lands in a slot of
591            // one row that no other write fills.
592            let off = unsafe { std::slice::from_raw_parts(off_p.get(), n + 1) };
593            let start = unsafe { std::slice::from_raw_parts(start_p.get(), n) };
594            let keep = |i: usize, j: i32| {
595                j >= 0 && (j as usize) < n && j as usize != i && lists(nom, k, j as usize, i as i32)
596            };
597            if mutual {
598                for i in rows(c) {
599                    let row = &nom[i * k..(i + 1) * k];
600                    let low = &mut s.rows;
601                    low.clear();
602                    low.extend(
603                        row.iter()
604                            .copied()
605                            .filter(|&j| (j as usize) < i && keep(i, j)),
606                    );
607                    low.sort_unstable();
608                    let mut put = off[i] as usize;
609                    for &j in low.iter() {
610                        unsafe { out.add(put).write(j) };
611                        put += 1;
612                    }
613                    for &j in row {
614                        if j as usize > i && keep(i, j) {
615                            unsafe { out.add(put).write(j) };
616                            put += 1;
617                        }
618                    }
619                }
620                return;
621            }
622            // SAFETY: the degree stage has finished.
623            let acc = unsafe { std::slice::from_raw_parts(acc_p.get(), nk) };
624            let finish = |j: usize| {
625                let own = acc[j * k..(j + 1) * k].iter().filter(|&&a| a != 0).count();
626                let (b, m, e) = (off[j] as usize, start[j] as usize, off[j + 1] as usize);
627                // SAFETY: every edge from another row into row `j` is
628                // written (`left` reached zero), and row `j`'s own edges
629                // lie between these two runs.
630                unsafe {
631                    std::slice::from_raw_parts_mut(out.add(b), m - b).sort_unstable();
632                    std::slice::from_raw_parts_mut(out.add(m + own), e - m - own).sort_unstable();
633                }
634            };
635            for i in rows(c) {
636                let mut put = start[i] as usize;
637                for t in 0..k {
638                    if acc[i * k + t] == 0 {
639                        continue;
640                    }
641                    let j = nom[i * k + t] as usize;
642                    unsafe { out.add(put).write(j as i32) };
643                    put += 1;
644                    let at = if i < j {
645                        off[j] as usize + lo[j].fetch_sub(1, Ordering::Relaxed) as usize - 1
646                    } else {
647                        off[j + 1] as usize - hi[j].fetch_sub(1, Ordering::Relaxed) as usize
648                    };
649                    unsafe { out.add(at).write(i as i32) };
650                    if left[j].fetch_sub(1, Ordering::AcqRel) == 1 {
651                        finish(j);
652                    }
653                }
654            }
655        };
656        let tail = [
657            Stage {
658                chunks,
659                run: &degree,
660            },
661            Stage {
662                chunks: 1,
663                run: &prefix,
664            },
665            Stage { chunks, run: &fill },
666        ];
667        let nn = unsafe { std::slice::from_raw_parts_mut(nom_p.get(), nk) };
668        execute(
669            xyz,
670            simbox,
671            k,
672            mask,
673            cell_hint,
674            nn,
675            None,
676            Some(&prep),
677            &tail,
678        )
679    };
680    *GRAPH_POOL.lock().unwrap_or_else(|err| err.into_inner()) = Some(bufs);
681    result?;
682    if overflow.load(Ordering::Relaxed) {
683        return Err(Error::Overflow);
684    }
685    if failed.load(Ordering::Relaxed) {
686        return Err(Error::BufferSize);
687    }
688    Ok(())
689}
690
691/// The k-nearest graph as CSR `(offsets, columns)`; see the C entry
692/// `lc_knearest_csr` for the row order.
693pub fn knearest_csr(
694    xyz: &[[f64; 3]],
695    simbox: &Cell,
696    k: usize,
697    mask: Option<&[bool]>,
698    cell_hint: Option<f64>,
699    mutual: bool,
700) -> Result<(Vec<i32>, Vec<i32>), Error> {
701    let mut offsets = vec![0i32; xyz.len() + 1];
702    let cols = Mutex::new(Vec::<i32>::new());
703    let alloc = |total: usize| {
704        let mut guard = cols.lock().unwrap_or_else(|err| err.into_inner());
705        guard.resize(total, 0);
706        guard.as_mut_ptr()
707    };
708    knearest_graph(
709        xyz,
710        simbox,
711        k,
712        mask,
713        cell_hint,
714        mutual,
715        &mut offsets,
716        &alloc,
717    )?;
718    let cols = cols.into_inner().unwrap_or_else(|err| err.into_inner());
719    Ok((offsets, cols))
720}
721
722/// k-nearest neighbours of every point (or of the masked subset).
723///
724/// `mask[i] == false` drops point `i` from both sources and candidates.
725/// `mask` is `None` or length `n` ([`Error::MaskLen`] otherwise).
726/// `cell_hint` is the target cell edge; `None` uses 3.0 in the same units
727/// as the box. Each row has `min(k, n_active - 1)` entries.
728///
729/// Fold, bin, then grow a rectangular index box. An orthorhombic cell
730/// is used as stored. A restricted triclinic cell is tilt-reduced
731/// first. A general orientation is Minkowski-reduced. Distances are
732/// [`Cell::dist2_shifted`] plus [`Cell::lattice_shift`]. The walk does
733/// not stamp unique cells: occupants of one bin can need different
734/// images. A full heap stops when its worst distance is at most the
735/// nearest unvisited face.
736///
737/// ```
738/// use linkcell::{knearest, Cell};
739///
740/// # fn main() -> Result<(), linkcell::Error> {
741/// let sim = Cell::ortho(10.0, 10.0, 10.0)?;
742/// let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
743/// let mask = [true, false, true];
744/// let rows = knearest(&xyz, &sim, 1, Some(&mask), None)?;
745/// assert!(rows[1].indices.is_empty());
746/// assert_eq!(rows[0].indices, vec![2]);
747/// assert_eq!(rows[2].indices, vec![0]);
748/// # Ok(())
749/// # }
750/// ```
751pub fn knearest(
752    xyz: &[[f64; 3]],
753    simbox: &Cell,
754    k: usize,
755    mask: Option<&[bool]>,
756    cell_hint: Option<f64>,
757) -> Result<Vec<Neighbors>, Error> {
758    let n = xyz.len();
759    let Some(nk) = n.checked_mul(k) else {
760        return Err(Error::Overflow);
761    };
762    let mut nn = vec![-1i32; nk];
763    let mut d2 = vec![f64::NAN; nk];
764    write_one(xyz, simbox, k, mask, cell_hint, &mut nn, Some(&mut d2))?;
765    let mut out = vec![Neighbors::default(); n];
766    for i in 0..n {
767        let row_nn = &nn[i * k..(i + 1) * k];
768        let row_d2 = &d2[i * k..(i + 1) * k];
769        let m = row_nn.iter().take_while(|j| **j >= 0).count();
770        out[i].indices = row_nn[..m].iter().map(|&j| j as usize).collect();
771        out[i].dist2 = row_d2[..m].to_vec();
772    }
773    Ok(out)
774}
775
776#[derive(Clone, Copy)]
777struct Geom {
778    cols: [[f64; 3]; 3],
779    lengths: [f64; 3],
780    nbin: [i32; 3],
781    widths: [f64; 3],
782}
783
784/// Threads in the last k-nearest team. Zero before the first query.
785static TEAM: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
786
787/// Opt-in placement of the k-nearest team. Off unless a caller asks.
788static PIN_LEAST_LOADED: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
789
790/// Place the k-nearest team workers on the least-loaded CPUs.
791///
792/// Off by default. A query does not read CPU counters or change affinity
793/// until this is set, and it does not consult an environment variable.
794/// Turning it off restores each worker to the mask it had before the pin.
795/// A team of one is the calling thread, pinned for the query only.
796/// Builds without the team query store the flag and leave placement alone.
797pub fn pin_knearest_to_least_loaded(enabled: bool) {
798    PIN_LEAST_LOADED.store(enabled, std::sync::atomic::Ordering::Relaxed);
799}
800
801/// Threads that ran the last k-nearest query.
802///
803/// Zero before the first query. This is the k-nearest team when it ran,
804/// and the rayon pool size otherwise. The team is sized as libgomp sizes
805/// a parallel region the caller opens: `omp_get_max_threads()`, trimmed
806/// by the load average under `OMP_DYNAMIC` and capped by
807/// `OMP_THREAD_LIMIT`. Its stacks follow `OMP_STACKSIZE`. It is resized
808/// on the next query when that size changes. A team of one is the calling
809/// thread, with no worker.
810pub fn knearest_team_threads() -> usize {
811    TEAM.load(std::sync::atomic::Ordering::Relaxed)
812}
813
814/// Join the standing k-nearest team.
815///
816/// The image destructor does this on unload and on process exit. Calling
817/// it directly joins the workers before a `dlclose` and leaves no thread
818/// behind. A later query starts a new team. Safe to call more than once.
819pub fn shutdown_knearest_team() {
820    #[cfg(all(feature = "parallel", linkcell_openmp))]
821    unsafe {
822        lc_knn_shutdown_impl();
823    }
824}
825
826/// C ABI for the same join, so a `dlclose` of this image can stop the team
827/// first. The image destructor calls the implementation directly.
828#[cfg(all(feature = "parallel", linkcell_openmp))]
829#[no_mangle]
830pub extern "C" fn lc_knn_shutdown() {
831    unsafe { lc_knn_shutdown_impl() }
832}
833
834#[cfg(all(feature = "parallel", linkcell_openmp))]
835extern "C" {
836    fn lc_knn_shutdown_impl();
837}
838
839#[cfg(all(test, feature = "parallel", linkcell_openmp))]
840thread_local! {
841    static FORCE_FUSED: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
842    static FORCE_LEGACY: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
843}
844
845#[cfg(all(feature = "parallel", linkcell_openmp))]
846fn force_fused() -> bool {
847    #[cfg(test)]
848    {
849        FORCE_FUSED.with(|cell| cell.get())
850    }
851    #[cfg(not(test))]
852    {
853        false
854    }
855}
856
857#[cfg(all(feature = "parallel", linkcell_openmp))]
858fn force_legacy() -> bool {
859    #[cfg(test)]
860    {
861        FORCE_LEGACY.with(|cell| cell.get())
862    }
863    #[cfg(not(test))]
864    {
865        false
866    }
867}
868
869/// Per-worker buffers of one search region.
870#[derive(Default)]
871pub(crate) struct Scratch {
872    cand: Candidates,
873    heap: Option<KHeap>,
874    /// Row scratch for stages appended to the search.
875    pub(crate) rows: Vec<i32>,
876}
877
878/// Units of the scan (blocks or bins) per chunk: about sixteen chunks a
879/// worker, so a worker the scheduler parks holds a small share.
880fn scan_chunk(units: usize, width: usize) -> usize {
881    (units / (16 * width.max(1))).max(1)
882}
883
884#[allow(clippy::too_many_arguments)]
885fn execute(
886    xyz: &[[f64; 3]],
887    simbox: &Cell,
888    k: usize,
889    mask: Option<&[bool]>,
890    cell_hint: Option<f64>,
891    out_nn: &mut [i32],
892    mut out_d2: Option<&mut [f64]>,
893    prep: Option<&(dyn Fn(std::ops::Range<usize>) + Sync)>,
894    tail: &[Stage<'_, Scratch>],
895) -> Result<(), Error> {
896    if k == 0 {
897        return Err(Error::ZeroK);
898    }
899    if xyz.is_empty() {
900        return Err(Error::Empty);
901    }
902    let n = xyz.len();
903    if let Some(m) = mask {
904        if m.len() != n {
905            return Err(Error::MaskLen);
906        }
907    }
908    let n_active = match mask {
909        Some(m) => m.iter().filter(|&&on| on).count(),
910        None => n,
911    };
912    if n_active <= 1 {
913        out_nn.fill(-1);
914        if let Some(d2) = out_d2.as_mut() {
915            d2.fill(f64::NAN);
916        }
917        if let Some(prep) = prep {
918            prep(0..n);
919        }
920        crate::team::run(1, None, tail);
921        return Ok(());
922    }
923    crate::pop::prepare();
924
925    // Orthorhombic MIC is the per-axis wrap. A LAMMPS / GROMACS
926    // restricted cell is tilt-reduced in place (same Cartesian frame).
927    // Anything else is Minkowski-reduced so the short vectors are the edges.
928    let walk = if simbox.is_ortho() {
929        *simbox
930    } else if simbox.is_restricted() {
931        simbox.reduce_tilts().unwrap_or(*simbox)
932    } else {
933        match minimage::minkowski_reduce(simbox) {
934            Ok(cell) => cell,
935            Err(_) => *simbox,
936        }
937    };
938    let edge = bins::target_edge(&walk, cell_hint, 3.0);
939    let active_owned = mask.map(|m| (0..n).filter(|&i| m[i]).collect::<Vec<_>>());
940    #[cfg(all(feature = "parallel", linkcell_openmp))]
941    if active_owned.is_none()
942        && prep.is_none()
943        && tail.is_empty()
944        && !crate::team::installed()
945        && !crate::on_caller()
946        && !force_legacy()
947        && (xyz.len() >= bins::PARALLEL_MESH || force_fused())
948    {
949        // The region writes only the slots it finds.
950        out_nn.fill(-1);
951        if let Some(d2) = out_d2.as_mut() {
952            d2.fill(f64::NAN);
953        }
954        return fused::run(xyz, &walk, k, edge, out_nn, out_d2);
955    }
956    let nn = RowsOut(out_nn.as_mut_ptr());
957    let dd = out_d2.map(|d| RowsOut(d.as_mut_ptr()));
958    let mode = match (walk.is_ortho(), walk.is_restricted()) {
959        (true, _) => 0u8,
960        (false, true) => 1,
961        (false, false) => 2,
962    };
963    crate::team::with_current(|width, spawn| {
964        if width <= 1 || spawn.is_none() {
965            if let Some(m) = mask {
966                for (i, &on) in m.iter().enumerate() {
967                    if !on {
968                        // SAFETY: row `i` of an `n * k` output.
969                        unsafe {
970                            nn.row(i, k).fill(-1);
971                            if let Some(d) = dd {
972                                d.row(i, k).fill(f64::NAN);
973                            }
974                        }
975                    }
976                }
977            }
978            if let Some(prep) = prep {
979                prep(0..n);
980            }
981            let mesh = timed_mesh(|| Mesh::build(xyz, &walk, active_owned.as_deref(), edge))?;
982            let nbin = [mesh.nx, mesh.ny, mesh.nz];
983            let geom = geom_of(&walk, nbin, mesh.widths);
984            let max_reach = reach_of(&walk, &geom, mesh.image_reach());
985            let side = block_side(mesh.occupants.len(), nbin);
986            let (units, _) = scan_units(nbin, side);
987            let mut scratch = Scratch::default();
988            match mode {
989                0 => serial_scan::<0>(
990                    &mesh,
991                    &geom,
992                    k,
993                    max_reach,
994                    side,
995                    nn,
996                    dd,
997                    units,
998                    &mut scratch,
999                ),
1000                1 => serial_scan::<1>(
1001                    &mesh,
1002                    &geom,
1003                    k,
1004                    max_reach,
1005                    side,
1006                    nn,
1007                    dd,
1008                    units,
1009                    &mut scratch,
1010                ),
1011                _ => serial_scan::<2>(
1012                    &mesh,
1013                    &geom,
1014                    k,
1015                    max_reach,
1016                    side,
1017                    nn,
1018                    dd,
1019                    units,
1020                    &mut scratch,
1021                ),
1022            }
1023            drop(mesh);
1024            crate::team::run(1, None, tail);
1025            return Ok(());
1026        }
1027        let stages = bins::MeshStages::new(xyz, &walk, active_owned.as_deref(), edge, width)?;
1028        let nbin = stages.nbin();
1029        let geom = geom_of(&walk, nbin, stages.widths());
1030        let max_reach = reach_of(
1031            &walk,
1032            &geom,
1033            nbin.iter().copied().max().unwrap_or(1) / 2 + 2,
1034        );
1035        let side = block_side(stages.n_active(), nbin);
1036        let (units, _) = scan_units(nbin, side);
1037        let per = scan_chunk(units, width);
1038        let fold_chunks = stages.fold_chunks();
1039        let fold = |_: &mut Scratch, c: usize| {
1040            let _timer = crate::pop::JobTimer::new();
1041            stages.fold(c);
1042            let lo = n * c / fold_chunks;
1043            let hi = n * (c + 1) / fold_chunks;
1044            if let Some(prep) = prep {
1045                prep(lo..hi);
1046            }
1047            if let Some(m) = mask {
1048                for i in (lo..hi).filter(|&i| !m[i]) {
1049                    // SAFETY: chunk `c` alone fills masked rows `lo..hi`.
1050                    unsafe {
1051                        nn.row(i, k).fill(-1);
1052                        if let Some(d) = dd {
1053                            d.row(i, k).fill(f64::NAN);
1054                        }
1055                    }
1056                }
1057            }
1058        };
1059        let prefix = |_: &mut Scratch, _: usize| stages.prefix();
1060        let scatter = |_: &mut Scratch, t: usize| {
1061            let _timer = crate::pop::JobTimer::new();
1062            stages.scatter(t);
1063        };
1064        let mesh = stages.mesh();
1065        let geom = &geom;
1066        let path = crate::simd::select();
1067        let scan = move |s: &mut Scratch, c: usize| {
1068            let _timer = crate::pop::JobTimer::new();
1069            let lo = c * per;
1070            let hi = (lo + per).min(units);
1071            match mode {
1072                0 => scan_range::<0>(mesh, geom, k, max_reach, side, nn, dd, lo..hi, path, s),
1073                1 => scan_range::<1>(mesh, geom, k, max_reach, side, nn, dd, lo..hi, path, s),
1074                _ => scan_range::<2>(mesh, geom, k, max_reach, side, nn, dd, lo..hi, path, s),
1075            }
1076        };
1077        let mut list: Vec<Stage<'_, Scratch>> = vec![
1078            Stage {
1079                chunks: fold_chunks,
1080                run: &fold,
1081            },
1082            Stage {
1083                chunks: 1,
1084                run: &prefix,
1085            },
1086            Stage {
1087                chunks: stages.scatter_chunks(),
1088                run: &scatter,
1089            },
1090            Stage {
1091                chunks: (units + per - 1) / per,
1092                run: &scan,
1093            },
1094        ];
1095        list.extend(tail.iter().map(|t| Stage {
1096            chunks: t.chunks,
1097            run: t.run,
1098        }));
1099        crate::team::run(width, spawn, &list);
1100        Ok(())
1101    })
1102}
1103
1104fn timed_mesh(build: impl FnOnce() -> Result<Mesh, Error>) -> Result<Mesh, Error> {
1105    #[cfg(feature = "timing")]
1106    if crate::simd::coarse_timing_enabled() {
1107        let started = std::time::Instant::now();
1108        let mesh = build()?;
1109        crate::simd::add_mesh_ns(started.elapsed().as_nanos());
1110        return Ok(mesh);
1111    }
1112    build()
1113}
1114
1115fn geom_of(walk: &Cell, nbin: [i32; 3], widths: [f64; 3]) -> Geom {
1116    Geom {
1117        cols: [walk.a(), walk.b(), walk.c()],
1118        lengths: walk.widths(),
1119        nbin,
1120        widths,
1121    }
1122}
1123
1124/// Shell walk of every source in bin `c`.
1125#[cfg(all(feature = "parallel", linkcell_openmp))]
1126fn walk_cell<const MODE: u8>(
1127    mesh: &Mesh,
1128    geom: &Geom,
1129    k: usize,
1130    max_reach: i32,
1131    bin: [i32; 3],
1132    c: usize,
1133    out: (RowsOut<i32>, Option<RowsOut<f64>>),
1134) {
1135    let (nn, dd) = out;
1136    for slot in mesh.offsets[c]..mesh.offsets[c + 1] {
1137        let i = mesh.occupants[slot];
1138        // Safety: each source owns row `i` of both outputs, and the caller
1139        // sized them to `n * k`. No other slot writes that row.
1140        let (row, row_d2) = unsafe { (nn.row(i, k), dd.map(|d| d.row(i, k))) };
1141        walk_source::<MODE>(mesh, geom, k, max_reach, bin, slot, row, row_d2, None);
1142    }
1143}
1144
1145/// Shell walk of the cells in `begin..end`.
1146#[cfg(all(feature = "parallel", linkcell_openmp))]
1147fn walk_cells<const MODE: u8>(
1148    mesh: &Mesh,
1149    geom: &Geom,
1150    k: usize,
1151    max_reach: i32,
1152    out: (RowsOut<i32>, Option<RowsOut<f64>>),
1153    begin: usize,
1154    end: usize,
1155) {
1156    let [nx, ny, _] = geom.nbin;
1157    for c in begin..end {
1158        let c32 = c as i32;
1159        let bin = [c32 % nx, (c32 / nx) % ny, c32 / (nx * ny)];
1160        walk_cell::<MODE>(mesh, geom, k, max_reach, bin, c, out);
1161    }
1162}
1163
1164fn reach_of(walk: &Cell, geom: &Geom, image_reach: i32) -> i32 {
1165    let [nx, ny, nz] = geom.nbin;
1166    let widths = geom.widths;
1167    let cell_min = (widths[0] / f64::from(nx))
1168        .min(widths[1] / f64::from(ny))
1169        .min(widths[2] / f64::from(nz));
1170    let need = (box_diameter(walk) / cell_min).ceil();
1171    if need.is_finite() && need < 1.0e7 {
1172        (need as i32).saturating_add(3).max(image_reach)
1173    } else {
1174        image_reach
1175    }
1176}
1177
1178/// Scan units, blocks of `side` bins or single bins, and the blocks per
1179/// axis.
1180fn scan_units(nbin: [i32; 3], side: Option<i32>) -> (usize, [i32; 3]) {
1181    let [nx, ny, nz] = nbin;
1182    match side {
1183        Some(side) => {
1184            let blocks = [
1185                (nx + side - 1) / side,
1186                (ny + side - 1) / side,
1187                (nz + side - 1) / side,
1188            ];
1189            ((blocks[0] * blocks[1] * blocks[2]) as usize, blocks)
1190        }
1191        None => ((nx as usize) * (ny as usize) * (nz as usize), nbin),
1192    }
1193}
1194
1195#[allow(clippy::too_many_arguments)]
1196fn serial_scan<const MODE: u8>(
1197    mesh: &Mesh,
1198    geom: &Geom,
1199    k: usize,
1200    max_reach: i32,
1201    side: Option<i32>,
1202    nn: RowsOut<i32>,
1203    dd: Option<RowsOut<f64>>,
1204    units: usize,
1205    scratch: &mut Scratch,
1206) {
1207    let _timer = crate::pop::JobTimer::new();
1208    let path = crate::simd::select();
1209    scan_range::<MODE>(
1210        mesh,
1211        geom,
1212        k,
1213        max_reach,
1214        side,
1215        nn,
1216        dd,
1217        0..units,
1218        path,
1219        scratch,
1220    );
1221}
1222
1223/// Scan units `range`: blocks through [`scan_block`] when `side` is set,
1224/// bins through the shell walk otherwise.
1225#[allow(clippy::too_many_arguments)]
1226fn scan_range<const MODE: u8>(
1227    mesh: &Mesh,
1228    geom: &Geom,
1229    k: usize,
1230    max_reach: i32,
1231    side: Option<i32>,
1232    nn: RowsOut<i32>,
1233    dd: Option<RowsOut<f64>>,
1234    range: std::ops::Range<usize>,
1235    path: crate::simd::Path,
1236    scratch: &mut Scratch,
1237) {
1238    match side {
1239        Some(side) => {
1240            let (_, blocks) = scan_units(geom.nbin, Some(side));
1241            let Scratch { cand, heap, .. } = scratch;
1242            let heap = heap.get_or_insert_with(|| KHeap::new(k));
1243            for blk in range {
1244                scan_block::<MODE>(
1245                    mesh, geom, k, max_reach, side, blocks, path, nn, dd, cand, heap, blk,
1246                );
1247            }
1248        }
1249        None => {
1250            let [nx, ny, _] = geom.nbin;
1251            for c in range {
1252                let ci = c as i32;
1253                let bin = [ci % nx, (ci / nx) % ny, ci / (nx * ny)];
1254                for slot in mesh.offsets[c]..mesh.offsets[c + 1] {
1255                    let i = mesh.occupants[slot];
1256                    // Safety: each source owns row `i` of both outputs, and the
1257                    // caller sized them to `n * k`.
1258                    let (row, mut row_d2) = unsafe { (nn.row(i, k), dd.map(|d| d.row(i, k))) };
1259                    clear_row(row, row_d2.as_deref_mut());
1260                    walk_source::<MODE>(mesh, geom, k, max_reach, bin, slot, row, row_d2, None);
1261                }
1262            }
1263        }
1264    }
1265}
1266
1267/// Every slot of a row unused: the search writes the found prefix.
1268#[inline(always)]
1269fn clear_row(row: &mut [i32], d2: Option<&mut [f64]>) {
1270    row.fill(-1);
1271    if let Some(d2) = d2 {
1272        d2.fill(f64::NAN);
1273    }
1274}
1275
1276/// Bins a side of the source blocks of [`scan_block`] for this mesh:
1277/// two when bins hold few points, so eight bins share one gather, and one
1278/// otherwise. `None` when a candidate box would wrap onto itself.
1279fn block_side(n_active: usize, nbin: [i32; 3]) -> Option<i32> {
1280    #[cfg(test)]
1281    if NO_BLOCKS.load(std::sync::atomic::Ordering::Relaxed) {
1282        return None;
1283    }
1284    let ncell = nbin.iter().map(|&n| n as usize).product::<usize>().max(1);
1285    let side = if n_active < 4 * ncell { 2 } else { 1 };
1286    nbin.iter().all(|&n| n >= side + 2).then_some(side)
1287}
1288
1289/// Tests turn the blocks off to compare against the shell walk.
1290#[cfg(test)]
1291static NO_BLOCKS: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
1292
1293/// The points around one block of bins, each moved by its image shift as
1294/// [`visit_cell`] moves it, and their indices.
1295#[derive(Default)]
1296struct Candidates {
1297    x: Vec<f64>,
1298    y: Vec<f64>,
1299    z: Vec<f64>,
1300    id: Vec<u64>,
1301    /// One source's distances, read only through a raw pointer.
1302    #[cfg_attr(
1303        not(any(target_arch = "x86_64", target_arch = "aarch64")),
1304        allow(dead_code)
1305    )]
1306    d2: Vec<f64>,
1307}
1308
1309/// Shared inputs for one block scan. The candidate list and heap stay
1310/// per thread.
1311#[cfg(all(feature = "parallel", linkcell_openmp))]
1312struct BlockScan<'a> {
1313    mesh: &'a Mesh,
1314    geom: &'a Geom,
1315    k: usize,
1316    max_reach: i32,
1317    side: i32,
1318    blocks: [i32; 3],
1319    path: crate::simd::Path,
1320    time_scan: bool,
1321    nn: RowsOut<i32>,
1322    dd: Option<RowsOut<f64>>,
1323}
1324
1325/// One block of the shared-candidate scan. `blk` is the block index.
1326#[cfg(all(feature = "parallel", linkcell_openmp))]
1327fn select_one_block<const MODE: u8>(
1328    scan: &BlockScan<'_>,
1329    cand: &mut Candidates,
1330    heap: &mut KHeap,
1331    blk: usize,
1332) {
1333    let mesh = scan.mesh;
1334    let geom = scan.geom;
1335    let k = scan.k;
1336    let max_reach = scan.max_reach;
1337    let side = scan.side;
1338    let blocks = scan.blocks;
1339    let path = scan.path;
1340    let time_scan = scan.time_scan;
1341    let nn = scan.nn;
1342    let dd = scan.dd;
1343    let [nx, ny, nz] = geom.nbin;
1344    let blk = blk as i32;
1345    let x0 = side * (blk % blocks[0]);
1346    let y0 = side * ((blk / blocks[0]) % blocks[1]);
1347    let z0 = side * (blk / (blocks[0] * blocks[1]));
1348    cand.x.clear();
1349    cand.y.clear();
1350    cand.z.clear();
1351    cand.id.clear();
1352    let interior =
1353        x0 >= 1 && y0 >= 1 && z0 >= 1 && x0 + side < nx && y0 + side < ny && z0 + side < nz;
1354    for dz in -1..=side {
1355        for dy in -1..=side {
1356            // Inside the box a row of bins is one run of slots with no
1357            // shift: `p + 0` is `p`.
1358            if interior {
1359                let row = ((z0 + dz) * ny + (y0 + dy)) * nx + x0;
1360                let (lo, hi) = (
1361                    mesh.offsets[(row - 1) as usize],
1362                    mesh.offsets[(row + side + 1) as usize],
1363                );
1364                for slot in lo..hi {
1365                    let p = mesh.slot_folded[slot];
1366                    cand.x.push(p[0]);
1367                    cand.y.push(p[1]);
1368                    cand.z.push(p[2]);
1369                    cand.id.push(mesh.occupants[slot] as u64);
1370                }
1371                continue;
1372            }
1373            for dx in -1..=side {
1374                let (cell, na, nb, nc) = mesh.locate(x0 + dx, y0 + dy, z0 + dz);
1375                let shift = image_shift::<MODE>(geom, na, nb, nc);
1376                for slot in mesh.offsets[cell]..mesh.offsets[cell + 1] {
1377                    let p = mesh.slot_folded[slot];
1378                    cand.x.push(p[0] + shift[0]);
1379                    cand.y.push(p[1] + shift[1]);
1380                    cand.z.push(p[2] + shift[2]);
1381                    cand.id.push(mesh.occupants[slot] as u64);
1382                }
1383            }
1384        }
1385    }
1386    let planes = box_planes([x0, y0, z0], side, geom);
1387    for iz in z0..(z0 + side).min(nz) {
1388        for iy in y0..(y0 + side).min(ny) {
1389            for ix in x0..(x0 + side).min(nx) {
1390                let c = ((iz * ny + iy) * nx + ix) as usize;
1391                for slot in mesh.offsets[c]..mesh.offsets[c + 1] {
1392                    let i = mesh.occupants[slot];
1393                    // Safety: each source owns row `i` of both outputs,
1394                    // and the caller sized them to `n * k`.
1395                    let (row, row_d2) = unsafe { (nn.row(i, k), dd.map(|d| d.row(i, k))) };
1396                    heap.clear();
1397                    let pi = mesh.slot_folded[slot];
1398                    #[cfg(feature = "timing")]
1399                    if time_scan {
1400                        let started = std::time::Instant::now();
1401                        scan_at(path, cand, pi, i, heap);
1402                        crate::simd::add_scan_ns(started.elapsed().as_nanos());
1403                    } else {
1404                        scan_at(path, cand, pi, i, heap);
1405                    }
1406                    #[cfg(not(feature = "timing"))]
1407                    {
1408                        let _ = time_scan;
1409                        scan_at(path, cand, pi, i, heap);
1410                    }
1411                    let bound = box_bound(mesh.slot_frac[slot], &planes, geom);
1412                    if heap.full() && heap.worst() < bound {
1413                        heap.write_sorted(row, row_d2);
1414                    } else {
1415                        walk_source::<MODE>(
1416                            mesh,
1417                            geom,
1418                            k,
1419                            max_reach,
1420                            [ix, iy, iz],
1421                            slot,
1422                            row,
1423                            row_d2,
1424                            Some(heap.clone()),
1425                        );
1426                    }
1427                }
1428            }
1429        }
1430    }
1431}
1432
1433/// One block of `side` bins a side: a block's sources share one
1434/// candidate list, the occupants of the `side + 2` bins a side around
1435/// the block with their images, gathered once. When a source's k-th
1436/// neighbour is closer than the plane bound of the gathered bins, the answer
1437/// is among the candidates: every other point lies strictly past one of
1438/// those planes. Distances are formed as [`visit_cell`] forms them and
1439/// the heap keeps the same k, so every row is the shell walk's; a source
1440/// the bound does not settle resumes the shell walk from its heap, which
1441/// holds its 3 x 3 x 3 bins already.
1442#[allow(clippy::too_many_arguments)]
1443#[inline(always)]
1444fn scan_block<const MODE: u8>(
1445    mesh: &Mesh,
1446    geom: &Geom,
1447    k: usize,
1448    max_reach: i32,
1449    side: i32,
1450    blocks: [i32; 3],
1451    path: crate::simd::Path,
1452    nn: RowsOut<i32>,
1453    dd: Option<RowsOut<f64>>,
1454    cand: &mut Candidates,
1455    heap: &mut KHeap,
1456    blk: usize,
1457) {
1458    let [nx, ny, nz] = geom.nbin;
1459    #[cfg(feature = "timing")]
1460    let time_scan = crate::simd::scan_timing_enabled();
1461    let blk = blk as i32;
1462    let x0 = side * (blk % blocks[0]);
1463    let y0 = side * ((blk / blocks[0]) % blocks[1]);
1464    let z0 = side * (blk / (blocks[0] * blocks[1]));
1465    cand.x.clear();
1466    cand.y.clear();
1467    cand.z.clear();
1468    cand.id.clear();
1469    let interior =
1470        x0 >= 1 && y0 >= 1 && z0 >= 1 && x0 + side < nx && y0 + side < ny && z0 + side < nz;
1471    for dz in -1..=side {
1472        for dy in -1..=side {
1473            // Inside the box a row of bins is one run of slots with no
1474            // shift: `p + 0` is `p`.
1475            if interior {
1476                let row = ((z0 + dz) * ny + (y0 + dy)) * nx + x0;
1477                let (lo, hi) = (
1478                    mesh.offsets[(row - 1) as usize],
1479                    mesh.offsets[(row + side + 1) as usize],
1480                );
1481                for slot in lo..hi {
1482                    let p = mesh.slot_folded[slot];
1483                    cand.x.push(p[0]);
1484                    cand.y.push(p[1]);
1485                    cand.z.push(p[2]);
1486                    cand.id.push(mesh.occupants[slot] as u64);
1487                }
1488                continue;
1489            }
1490            for dx in -1..=side {
1491                let (cell, na, nb, nc) = mesh.locate(x0 + dx, y0 + dy, z0 + dz);
1492                let shift = image_shift::<MODE>(geom, na, nb, nc);
1493                for slot in mesh.offsets[cell]..mesh.offsets[cell + 1] {
1494                    let p = mesh.slot_folded[slot];
1495                    cand.x.push(p[0] + shift[0]);
1496                    cand.y.push(p[1] + shift[1]);
1497                    cand.z.push(p[2] + shift[2]);
1498                    cand.id.push(mesh.occupants[slot] as u64);
1499                }
1500            }
1501        }
1502    }
1503    let planes = box_planes([x0, y0, z0], side, geom);
1504    for iz in z0..(z0 + side).min(nz) {
1505        for iy in y0..(y0 + side).min(ny) {
1506            for ix in x0..(x0 + side).min(nx) {
1507                let c = ((iz * ny + iy) * nx + ix) as usize;
1508                for slot in mesh.offsets[c]..mesh.offsets[c + 1] {
1509                    let i = mesh.occupants[slot];
1510                    // Safety: each source owns row `i` of both outputs,
1511                    // and the caller sized them to `n * k`.
1512                    let (row, mut row_d2) = unsafe { (nn.row(i, k), dd.map(|d| d.row(i, k))) };
1513                    clear_row(row, row_d2.as_deref_mut());
1514                    heap.clear();
1515                    let pi = mesh.slot_folded[slot];
1516                    #[cfg(feature = "timing")]
1517                    if time_scan {
1518                        let started = std::time::Instant::now();
1519                        scan_at(path, cand, pi, i, heap);
1520                        crate::simd::add_scan_ns(started.elapsed().as_nanos());
1521                    } else {
1522                        scan_at(path, cand, pi, i, heap);
1523                    }
1524                    #[cfg(not(feature = "timing"))]
1525                    scan_at(path, cand, pi, i, heap);
1526                    let bound = box_bound(mesh.slot_frac[slot], &planes, geom);
1527                    if heap.full() && heap.worst() < bound {
1528                        heap.write_sorted(row, row_d2);
1529                    } else {
1530                        walk_source::<MODE>(
1531                            mesh,
1532                            geom,
1533                            k,
1534                            max_reach,
1535                            [ix, iy, iz],
1536                            slot,
1537                            row,
1538                            row_d2,
1539                            Some(heap.clone()),
1540                        );
1541                    }
1542                }
1543            }
1544        }
1545    }
1546}
1547
1548/// Fractional planes of the gathered bins, from `corner - 1` to `corner +
1549/// side` on each axis: `[lower, upper]` per axis.
1550fn box_planes(corner: [i32; 3], side: i32, geom: &Geom) -> [[f64; 2]; 3] {
1551    std::array::from_fn(|a| {
1552        let nf = f64::from(geom.nbin[a]);
1553        [
1554            f64::from(corner[a] - 1) / nf,
1555            f64::from(corner[a] + side + 1) / nf,
1556        ]
1557    })
1558}
1559
1560/// The squared plane bound of the gathered bins, formed as [`axis_gap`]
1561/// forms the shell walk's: bins are half-open, so every point not
1562/// gathered lies strictly past one of these planes.
1563fn box_bound(origin: [f64; 3], planes: &[[f64; 2]; 3], geom: &Geom) -> f64 {
1564    (0..3)
1565        .map(|a| {
1566            let plus = (planes[a][1] - origin[a]) * geom.widths[a];
1567            let minus = (origin[a] - planes[a][0]) * geom.widths[a];
1568            let gap = plus.min(minus);
1569            if gap > 0.0 && gap.is_finite() {
1570                gap * gap
1571            } else {
1572                0.0
1573            }
1574        })
1575        .fold(f64::INFINITY, f64::min)
1576}
1577
1578/// [`scan`] on `path`. [`crate::simd::select`] already rejected a path
1579/// this CPU cannot run. A stale path falls through to [`scan`].
1580fn scan_at(
1581    path: crate::simd::Path,
1582    cand: &mut Candidates,
1583    pi: [f64; 3],
1584    i: usize,
1585    heap: &mut KHeap,
1586) {
1587    match path {
1588        #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1589        crate::simd::Path::Avx512 => {
1590            debug_assert!(std::is_x86_feature_detected!("avx512f"));
1591            // Safety: `select` only returns this path when AVX-512F is available.
1592            unsafe { scan_avx512(cand, pi, i, heap) };
1593        }
1594        #[cfg(target_arch = "x86_64")]
1595        crate::simd::Path::Avx2 => {
1596            debug_assert!(
1597                std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma")
1598            );
1599            // Safety: `select` only returns this path when AVX2 and FMA are available.
1600            // FMA is not enabled on the kernel.
1601            unsafe { scan_avx2(cand, pi, i, heap) };
1602        }
1603        #[cfg(target_arch = "aarch64")]
1604        crate::simd::Path::Neon => {
1605            // Safety: NEON is baseline on aarch64, and `select` only
1606            // returns this path when that target feature is on.
1607            unsafe { scan_neon(cand, pi, i, heap) };
1608        }
1609        _ => scan(cand, pi, i, heap),
1610    }
1611}
1612
1613/// Push every candidate but the source itself.
1614fn scan(cand: &Candidates, pi: [f64; 3], i: usize, heap: &mut KHeap) {
1615    for t in 0..cand.x.len() {
1616        let j = cand.id[t] as usize;
1617        if j != i {
1618            let dx = cand.x[t] - pi[0];
1619            let dy = cand.y[t] - pi[1];
1620            let dz = cand.z[t] - pi[2];
1621            heap.push(dx * dx + dy * dy + dz * dz, j);
1622        }
1623    }
1624}
1625
1626/// [`scan`] eight candidates at a time, in two passes. The first forms
1627/// every distance and the lane-wise minimum over all of them: eight
1628/// distances of eight different candidates, so the k-th smallest of them
1629/// bounds the k-th nearest from above. The second pushes only candidates
1630/// at or under that bound (and under the heap's worst once it is full),
1631/// which are all [`KHeap::push`] could keep.
1632///
1633/// # Safety
1634/// AVX-512F is available.
1635#[allow(clippy::incompatible_msrv)]
1636#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1637#[target_feature(enable = "avx512f")]
1638unsafe fn scan_avx512(cand: &mut Candidates, pi: [f64; 3], i: usize, heap: &mut KHeap) {
1639    use std::arch::x86_64::{
1640        _mm512_add_pd, _mm512_cmp_pd_mask, _mm512_cmpneq_epi64_mask, _mm512_loadu_pd,
1641        _mm512_mask_blend_pd, _mm512_maskz_loadu_epi64, _mm512_maskz_loadu_pd, _mm512_min_pd,
1642        _mm512_mul_pd, _mm512_set1_epi64, _mm512_set1_pd, _mm512_storeu_pd, _mm512_sub_pd,
1643        _CMP_LE_OQ, _CMP_LT_OQ,
1644    };
1645    let m = cand.x.len();
1646    let padded = (m + 7) & !7;
1647    cand.d2.clear();
1648    cand.d2.reserve(padded);
1649    let dp = cand.d2.as_mut_ptr();
1650    let (px, py, pz) = (
1651        _mm512_set1_pd(pi[0]),
1652        _mm512_set1_pd(pi[1]),
1653        _mm512_set1_pd(pi[2]),
1654    );
1655    let me = _mm512_set1_epi64(i as i64);
1656    let inf = _mm512_set1_pd(f64::INFINITY);
1657    let mut low = inf;
1658    let mut t = 0usize;
1659    while t < m {
1660        let tm: u8 = if m - t >= 8 {
1661            0xff
1662        } else {
1663            ((1u32 << (m - t)) - 1) as u8
1664        };
1665        let dx = _mm512_sub_pd(_mm512_maskz_loadu_pd(tm, cand.x.as_ptr().add(t)), px);
1666        let dy = _mm512_sub_pd(_mm512_maskz_loadu_pd(tm, cand.y.as_ptr().add(t)), py);
1667        let dz = _mm512_sub_pd(_mm512_maskz_loadu_pd(tm, cand.z.as_ptr().add(t)), pz);
1668        let d2 = _mm512_add_pd(
1669            _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
1670            _mm512_mul_pd(dz, dz),
1671        );
1672        let ids = _mm512_maskz_loadu_epi64(tm, cand.id.as_ptr().add(t) as *const i64);
1673        let keep = _mm512_cmpneq_epi64_mask(ids, me) & tm;
1674        // The source itself and lanes past the end never count.
1675        let d2 = _mm512_mask_blend_pd(keep, inf, d2);
1676        low = _mm512_min_pd(low, d2);
1677        _mm512_storeu_pd(dp.add(t), d2);
1678        t += 8;
1679    }
1680    let mut bound = f64::INFINITY;
1681    if heap.k <= 8 {
1682        let mut lanes = [0.0f64; 8];
1683        _mm512_storeu_pd(lanes.as_mut_ptr(), low);
1684        lanes.sort_unstable_by(f64::total_cmp);
1685        bound = lanes[heap.k - 1];
1686    }
1687    let mut t = 0usize;
1688    while t < padded {
1689        let limit = if heap.full() {
1690            heap.worst().min(bound)
1691        } else {
1692            bound
1693        };
1694        let d2 = _mm512_loadu_pd(dp.add(t));
1695        let mut take: u8 = _mm512_cmp_pd_mask::<_CMP_LE_OQ>(d2, _mm512_set1_pd(limit))
1696            & _mm512_cmp_pd_mask::<_CMP_LT_OQ>(d2, inf);
1697        while take != 0 {
1698            let l = take.trailing_zeros() as usize;
1699            take &= take - 1;
1700            heap.push(*dp.add(t + l), cand.id[t + l] as usize);
1701        }
1702        t += 8;
1703    }
1704}
1705
1706/// [`scan`] four candidates at a time. Sums are separate multiplies and
1707/// adds, the same order as [`scan`], so each distance is the same bits.
1708/// The lane-wise minimums bound the push when `k` fits in four lanes.
1709///
1710/// # Safety
1711/// AVX2 is available. FMA is a selection gate and is not enabled here.
1712#[allow(clippy::incompatible_msrv)]
1713#[cfg(target_arch = "x86_64")]
1714#[target_feature(enable = "avx,avx2")]
1715unsafe fn scan_avx2(cand: &mut Candidates, pi: [f64; 3], i: usize, heap: &mut KHeap) {
1716    use std::arch::x86_64::{
1717        _mm256_add_pd, _mm256_and_pd, _mm256_blendv_pd, _mm256_castsi256_pd, _mm256_cmp_pd,
1718        _mm256_cmpeq_epi64, _mm256_loadu_pd, _mm256_loadu_si256, _mm256_min_pd, _mm256_movemask_pd,
1719        _mm256_mul_pd, _mm256_set1_epi64x, _mm256_set1_pd, _mm256_storeu_pd, _mm256_sub_pd,
1720        _CMP_LE_OQ, _CMP_LT_OQ,
1721    };
1722    let m = cand.x.len();
1723    let padded = (m + 3) & !3;
1724    cand.d2.clear();
1725    cand.d2.reserve(padded);
1726    let dp = cand.d2.as_mut_ptr();
1727    let (px, py, pz) = (
1728        _mm256_set1_pd(pi[0]),
1729        _mm256_set1_pd(pi[1]),
1730        _mm256_set1_pd(pi[2]),
1731    );
1732    let me = _mm256_set1_epi64x(i as i64);
1733    let inf = _mm256_set1_pd(f64::INFINITY);
1734    let mut low = inf;
1735    let mut t = 0usize;
1736    while t < m {
1737        let (xv, yv, zv, ids) = if m - t >= 4 {
1738            (
1739                _mm256_loadu_pd(cand.x.as_ptr().add(t)),
1740                _mm256_loadu_pd(cand.y.as_ptr().add(t)),
1741                _mm256_loadu_pd(cand.z.as_ptr().add(t)),
1742                _mm256_loadu_si256(cand.id.as_ptr().add(t).cast()),
1743            )
1744        } else {
1745            let n = m - t;
1746            let mut x = [0.0f64; 4];
1747            let mut y = [0.0f64; 4];
1748            let mut z = [0.0f64; 4];
1749            let mut id = [i as u64; 4];
1750            x[..n].copy_from_slice(&cand.x[t..m]);
1751            y[..n].copy_from_slice(&cand.y[t..m]);
1752            z[..n].copy_from_slice(&cand.z[t..m]);
1753            id[..n].copy_from_slice(&cand.id[t..m]);
1754            (
1755                _mm256_loadu_pd(x.as_ptr()),
1756                _mm256_loadu_pd(y.as_ptr()),
1757                _mm256_loadu_pd(z.as_ptr()),
1758                _mm256_loadu_si256(id.as_ptr().cast()),
1759            )
1760        };
1761        let dx = _mm256_sub_pd(xv, px);
1762        let dy = _mm256_sub_pd(yv, py);
1763        let dz = _mm256_sub_pd(zv, pz);
1764        let d2 = _mm256_add_pd(
1765            _mm256_add_pd(_mm256_mul_pd(dx, dx), _mm256_mul_pd(dy, dy)),
1766            _mm256_mul_pd(dz, dz),
1767        );
1768        let eq = _mm256_cmpeq_epi64(ids, me);
1769        let d2 = _mm256_blendv_pd(d2, inf, _mm256_castsi256_pd(eq));
1770        low = _mm256_min_pd(low, d2);
1771        _mm256_storeu_pd(dp.add(t), d2);
1772        t += 4;
1773    }
1774    let mut bound = f64::INFINITY;
1775    if (1..=4).contains(&heap.k) && m > 0 {
1776        let mut lanes = [0.0f64; 4];
1777        _mm256_storeu_pd(lanes.as_mut_ptr(), low);
1778        lanes.sort_unstable_by(f64::total_cmp);
1779        bound = lanes[heap.k - 1];
1780    }
1781    let mut t = 0usize;
1782    while t < m {
1783        let limit = if heap.full() {
1784            heap.worst().min(bound)
1785        } else {
1786            bound
1787        };
1788        let d2 = _mm256_loadu_pd(dp.add(t));
1789        let le = _mm256_cmp_pd::<_CMP_LE_OQ>(d2, _mm256_set1_pd(limit));
1790        let lt = _mm256_cmp_pd::<_CMP_LT_OQ>(d2, inf);
1791        let mut take = _mm256_movemask_pd(_mm256_and_pd(le, lt));
1792        while take != 0 {
1793            let l = take.trailing_zeros() as usize;
1794            take &= take - 1;
1795            if t + l < m {
1796                heap.push(*dp.add(t + l), cand.id[t + l] as usize);
1797            }
1798        }
1799        t += 4;
1800    }
1801}
1802
1803/// [`scan`] two candidates at a time. The arithmetic matches [`scan`].
1804///
1805/// # Safety
1806/// NEON is available.
1807#[cfg(target_arch = "aarch64")]
1808#[target_feature(enable = "neon")]
1809unsafe fn scan_neon(cand: &mut Candidates, pi: [f64; 3], i: usize, heap: &mut KHeap) {
1810    use std::arch::aarch64::{
1811        vaddq_f64, vandq_u64, vbslq_f64, vceqq_u64, vcleq_f64, vcltq_f64, vdupq_n_f64, vdupq_n_u64,
1812        vgetq_lane_f64, vgetq_lane_u64, vld1q_f64, vld1q_u64, vminq_f64, vmulq_f64, vst1q_f64,
1813        vsubq_f64,
1814    };
1815    let m = cand.x.len();
1816    let padded = (m + 1) & !1;
1817    cand.d2.clear();
1818    cand.d2.reserve(padded);
1819    let dp = cand.d2.as_mut_ptr();
1820    let (px, py, pz) = (vdupq_n_f64(pi[0]), vdupq_n_f64(pi[1]), vdupq_n_f64(pi[2]));
1821    let me = vdupq_n_u64(i as u64);
1822    let inf = vdupq_n_f64(f64::INFINITY);
1823    let mut low = inf;
1824    let mut t = 0usize;
1825    while t < m {
1826        let (xv, yv, zv, ids) = if m - t >= 2 {
1827            (
1828                vld1q_f64(cand.x.as_ptr().add(t)),
1829                vld1q_f64(cand.y.as_ptr().add(t)),
1830                vld1q_f64(cand.z.as_ptr().add(t)),
1831                vld1q_u64(cand.id.as_ptr().add(t)),
1832            )
1833        } else {
1834            let mut x = [0.0f64; 2];
1835            let mut y = [0.0f64; 2];
1836            let mut z = [0.0f64; 2];
1837            let mut id = [i as u64; 2];
1838            x[0] = cand.x[t];
1839            y[0] = cand.y[t];
1840            z[0] = cand.z[t];
1841            id[0] = cand.id[t];
1842            (
1843                vld1q_f64(x.as_ptr()),
1844                vld1q_f64(y.as_ptr()),
1845                vld1q_f64(z.as_ptr()),
1846                vld1q_u64(id.as_ptr()),
1847            )
1848        };
1849        let dx = vsubq_f64(xv, px);
1850        let dy = vsubq_f64(yv, py);
1851        let dz = vsubq_f64(zv, pz);
1852        let d2 = vaddq_f64(
1853            vaddq_f64(vmulq_f64(dx, dx), vmulq_f64(dy, dy)),
1854            vmulq_f64(dz, dz),
1855        );
1856        let eq = vceqq_u64(ids, me);
1857        let d2 = vbslq_f64(eq, inf, d2);
1858        low = vminq_f64(low, d2);
1859        vst1q_f64(dp.add(t), d2);
1860        t += 2;
1861    }
1862    let mut bound = f64::INFINITY;
1863    if (1..=2).contains(&heap.k) && m > 0 {
1864        let mut lanes = [0.0f64; 2];
1865        vst1q_f64(lanes.as_mut_ptr(), low);
1866        lanes.sort_unstable_by(f64::total_cmp);
1867        bound = lanes[heap.k - 1];
1868    }
1869    let mut t = 0usize;
1870    while t < m {
1871        let limit = if heap.full() {
1872            heap.worst().min(bound)
1873        } else {
1874            bound
1875        };
1876        let d2 = vld1q_f64(dp.add(t));
1877        let take = vandq_u64(vcleq_f64(d2, vdupq_n_f64(limit)), vcltq_f64(d2, inf));
1878        if vgetq_lane_u64::<0>(take) != 0 {
1879            heap.push(vgetq_lane_f64::<0>(d2), cand.id[t] as usize);
1880        }
1881        if t + 1 < m && vgetq_lane_u64::<1>(take) != 0 {
1882            heap.push(vgetq_lane_f64::<1>(d2), cand.id[t + 1] as usize);
1883        }
1884        t += 2;
1885    }
1886}
1887
1888/// An output many sources write, one row each.
1889#[derive(Clone, Copy)]
1890struct RowsOut<T>(*mut T);
1891unsafe impl<T: Send> Send for RowsOut<T> {}
1892unsafe impl<T: Send> Sync for RowsOut<T> {}
1893
1894impl<T> RowsOut<T> {
1895    /// Row `i` of width `k`.
1896    ///
1897    /// # Safety
1898    /// The output holds row `i`, and no other job touches it while the
1899    /// slice lives.
1900    #[allow(clippy::mut_from_ref)]
1901    unsafe fn row<'a>(self, i: usize, k: usize) -> &'a mut [T] {
1902        std::slice::from_raw_parts_mut(self.0.add(i * k), k)
1903    }
1904}
1905
1906/// The shell walk of one source. `start` is a heap that already holds
1907/// every point of the source's 3 x 3 x 3 bins (and maybe more): the walk
1908/// then begins at the next layer, and a point it meets again changes
1909/// nothing, since the heap keeps one image per point.
1910#[inline(always)]
1911#[allow(clippy::too_many_arguments)]
1912fn walk_source<const MODE: u8>(
1913    mesh: &Mesh,
1914    geom: &Geom,
1915    k: usize,
1916    max_reach: i32,
1917    bin: [i32; 3],
1918    slot: usize,
1919    nn: &mut [i32],
1920    d2: Option<&mut [f64]>,
1921    start: Option<KHeap>,
1922) {
1923    let resumed = start.is_some();
1924    let mut heap = start.unwrap_or_else(|| KHeap::new(k));
1925    let [ix, iy, iz] = bin;
1926    let i = mesh.occupants[slot];
1927    let origin = mesh.slot_frac[slot];
1928    let pi = mesh.slot_folded[slot];
1929    // Nothing visited yet. The first layer is the 3x3x3 around the source.
1930    let mut prev = [-1i32; 3];
1931    let mut reach = [1i32; 3];
1932    let mut first = true;
1933    loop {
1934        if !(first && resumed) {
1935            let mut query = CellQuery {
1936                heap: &mut heap,
1937                mesh,
1938                geom,
1939                i,
1940                pi,
1941                origin,
1942            };
1943            let allow_slab = prev[0] >= 0;
1944            for_new_layer(prev, reach, |dx, dy, dz| {
1945                visit_cell::<MODE>(&mut query, ix + dx, iy + dy, iz + dz, allow_slab);
1946            });
1947        }
1948        first = false;
1949        let gaps = [
1950            axis_gap(origin[0], ix, reach[0], geom.nbin[0], geom.widths[0]),
1951            axis_gap(origin[1], iy, reach[1], geom.nbin[1], geom.widths[1]),
1952            axis_gap(origin[2], iz, reach[2], geom.nbin[2], geom.widths[2]),
1953        ];
1954        if heap.full() {
1955            let bound = gaps
1956                .into_iter()
1957                .map(|gap| {
1958                    if gap > 0.0 && gap.is_finite() {
1959                        gap * gap
1960                    } else {
1961                        0.0
1962                    }
1963                })
1964                .fold(f64::INFINITY, f64::min);
1965            if heap.worst() <= bound {
1966                break;
1967            }
1968        }
1969        prev = reach;
1970        let mut grew = false;
1971        if heap.full() {
1972            let worst = heap.worst();
1973            for a in 0..3 {
1974                let gap2 = if gaps[a] > 0.0 && gaps[a].is_finite() {
1975                    gaps[a] * gaps[a]
1976                } else {
1977                    0.0
1978                };
1979                if worst > gap2 && reach[a] < max_reach {
1980                    reach[a] += 1;
1981                    grew = true;
1982                }
1983            }
1984        } else {
1985            for slot in &mut reach {
1986                if *slot < max_reach {
1987                    *slot += 1;
1988                    grew = true;
1989                }
1990            }
1991        }
1992        if !grew {
1993            break;
1994        }
1995    }
1996    heap.write_sorted(nn, d2);
1997}
1998
1999struct CellQuery<'a> {
2000    heap: &'a mut KHeap,
2001    mesh: &'a Mesh,
2002    geom: &'a Geom,
2003    i: usize,
2004    pi: [f64; 3],
2005    origin: [f64; 3],
2006}
2007
2008/// Cartesian shift of image `(na, nb, nc)` of a bin.
2009#[inline(always)]
2010fn image_shift<const MODE: u8>(geom: &Geom, na: i32, nb: i32, nc: i32) -> [f64; 3] {
2011    if MODE == 0 {
2012        if (na | nb | nc) == 0 {
2013            [0.0; 3]
2014        } else {
2015            [
2016                f64::from(na) * geom.lengths[0],
2017                f64::from(nb) * geom.lengths[1],
2018                f64::from(nc) * geom.lengths[2],
2019            ]
2020        }
2021    } else if MODE == 1 {
2022        // Restricted triclinic: a along x, b in the xy plane.
2023        let fa = f64::from(na);
2024        let fb = f64::from(nb);
2025        let fc = f64::from(nc);
2026        let a = geom.cols[0];
2027        let b = geom.cols[1];
2028        let c = geom.cols[2];
2029        [
2030            fa * a[0] + fb * b[0] + fc * c[0],
2031            fb * b[1] + fc * c[1],
2032            fc * c[2],
2033        ]
2034    } else {
2035        let fa = f64::from(na);
2036        let fb = f64::from(nb);
2037        let fc = f64::from(nc);
2038        let a = geom.cols[0];
2039        let b = geom.cols[1];
2040        let c = geom.cols[2];
2041        [
2042            fa * a[0] + fb * b[0] + fc * c[0],
2043            fa * a[1] + fb * b[1] + fc * c[1],
2044            fa * a[2] + fb * b[2] + fc * c[2],
2045        ]
2046    }
2047}
2048
2049#[inline(always)]
2050fn visit_cell<const MODE: u8>(q: &mut CellQuery<'_>, jx: i32, jy: i32, jz: i32, allow_slab: bool) {
2051    let (cell, na, nb, nc) = q.mesh.locate(jx, jy, jz);
2052    let lo = q.mesh.offsets[cell];
2053    let hi = q.mesh.offsets[cell + 1];
2054    let count = hi - lo;
2055    if count == 0 {
2056        return;
2057    }
2058    // One orthorhombic occupant is a subtract and three multiplies.
2059    // The slab test is three divisions, so it only pays for a crowded bin.
2060    // Mode 0 is orthorhombic: one occupant is a subtract, and the slab
2061    // test costs more than the distance. Restricted and general cells
2062    // keep the slab, because the shift is a matrix product.
2063    if allow_slab && !(MODE == 0 && count == 1) && q.heap.full() {
2064        let lb = slab_dist2(q.origin, [jx, jy, jz], q.geom.nbin, q.geom.widths);
2065        if q.heap.worst() <= lb {
2066            return;
2067        }
2068    }
2069    let shift = image_shift::<MODE>(q.geom, na, nb, nc);
2070    let pi = q.pi;
2071    for (&ju, &p) in q.mesh.occupants[lo..hi]
2072        .iter()
2073        .zip(&q.mesh.slot_folded[lo..hi])
2074    {
2075        if ju != q.i {
2076            let dx = p[0] + shift[0] - pi[0];
2077            let dy = p[1] + shift[1] - pi[1];
2078            let dz = p[2] + shift[2] - pi[2];
2079            q.heap.push(dx * dx + dy * dy + dz * dz, ju);
2080        }
2081    }
2082}
2083
2084/// Brute-force k-nearest. Tests and small systems only.
2085///
2086/// An orthorhombic box calls [`crate::dist2_ortho_diffs`]: SoA
2087/// differences, one reciprocal per axis, then the Highway wrap
2088/// `dr -= box * round(dr / box)`. On a rectangular box that wrap is
2089/// the Euclidean nearest image. Any other box stays on
2090/// [`Cell::dist2_euclidean`]: Smith half-edge test, then a
2091/// Minkowski-reduced 27-image. A hex-prism body diagonal is a
2092/// fractional wrap that is not the nearest image.
2093///
2094/// ```
2095/// use linkcell::{knearest, knearest_brute, Cell};
2096///
2097/// # fn main() -> Result<(), linkcell::Error> {
2098/// let sim = Cell::ortho(10.0, 10.0, 10.0)?;
2099/// let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
2100/// let cell = knearest(&xyz, &sim, 1, None, None)?;
2101/// let brute = knearest_brute(&xyz, &sim, 1, None)?;
2102/// assert_eq!(cell[0].indices, brute[0].indices);
2103/// assert!((cell[0].dist2[0] - brute[0].dist2[0]).abs() < 1e-12);
2104/// # Ok(())
2105/// # }
2106/// ```
2107pub fn knearest_brute(
2108    xyz: &[[f64; 3]],
2109    simbox: &Cell,
2110    k: usize,
2111    mask: Option<&[bool]>,
2112) -> Result<Vec<Neighbors>, Error> {
2113    if k == 0 {
2114        return Err(Error::ZeroK);
2115    }
2116    if xyz.is_empty() {
2117        return Err(Error::Empty);
2118    }
2119    let n = xyz.len();
2120    let active: Vec<usize> = (0..n)
2121        .filter(|&i| {
2122            mask.map(|m| m.get(i).copied().unwrap_or(false))
2123                .unwrap_or(true)
2124        })
2125        .collect();
2126    let mut out = vec![Neighbors::default(); n];
2127    let ortho = simbox.is_ortho();
2128    let widths = simbox.widths();
2129    for &i in &active {
2130        let others: Vec<usize> = active.iter().copied().filter(|&j| j != i).collect();
2131        let d2 = if ortho {
2132            ortho_highway_dist2(xyz[i], &others, xyz, widths)?
2133        } else {
2134            others
2135                .iter()
2136                .map(|&j| pair_dist2(simbox, xyz[i], xyz[j]))
2137                .collect()
2138        };
2139        let mut pairs: Vec<(f64, usize)> = d2.into_iter().zip(others).collect();
2140        pairs.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.cmp(&b.1)));
2141        pairs.truncate(k);
2142        out[i].dist2 = pairs.iter().map(|p| p.0).collect();
2143        out[i].indices = pairs.iter().map(|p| p.1).collect();
2144    }
2145    Ok(out)
2146}
2147
2148#[cfg(all(feature = "parallel", linkcell_openmp))]
2149#[path = "knn_fused.rs"]
2150mod fused;
2151
2152#[cfg(test)]
2153mod scale_mesh_tests {
2154    use super::*;
2155
2156    #[test]
2157    fn brute_ortho_matches_euclidean_mic() {
2158        let (xyz, cell) = ortho_lattice(4);
2159        let k = 4;
2160        let brute = knearest_brute(&xyz, &cell, k, None).unwrap();
2161        let mut best: Vec<(f64, usize)> = (1..xyz.len())
2162            .map(|j| (cell.dist2_euclidean(xyz[0], xyz[j]), j))
2163            .collect();
2164        best.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.cmp(&b.1)));
2165        best.truncate(k);
2166        assert_eq!(
2167            brute[0].indices,
2168            best.iter().map(|p| p.1).collect::<Vec<_>>()
2169        );
2170        for (t, (d, _)) in best.iter().enumerate() {
2171            assert!((brute[0].dist2[t] - d).abs() < 1e-12);
2172        }
2173    }
2174
2175    fn ortho_lattice(nside: usize) -> (Vec<[f64; 3]>, Cell) {
2176        let a = 3.125;
2177        let boxl = nside as f64 * a;
2178        let cell = Cell::ortho(boxl, boxl, boxl).unwrap();
2179        let mut xyz = Vec::with_capacity(nside * nside * nside);
2180        for iz in 0..nside {
2181            for iy in 0..nside {
2182                for ix in 0..nside {
2183                    xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
2184                }
2185            }
2186        }
2187        (xyz, cell)
2188    }
2189
2190    fn assert_certified(
2191        cell: &Cell,
2192        xyz: &[[f64; 3]],
2193        active: &[usize],
2194        i: usize,
2195        row: &Neighbors,
2196    ) {
2197        let k = 4;
2198        let mut best: Vec<(f64, usize)> = active
2199            .iter()
2200            .copied()
2201            .filter(|&j| j != i)
2202            .map(|j| (cell.dist2_euclidean(xyz[i], xyz[j]), j))
2203            .collect();
2204        best.sort_by(|p, q| p.0.total_cmp(&q.0).then(p.1.cmp(&q.1)));
2205        let kth = best[k - 1].0;
2206        assert_eq!(row.indices.len(), k);
2207        for (&d, &j) in row.dist2.iter().zip(&row.indices) {
2208            let true_d = cell.dist2_euclidean(xyz[i], xyz[j]);
2209            assert!((d - true_d).abs() <= 1e-8 * true_d.max(1.0));
2210            assert!(
2211                d <= kth * (1.0 + 1e-8) + 1e-9,
2212                "i={i} j={j} d={d} kth={kth}"
2213            );
2214        }
2215        for (d, j) in &best {
2216            if *d + 1e-8 < kth {
2217                assert!(
2218                    row.indices.contains(j),
2219                    "i={i} missed closer {j} d={d} kth={kth}"
2220                );
2221            }
2222        }
2223    }
2224
2225    #[test]
2226    fn parallel_mesh_matches_euclidean_on_a_large_lattice() {
2227        // 22^3 = 10648 active points, above the parallel-mesh threshold.
2228        let (xyz, cell) = ortho_lattice(22);
2229        let rows = knearest(&xyz, &cell, 4, None, Some(3.0)).unwrap();
2230        let active: Vec<usize> = (0..xyz.len()).collect();
2231        for i in (0..xyz.len()).step_by(700) {
2232            assert_certified(&cell, &xyz, &active, i, &rows[i]);
2233        }
2234    }
2235
2236    #[test]
2237    fn parallel_mesh_respects_a_mask() {
2238        let (xyz, cell) = ortho_lattice(26);
2239        let mask: Vec<bool> = (0..xyz.len()).map(|i| i % 2 == 0).collect();
2240        let rows = knearest(&xyz, &cell, 4, Some(&mask), Some(3.0)).unwrap();
2241        let active: Vec<usize> = (0..xyz.len()).filter(|&i| mask[i]).collect();
2242        assert!(active.len() >= 8_192);
2243        for &i in active.iter().step_by(900) {
2244            assert_certified(&cell, &xyz, &active, i, &rows[i]);
2245            assert!(rows[i + 1].indices.is_empty());
2246        }
2247    }
2248
2249    #[test]
2250    fn blocks_write_the_shell_walk_rows() {
2251        // Lattices a few ulps off (many equal distances, so index order
2252        // decides), random points, and a sparse box, in an orthorhombic,
2253        // a restricted, and a general cell; bins of one point and of
2254        // several, so both block sides run; k up to 20, past the bound
2255        // of the two-pass scan.
2256        let mut state = 0x853c_49e6_748f_ea9bu64;
2257        let mut next = || {
2258            state ^= state << 13;
2259            state ^= state >> 7;
2260            state ^= state << 17;
2261            state
2262        };
2263        let cells = [
2264            Cell::ortho(25.0, 25.0, 25.0).unwrap(),
2265            Cell::from_vectors(
2266                [25.0, 0.0, 0.0],
2267                [4.0, 24.0, 0.0],
2268                [-3.0, 2.0, 24.5],
2269                [0.0; 3],
2270            )
2271            .unwrap(),
2272            Cell::from_vectors(
2273                [24.0, 3.0, -2.0],
2274                [2.5, 23.5, 3.0],
2275                [-1.5, 2.0, 24.0],
2276                [0.5, 0.0, -0.5],
2277            )
2278            .unwrap(),
2279        ];
2280        for sim in &cells {
2281            let mut sets: Vec<Vec<[f64; 3]>> = Vec::new();
2282            let mut lattice = Vec::new();
2283            for iz in 0..10 {
2284                for iy in 0..10 {
2285                    for ix in 0..10 {
2286                        let mut s = [
2287                            (ix as f64 + 0.5) / 10.0,
2288                            (iy as f64 + 0.5) / 10.0,
2289                            (iz as f64 + 0.5) / 10.0,
2290                        ];
2291                        for v in s.iter_mut() {
2292                            let ulps = (next() % 7) as i64 - 3;
2293                            *v = f64::from_bits((v.to_bits() as i64 + ulps) as u64);
2294                        }
2295                        lattice.push(sim.cartesian(s));
2296                    }
2297                }
2298            }
2299            sets.push(lattice);
2300            let unit = |v: u64| (v >> 11) as f64 / (1u64 << 53) as f64;
2301            sets.push(
2302                (0..1500)
2303                    .map(|_| sim.cartesian([unit(next()), unit(next()), unit(next())]))
2304                    .collect(),
2305            );
2306            sets.push(
2307                (0..60)
2308                    .map(|_| sim.cartesian([unit(next()), unit(next()), unit(next())]))
2309                    .collect(),
2310            );
2311            for xyz in &sets {
2312                let mask: Vec<bool> = (0..xyz.len()).map(|t| t % 7 != 3).collect();
2313                for hint in [Some(2.4), Some(5.0)] {
2314                    for k in [1, 4, 8, 12, 20] {
2315                        for mask in [None, Some(mask.as_slice())] {
2316                            let blocked = knearest(xyz, sim, k, mask, hint).unwrap();
2317                            NO_BLOCKS.store(true, std::sync::atomic::Ordering::Relaxed);
2318                            let walked = knearest(xyz, sim, k, mask, hint).unwrap();
2319                            NO_BLOCKS.store(false, std::sync::atomic::Ordering::Relaxed);
2320                            for (i, (b, w)) in blocked.iter().zip(&walked).enumerate() {
2321                                assert_eq!(
2322                                    b.indices,
2323                                    w.indices,
2324                                    "n={} k={k} hint={hint:?} i={i}",
2325                                    xyz.len()
2326                                );
2327                                let bits = |r: &Neighbors| -> Vec<u64> {
2328                                    r.dist2.iter().map(|d| d.to_bits()).collect()
2329                                };
2330                                assert_eq!(
2331                                    bits(b),
2332                                    bits(w),
2333                                    "n={} k={k} hint={hint:?} i={i}",
2334                                    xyz.len()
2335                                );
2336                            }
2337                        }
2338                    }
2339                }
2340            }
2341        }
2342    }
2343
2344    fn row_bits(row: &Neighbors) -> (Vec<usize>, Vec<u64>) {
2345        (
2346            row.indices.clone(),
2347            row.dist2.iter().map(|d| d.to_bits()).collect(),
2348        )
2349    }
2350
2351    #[test]
2352    fn every_simd_path_matches_scalar_neighbours() {
2353        let mut state = 0x9e37_79b9_7f4a_7c15u64;
2354        let mut next = || {
2355            state ^= state << 13;
2356            state ^= state >> 7;
2357            state ^= state << 17;
2358            state
2359        };
2360        let unit = |v: u64| (v >> 11) as f64 / (1u64 << 53) as f64;
2361        let cells = [
2362            Cell::ortho(22.0, 19.0, 25.0).unwrap(),
2363            Cell::from_vectors(
2364                [22.0, 0.0, 0.0],
2365                [3.5, 20.0, 0.0],
2366                [-2.0, 1.5, 21.0],
2367                [0.0; 3],
2368            )
2369            .unwrap(),
2370            Cell::from_vectors(
2371                [20.0, 2.0, -1.0],
2372                [1.5, 19.0, 2.5],
2373                [-1.0, 1.5, 20.0],
2374                [0.25, 0.0, -0.25],
2375            )
2376            .unwrap(),
2377        ];
2378        for sim in &cells {
2379            let xyz: Vec<[f64; 3]> = (0..96)
2380                .map(|_| sim.cartesian([unit(next()), unit(next()), unit(next())]))
2381                .collect();
2382            let mask: Vec<bool> = (0..xyz.len()).map(|t| t % 5 != 1).collect();
2383            for k in [1usize, 4, 7, 8, 20] {
2384                for mask in [None, Some(mask.as_slice())] {
2385                    let scalar = {
2386                        let _guard = crate::simd::force(crate::simd::Path::Scalar);
2387                        knearest(&xyz, sim, k, mask, Some(3.0)).unwrap()
2388                    };
2389                    for path in crate::simd::paths_to_compare() {
2390                        let got = {
2391                            let _guard = crate::simd::force(path);
2392                            knearest(&xyz, sim, k, mask, Some(3.0)).unwrap()
2393                        };
2394                        for i in 0..xyz.len() {
2395                            assert_eq!(
2396                                row_bits(&got[i]),
2397                                row_bits(&scalar[i]),
2398                                "{path:?} k={k} i={i}"
2399                            );
2400                        }
2401                    }
2402                }
2403            }
2404        }
2405    }
2406
2407    #[test]
2408    fn scan_paths_match_scalar_bits() {
2409        let mut state = 0xc2b2_ae3d_27d4_eb4fu64;
2410        let mut next = || {
2411            state ^= state << 13;
2412            state ^= state >> 7;
2413            state ^= state << 17;
2414            state
2415        };
2416        let unit = |v: u64| (v >> 11) as f64 * (1.0 / (1u64 << 53) as f64);
2417        for &m in &[1usize, 2, 3, 4, 5, 8, 15, 32] {
2418            let mut cand = Candidates::default();
2419            for t in 0..m {
2420                cand.x.push(unit(next()) * 20.0);
2421                cand.y.push(unit(next()) * 20.0);
2422                cand.z.push(unit(next()) * 20.0);
2423                cand.id.push(t as u64);
2424            }
2425            let pi = [
2426                unit(next()) * 20.0,
2427                unit(next()) * 20.0,
2428                unit(next()) * 20.0,
2429            ];
2430            let source = m / 2;
2431            for k in [1usize, 2, 4, 8, 20] {
2432                let scalar = scan_row(crate::simd::Path::Scalar, &mut cand, pi, source, k);
2433                for path in crate::simd::paths_to_compare() {
2434                    let got = scan_row(path, &mut cand, pi, source, k);
2435                    assert_eq!(got, scalar, "{path:?} m={m} k={k}");
2436                }
2437            }
2438        }
2439    }
2440
2441    fn scan_row(
2442        path: crate::simd::Path,
2443        cand: &mut Candidates,
2444        pi: [f64; 3],
2445        i: usize,
2446        k: usize,
2447    ) -> (Vec<i32>, Vec<u64>) {
2448        let mut heap = KHeap::new(k);
2449        scan_at(path, cand, pi, i, &mut heap);
2450        let mut nn = vec![-1i32; k];
2451        let mut d2 = vec![f64::NAN; k];
2452        heap.write_sorted(&mut nn, Some(&mut d2));
2453        (nn, d2.iter().map(|v| v.to_bits()).collect())
2454    }
2455
2456    /// Fold columns and neighbour rows stay bitwise and ordering identical
2457    /// at 1 thread, 2 threads, and every core, on every SIMD path.
2458    #[cfg(feature = "parallel")]
2459    #[test]
2460    fn rank_invariant_across_threads_and_simd_paths() {
2461        let n_threads = std::thread::available_parallelism()
2462            .map(|n| n.get())
2463            .unwrap_or(1);
2464        let mut counts = vec![1usize, 2, 3, 8, n_threads];
2465        counts.sort_unstable();
2466        counts.dedup();
2467        let (mut xyz, cell) = ortho_lattice(21);
2468        xyz[0][0] = -0.0;
2469        xyz[1][1] = f64::from_bits(xyz[1][1].to_bits() + 1);
2470        xyz[2][2] = 1.0e-320;
2471        let reference = rank_snapshot(1, crate::simd::Path::Scalar, &xyz, &cell);
2472        for &threads in &counts {
2473            for path in crate::simd::paths_to_compare() {
2474                let got = rank_snapshot(threads, path, &xyz, &cell);
2475                let tag = format!("threads={threads} path={path:?}");
2476                assert_eq!(got.frac.len(), reference.frac.len(), "{tag}");
2477                for i in 0..got.frac.len() {
2478                    assert_eq!(got.frac[i], reference.frac[i], "{tag} frac {i}");
2479                    assert_eq!(got.folded[i], reference.folded[i], "{tag} folded {i}");
2480                }
2481                assert_eq!(got.offsets, reference.offsets, "{tag} offsets");
2482                assert_eq!(got.occupants, reference.occupants, "{tag} occupants");
2483                assert_eq!(got.nn.len(), reference.nn.len(), "{tag}");
2484                for i in 0..got.nn.len() {
2485                    assert_eq!(got.nn[i], reference.nn[i], "{tag} nn {i}");
2486                    assert_eq!(got.d2[i], reference.d2[i], "{tag} d2 {i}");
2487                }
2488                assert_eq!(got.pairs, reference.pairs, "{tag} pairs");
2489            }
2490        }
2491    }
2492
2493    #[cfg(feature = "parallel")]
2494    struct RankSnap {
2495        frac: Vec<[u64; 3]>,
2496        folded: Vec<[u64; 3]>,
2497        offsets: Vec<usize>,
2498        occupants: Vec<usize>,
2499        nn: Vec<Vec<usize>>,
2500        d2: Vec<Vec<u64>>,
2501        pairs: Vec<(usize, usize, [i32; 3], u64)>,
2502    }
2503
2504    #[cfg(feature = "parallel")]
2505    fn rank_snapshot(
2506        threads: usize,
2507        path: crate::simd::Path,
2508        xyz: &[[f64; 3]],
2509        cell: &Cell,
2510    ) -> RankSnap {
2511        let pool = rayon::ThreadPoolBuilder::new()
2512            .num_threads(threads)
2513            .build()
2514            .unwrap();
2515        pool.install(move || {
2516            let _guard = crate::simd::force(path);
2517            let mesh = Mesh::build(xyz, cell, None, 3.0).unwrap();
2518            let rows = knearest(xyz, cell, 4, None, Some(3.0)).unwrap();
2519            let pairs = crate::pairs_within(xyz, cell, 4.5, None, None, false).unwrap();
2520            let mut cols = crate::PairColumns::default();
2521            crate::pairs_within_columns(xyz, cell, 4.5, None, None, false, &mut cols).unwrap();
2522            let pair_rows: Vec<_> = pairs
2523                .iter()
2524                .map(|p| (p.i, p.j, p.shift, p.dist2.to_bits()))
2525                .collect();
2526            let col_rows: Vec<_> = (0..cols.len())
2527                .map(|t| {
2528                    (
2529                        cols.i[t] as usize,
2530                        cols.j[t] as usize,
2531                        cols.shift[t],
2532                        cols.dist2[t].to_bits(),
2533                    )
2534                })
2535                .collect();
2536            assert_eq!(pair_rows, col_rows, "columns differ from rows");
2537            let bits = |v: [f64; 3]| [v[0].to_bits(), v[1].to_bits(), v[2].to_bits()];
2538            RankSnap {
2539                frac: mesh.frac.iter().copied().map(bits).collect(),
2540                folded: mesh.folded.iter().copied().map(bits).collect(),
2541                offsets: mesh.offsets.clone(),
2542                occupants: mesh.occupants.clone(),
2543                nn: rows.iter().map(|r| r.indices.clone()).collect(),
2544                d2: rows
2545                    .iter()
2546                    .map(|r| r.dist2.iter().map(|d| d.to_bits()).collect())
2547                    .collect(),
2548                pairs: pair_rows,
2549            }
2550        })
2551    }
2552}
2553
2554/// The fused region against brute force and the rayon walk.
2555#[cfg(all(test, feature = "parallel", linkcell_openmp))]
2556mod fused_agree {
2557    use super::{knearest_brute, knearest_into_d2, FORCE_FUSED, FORCE_LEGACY};
2558    use crate::Cell;
2559
2560    fn lcg(state: &mut u64) -> u64 {
2561        *state ^= *state << 13;
2562        *state ^= *state >> 7;
2563        *state ^= *state << 17;
2564        *state
2565    }
2566
2567    fn unit(state: &mut u64) -> f64 {
2568        (lcg(state) >> 11) as f64 * (1.0 / (1u64 << 53) as f64)
2569    }
2570
2571    fn periodic(cell: &Cell, n: usize, seed: u64) -> Vec<[f64; 3]> {
2572        let mut state = seed;
2573        (0..n)
2574            .map(|_| cell.cartesian([unit(&mut state), unit(&mut state), unit(&mut state)]))
2575            .collect()
2576    }
2577
2578    /// A cloud in the middle of the box. Images are a full edge away.
2579    fn open_cloud(cell: &Cell, n: usize, seed: u64) -> Vec<[f64; 3]> {
2580        let mut state = seed;
2581        (0..n)
2582            .map(|_| {
2583                cell.cartesian([
2584                    0.40 + 0.20 * unit(&mut state),
2585                    0.40 + 0.20 * unit(&mut state),
2586                    0.40 + 0.20 * unit(&mut state),
2587                ])
2588            })
2589            .collect()
2590    }
2591
2592    fn buffers(xyz: &[[f64; 3]], cell: &Cell, k: usize, hint: Option<f64>) -> (Vec<i32>, Vec<u64>) {
2593        let mut nn = vec![7i32; xyz.len() * k];
2594        let mut d2 = vec![1.0; xyz.len() * k];
2595        knearest_into_d2(xyz, cell, k, None, hint, &mut nn, Some(&mut d2)).unwrap();
2596        (nn, d2.into_iter().map(|v| v.to_bits()).collect())
2597    }
2598
2599    fn assert_same(label: &str, got: &(Vec<i32>, Vec<u64>), want: &(Vec<i32>, Vec<u64>)) {
2600        assert_eq!(got.0, want.0, "{label} indices");
2601        assert_eq!(got.1, want.1, "{label} dist2 bits");
2602    }
2603
2604    fn with_fused<T>(body: impl FnOnce() -> T) -> T {
2605        FORCE_FUSED.with(|cell| cell.set(true));
2606        let out = body();
2607        FORCE_FUSED.with(|cell| cell.set(false));
2608        out
2609    }
2610
2611    fn with_legacy<T>(body: impl FnOnce() -> T) -> T {
2612        FORCE_LEGACY.with(|cell| cell.set(true));
2613        let out = body();
2614        FORCE_LEGACY.with(|cell| cell.set(false));
2615        out
2616    }
2617
2618    fn cells(span: f64) -> Vec<Cell> {
2619        vec![
2620            Cell::ortho(span, span * 0.9, span * 1.15).unwrap(),
2621            Cell::from_vectors(
2622                [span, 0.0, 0.0],
2623                [span * 0.15, span * 0.95, 0.0],
2624                [span * -0.05, span * 0.08, span * 1.05],
2625                [0.0; 3],
2626            )
2627            .unwrap(),
2628        ]
2629    }
2630
2631    #[test]
2632    fn fused_matches_brute_and_legacy_on_periodic_and_open_boxes() {
2633        let shapes = [
2634            (
2635                "periodic",
2636                periodic as fn(&Cell, usize, u64) -> Vec<[f64; 3]>,
2637            ),
2638            ("open", open_cloud),
2639        ];
2640        for (shape, build) in shapes {
2641            for cell in cells(36.0) {
2642                for &(n, k, seed, hint) in &[
2643                    (48usize, 1usize, 0x11u64, None),
2644                    (96, 4, 0x22, Some(2.5)),
2645                    (160, 17, 0x33, Some(4.0)),
2646                    (320, 4, 0x44, Some(3.0)),
2647                    (7, 10, 0x55, None),
2648                ] {
2649                    let mut xyz = build(&cell, n, seed);
2650                    // A point outside the primary cell still folds in.
2651                    if n > 3 {
2652                        xyz[1][0] += cell.a()[0];
2653                        xyz[2][1] -= cell.b()[1];
2654                    }
2655                    // Two coincident sites.
2656                    if n > 8 {
2657                        xyz[5] = xyz[4];
2658                    }
2659                    let label = format!("{shape} n={n} k={k} seed={seed} hint={hint:?}");
2660                    let fused = with_fused(|| buffers(&xyz, &cell, k, hint));
2661                    let legacy = with_legacy(|| buffers(&xyz, &cell, k, hint));
2662                    let brute = knearest_brute(&xyz, &cell, k, None).unwrap();
2663                    assert_same(&format!("{label} fused vs legacy"), &fused, &legacy);
2664                    let mut brute_nn = vec![-1i32; n * k];
2665                    let mut brute_d2 = vec![f64::NAN; n * k];
2666                    for (i, row) in brute.iter().enumerate() {
2667                        for (t, (&j, &d)) in row.indices.iter().zip(&row.dist2).enumerate() {
2668                            brute_nn[i * k + t] = j as i32;
2669                            brute_d2[i * k + t] = d;
2670                        }
2671                    }
2672                    assert_eq!(fused.0, brute_nn, "{label} fused vs brute indices");
2673                    for (i, (&bits, brute_d)) in fused.1.iter().zip(&brute_d2).enumerate() {
2674                        let got = f64::from_bits(bits);
2675                        let scale = 1.0 + got.abs().max(brute_d.abs());
2676                        assert!(
2677                            (got.is_nan() && brute_d.is_nan())
2678                                || (got - brute_d).abs() <= 1e-12 * scale,
2679                            "{label} fused vs brute dist2 [{i}]: {got} vs {brute_d}"
2680                        );
2681                    }
2682                }
2683            }
2684        }
2685    }
2686
2687    #[test]
2688    fn large_unmasked_query_uses_the_region_and_matches_legacy() {
2689        let cell = Cell::ortho(48.0, 47.0, 49.5).unwrap();
2690        let mut state = 0xabcdu64;
2691        let xyz: Vec<[f64; 3]> = (0..9_000)
2692            .map(|_| cell.cartesian([unit(&mut state), unit(&mut state), unit(&mut state)]))
2693            .collect();
2694        let fused = buffers(&xyz, &cell, 4, Some(3.0));
2695        let legacy = with_legacy(|| buffers(&xyz, &cell, 4, Some(3.0)));
2696        assert_same("n=9000", &fused, &legacy);
2697        assert!(
2698            super::knearest_team_threads() >= 1,
2699            "team {}",
2700            super::knearest_team_threads()
2701        );
2702    }
2703
2704    /// Every thread of this process as `(id, name)`. Linux reads
2705    /// `/proc/self/task`. macOS asks Mach for the thread ports and
2706    /// pthread for each name.
2707    #[cfg(target_os = "linux")]
2708    fn threads() -> Vec<(String, String)> {
2709        let Ok(dir) = std::fs::read_dir("/proc/self/task") else {
2710            return Vec::new();
2711        };
2712        dir.flatten()
2713            .map(|entry| {
2714                let comm = std::fs::read_to_string(entry.path().join("comm")).unwrap_or_default();
2715                (
2716                    entry.file_name().to_string_lossy().into_owned(),
2717                    comm.trim_end().to_string(),
2718                )
2719            })
2720            .collect()
2721    }
2722
2723    #[cfg(target_os = "macos")]
2724    fn threads() -> Vec<(String, String)> {
2725        use std::os::raw::{c_char, c_int, c_void};
2726        extern "C" {
2727            static mach_task_self_: u32;
2728            fn task_threads(task: u32, list: *mut *mut u32, count: *mut u32) -> c_int;
2729            fn mach_port_deallocate(task: u32, name: u32) -> c_int;
2730            fn vm_deallocate(task: u32, address: usize, size: usize) -> c_int;
2731            fn pthread_from_mach_thread_np(port: u32) -> *mut c_void;
2732            fn pthread_getname_np(thread: *mut c_void, name: *mut c_char, len: usize) -> c_int;
2733        }
2734        let task = unsafe { mach_task_self_ };
2735        let mut list: *mut u32 = std::ptr::null_mut();
2736        let mut count = 0u32;
2737        if unsafe { task_threads(task, &mut list, &mut count) } != 0 {
2738            return Vec::new();
2739        }
2740        let ports = unsafe { std::slice::from_raw_parts(list, count as usize) };
2741        let found = ports
2742            .iter()
2743            .map(|&port| {
2744                let thread = unsafe { pthread_from_mach_thread_np(port) };
2745                let mut buf = [0 as c_char; 64];
2746                let named = !thread.is_null()
2747                    && unsafe { pthread_getname_np(thread, buf.as_mut_ptr(), buf.len()) } == 0;
2748                let name = if named {
2749                    unsafe { std::ffi::CStr::from_ptr(buf.as_ptr()) }
2750                        .to_string_lossy()
2751                        .into_owned()
2752                } else {
2753                    String::new()
2754                };
2755                (port.to_string(), name)
2756            })
2757            .collect();
2758        for &port in ports {
2759            unsafe { mach_port_deallocate(task, port) };
2760        }
2761        unsafe {
2762            vm_deallocate(
2763                task,
2764                list as usize,
2765                count as usize * std::mem::size_of::<u32>(),
2766            )
2767        };
2768        found
2769    }
2770
2771    fn task_count() -> usize {
2772        threads().len()
2773    }
2774
2775    fn wait_tasks(want: usize) -> usize {
2776        let mut last = task_count();
2777        for _ in 0..100 {
2778            if last <= want {
2779                return last;
2780            }
2781            std::thread::sleep(std::time::Duration::from_millis(5));
2782            last = task_count();
2783        }
2784        last
2785    }
2786
2787    /// The name `src/knn_region.c` gives every worker of the team.
2788    const TEAM_NAME: &str = "linkcell-knn";
2789
2790    /// Workers of linkcell's k-nearest team. The caller, rayon's pool and
2791    /// any thread an OpenMP runtime keeps do not carry the name.
2792    fn team_workers() -> usize {
2793        threads()
2794            .iter()
2795            .filter(|(_, name)| name == TEAM_NAME)
2796            .count()
2797    }
2798
2799    fn wait_team_workers(want: usize) -> usize {
2800        let mut last = team_workers();
2801        for _ in 0..100 {
2802            if last == want {
2803                return last;
2804            }
2805            std::thread::sleep(std::time::Duration::from_millis(5));
2806            last = team_workers();
2807        }
2808        last
2809    }
2810
2811    /// The team is joined, so no worker is left and the process is back to
2812    /// `before` threads under libgomp and libomp alike.
2813    fn assert_threads_back(before: usize, label: &str) {
2814        let workers = wait_team_workers(0);
2815        assert_eq!(
2816            workers,
2817            0,
2818            "{label} left linkcell workers running\n{}",
2819            task_names()
2820        );
2821        let after = wait_tasks(before);
2822        assert_eq!(
2823            after,
2824            before,
2825            "{label} left threads: before {before} after {after}\n{}",
2826            task_names()
2827        );
2828    }
2829
2830    fn task_names() -> String {
2831        let mut names = String::new();
2832        for (id, name) in threads() {
2833            names.push_str(&id);
2834            names.push(':');
2835            names.push_str(&name);
2836            names.push('\n');
2837        }
2838        names
2839    }
2840
2841    /// Child process: the team follows `omp_set_num_threads`, and shutdown
2842    /// joins it. When `liblinkcell.so` is beside the build, also query
2843    /// through that image and `dlclose` it.
2844    #[test]
2845    fn team_follows_omp_set_num_threads_and_joins_on_shutdown() {
2846        if std::env::var_os("LC_TEAM_PROBE").is_none() {
2847            let exe = std::env::current_exe().unwrap();
2848            let out = std::process::Command::new(&exe)
2849                .arg(
2850                    "knearest::fused_agree::team_follows_omp_set_num_threads_and_joins_on_shutdown",
2851                )
2852                .args(["--exact", "--test-threads", "1", "--nocapture"])
2853                .env("LC_TEAM_PROBE", "1")
2854                .output()
2855                .unwrap();
2856            assert!(
2857                out.status.success(),
2858                "probe status {:?}\n{}{}",
2859                out.status,
2860                String::from_utf8_lossy(&out.stdout),
2861                String::from_utf8_lossy(&out.stderr)
2862            );
2863            return;
2864        }
2865        extern "C" {
2866            fn omp_set_num_threads(n: i32);
2867            fn omp_get_max_threads() -> i32;
2868        }
2869        let before = task_count();
2870        assert_eq!(team_workers(), 0, "linkcell workers before the first query");
2871        let saved = unsafe { omp_get_max_threads() }.max(1);
2872        unsafe { omp_set_num_threads(2) };
2873        let cell = Cell::ortho(30.0, 30.0, 30.0).unwrap();
2874        let xyz = periodic(&cell, 64, 9);
2875        let _ = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
2876        assert_eq!(super::knearest_team_threads(), 2);
2877        let mid = task_count();
2878        assert!(
2879            mid >= before + 2,
2880            "team not running: before {before} mid {mid}"
2881        );
2882        assert_eq!(team_workers(), 2, "team of two not named\n{}", task_names());
2883        super::shutdown_knearest_team();
2884        assert_threads_back(before, "shutdown");
2885        unsafe { omp_set_num_threads(saved) };
2886        let _ = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
2887        assert_eq!(super::knearest_team_threads(), saved as usize);
2888        assert_eq!(
2889            team_workers(),
2890            saved as usize,
2891            "team of {saved} not named\n{}",
2892            task_names()
2893        );
2894        super::shutdown_knearest_team();
2895        assert_threads_back(before, "second shutdown");
2896
2897        let so = std::env::current_exe().ok().and_then(|mut exe| {
2898            for _ in 0..6 {
2899                exe.pop();
2900                let candidate = exe.join("liblinkcell.so");
2901                if candidate.is_file() {
2902                    return Some(candidate);
2903                }
2904            }
2905            None
2906        });
2907        if let Some(so) = so {
2908            unload_cdylib(&so, before, saved as usize);
2909        }
2910    }
2911
2912    /// Child process: after `lc_set_threads(1)` a C API search adds no
2913    /// thread. Asked from outside a pool, rayon would build its global
2914    /// pool at the cpu count, and the fused region would start its team.
2915    #[cfg(feature = "capi")]
2916    #[test]
2917    fn one_thread_capi_search_starts_no_thread() {
2918        if std::env::var_os("LC_ONE_THREAD_PROBE").is_none() {
2919            let exe = std::env::current_exe().unwrap();
2920            let out = std::process::Command::new(&exe)
2921                .arg("knearest::fused_agree::one_thread_capi_search_starts_no_thread")
2922                .args(["--exact", "--test-threads", "1", "--nocapture"])
2923                .env("LC_ONE_THREAD_PROBE", "1")
2924                .env_remove("RAYON_NUM_THREADS")
2925                .output()
2926                .unwrap();
2927            assert!(
2928                out.status.success(),
2929                "probe status {:?}\n{}{}",
2930                out.status,
2931                String::from_utf8_lossy(&out.stdout),
2932                String::from_utf8_lossy(&out.stderr)
2933            );
2934            return;
2935        }
2936        let before = task_count();
2937        crate::capi::lc_set_threads(1);
2938        let n = 8192usize;
2939        let xyz: Vec<f64> = (0..n)
2940            .flat_map(|i| [(i % 20) as f64, ((i / 20) % 20) as f64, (i / 400) as f64])
2941            .collect();
2942        let cell = [
2943            40.0, 0.0, 0.0, 0.0, 40.0, 0.0, 0.0, 0.0, 40.0, 0.0, 0.0, 0.0,
2944        ];
2945        let mut out = vec![-1i32; n * 2];
2946        let rc = unsafe {
2947            crate::capi::lc_knearest(
2948                xyz.as_ptr(),
2949                n,
2950                cell.as_ptr().cast(),
2951                2,
2952                std::ptr::null(),
2953                3.0,
2954                out.as_mut_ptr(),
2955            )
2956        };
2957        assert_eq!(rc, 0, "one-thread query");
2958        assert!(
2959            out.iter().all(|&j| j >= 0),
2960            "one-thread query left a slot empty"
2961        );
2962        let same = |label: &str| {
2963            assert_eq!(
2964                task_count(),
2965                before,
2966                "a one-thread {label} started threads\n{}",
2967                task_names()
2968            );
2969        };
2970        same("k-nearest search");
2971
2972        let simbox: *const crate::capi::lc_cell = cell.as_ptr().cast();
2973        let mut rows = 0usize;
2974        let rc = unsafe {
2975            crate::capi::lc_pairs_within(
2976                xyz.as_ptr(),
2977                n,
2978                simbox,
2979                1.5,
2980                std::ptr::null(),
2981                0.0,
2982                1,
2983                std::ptr::null_mut(),
2984                std::ptr::null_mut(),
2985                std::ptr::null_mut(),
2986                std::ptr::null_mut(),
2987                0,
2988                &mut rows,
2989            )
2990        };
2991        assert_eq!(rc, 0, "one-thread pair count");
2992        assert!(rows > 0, "one-thread pair count found no pair");
2993        same("pair count");
2994        let mut pi = vec![0i32; rows];
2995        let mut pj = vec![0i32; rows];
2996        let mut shift = vec![0i32; rows * 3];
2997        let mut d2 = vec![0.0f64; rows];
2998        let rc = unsafe {
2999            crate::capi::lc_pairs_within(
3000                xyz.as_ptr(),
3001                n,
3002                simbox,
3003                1.5,
3004                std::ptr::null(),
3005                0.0,
3006                1,
3007                pi.as_mut_ptr(),
3008                pj.as_mut_ptr(),
3009                shift.as_mut_ptr(),
3010                d2.as_mut_ptr(),
3011                rows,
3012                &mut rows,
3013            )
3014        };
3015        assert_eq!(rc, 0, "one-thread pair fill");
3016        same("pair fill");
3017
3018        let mut found = vec![crate::capi::lc_pair::default(); rows];
3019        let rc = unsafe {
3020            crate::capi::lc_pairs_within_rows(
3021                xyz.as_ptr(),
3022                n,
3023                simbox,
3024                1.5,
3025                std::ptr::null(),
3026                0.0,
3027                1,
3028                found.as_mut_ptr(),
3029                rows,
3030                &mut rows,
3031            )
3032        };
3033        assert_eq!(rc, 0, "one-thread pair rows");
3034        same("pair row fill");
3035
3036        let pbc = [1, 1, 0];
3037        let mut count = 0usize;
3038        let rc = unsafe {
3039            crate::capi::lc_pairs_within_pbc(
3040                xyz.as_ptr(),
3041                n,
3042                simbox,
3043                pbc.as_ptr(),
3044                1.5,
3045                std::ptr::null(),
3046                0.0,
3047                1,
3048                0,
3049                0,
3050                std::ptr::null_mut(),
3051                0,
3052                &mut count,
3053            )
3054        };
3055        assert_eq!(rc, 0, "one-thread mixed pair count");
3056        same("mixed-boundary pair count");
3057        let rc = unsafe {
3058            crate::capi::lc_pairs_open(
3059                xyz.as_ptr(),
3060                n,
3061                1.5,
3062                0.0,
3063                std::ptr::null_mut(),
3064                0,
3065                &mut count,
3066            )
3067        };
3068        assert_eq!(rc, 0, "one-thread open pair count");
3069        same("open pair count");
3070
3071        let mut ncell = 0usize;
3072        let rc = unsafe {
3073            crate::capi::lc_cell_grid(
3074                xyz.as_ptr(),
3075                n,
3076                simbox,
3077                1.5,
3078                std::ptr::null(),
3079                0.0,
3080                std::ptr::null_mut(),
3081                std::ptr::null_mut(),
3082                std::ptr::null_mut(),
3083                0,
3084                &mut ncell,
3085            )
3086        };
3087        assert_eq!(rc, 0, "one-thread cell grid");
3088        same("cell grid");
3089    }
3090
3091    fn unload_cdylib(so: &std::path::Path, before: usize, team: usize) {
3092        use std::os::raw::{c_char, c_int, c_void};
3093        extern "C" {
3094            fn dlopen(filename: *const c_char, flags: c_int) -> *mut c_void;
3095            fn dlsym(handle: *mut c_void, symbol: *const c_char) -> *mut c_void;
3096            fn dlclose(handle: *mut c_void) -> c_int;
3097        }
3098        const RTLD_NOW: c_int = 2;
3099        let path = std::ffi::CString::new(so.to_str().unwrap()).unwrap();
3100        let handle = unsafe { dlopen(path.as_ptr(), RTLD_NOW) };
3101        assert!(!handle.is_null(), "dlopen {}", so.display());
3102        let name = std::ffi::CString::new("lc_knearest").unwrap();
3103        let sym = unsafe { dlsym(handle, name.as_ptr()) };
3104        assert!(!sym.is_null(), "dlsym lc_knearest");
3105        type Knn = unsafe extern "C" fn(
3106            *const f64,
3107            usize,
3108            *const f64,
3109            usize,
3110            *const c_int,
3111            f64,
3112            *mut c_int,
3113        ) -> c_int;
3114        let knearest: Knn = unsafe { std::mem::transmute(sym) };
3115        let n = 8192usize;
3116        let mut xyz = vec![0.0f64; n * 3];
3117        for i in 0..n {
3118            xyz[i * 3] = (i % 20) as f64;
3119            xyz[i * 3 + 1] = ((i / 20) % 20) as f64;
3120            xyz[i * 3 + 2] = (i / 400) as f64;
3121        }
3122        let cell = [
3123            40.0, 0.0, 0.0, 0.0, 40.0, 0.0, 0.0, 0.0, 40.0, 0.0, 0.0, 0.0,
3124        ];
3125        let mut out = vec![-1i32; n * 2];
3126        let rc = unsafe {
3127            knearest(
3128                xyz.as_ptr(),
3129                n,
3130                cell.as_ptr(),
3131                2,
3132                std::ptr::null(),
3133                3.0,
3134                out.as_mut_ptr(),
3135            )
3136        };
3137        assert_eq!(rc, 0, "cdylib query");
3138        assert_eq!(
3139            team_workers(),
3140            team,
3141            "cdylib team of {team} did not start\n{}",
3142            task_names()
3143        );
3144        let stop_name = std::ffi::CString::new("lc_knn_shutdown").unwrap();
3145        let stop_sym = unsafe { dlsym(handle, stop_name.as_ptr()) };
3146        assert!(!stop_sym.is_null(), "dlsym lc_knn_shutdown");
3147        let stop: unsafe extern "C" fn() = unsafe { std::mem::transmute(stop_sym) };
3148        unsafe { stop() };
3149        assert_threads_back(before, "cdylib shutdown");
3150        let closed = unsafe { dlclose(handle) };
3151        assert_eq!(closed, 0, "dlclose");
3152        assert_threads_back(before, "dlclose");
3153    }
3154
3155    /// Guard size of worker `slot`, or 0 when that worker is not up.
3156    fn team_guard(slot: i32) -> usize {
3157        extern "C" {
3158            fn lc_knn_team_guard(slot: i32) -> usize;
3159        }
3160        unsafe { lc_knn_team_guard(slot) }
3161    }
3162
3163    /// The stack size of each worker of the standing team, in slot order,
3164    /// as the C library reports it for that thread.
3165    fn team_stacks() -> Vec<usize> {
3166        extern "C" {
3167            fn lc_knn_team_stack(slot: i32) -> usize;
3168        }
3169        (0..)
3170            .map(|slot| unsafe { lc_knn_team_stack(slot) })
3171            .take_while(|&size| size != 0)
3172            .collect()
3173    }
3174
3175    /// Child processes: `OMP_THREAD_LIMIT` caps the team below what
3176    /// `omp_set_num_threads` asks for, `OMP_STACKSIZE` sizes the worker
3177    /// stacks, a team of one is the caller with no worker, and
3178    /// `OMP_DYNAMIC` trims the team by the load average as libgomp does.
3179    #[test]
3180    fn team_honours_thread_limit_stacksize_and_dynamic() {
3181        let Some(mode) = std::env::var_os("LC_LIMIT_PROBE") else {
3182            let exe = std::env::current_exe().unwrap();
3183            for (mode, var, value) in [
3184                ("2", "OMP_THREAD_LIMIT", "2"),
3185                ("1", "OMP_THREAD_LIMIT", "1"),
3186                ("dyn", "OMP_DYNAMIC", "true"),
3187            ] {
3188                let out = std::process::Command::new(&exe)
3189                    .arg("knearest::fused_agree::team_honours_thread_limit_stacksize_and_dynamic")
3190                    .args(["--exact", "--test-threads", "1", "--nocapture"])
3191                    .env_remove("OMP_THREAD_LIMIT")
3192                    .env_remove("OMP_DYNAMIC")
3193                    .env("OMP_STACKSIZE", " 12m ")
3194                    .env(var, value)
3195                    .env("LC_LIMIT_PROBE", mode)
3196                    .output()
3197                    .unwrap();
3198                assert!(
3199                    out.status.success(),
3200                    "probe {mode} status {:?}\n{}{}",
3201                    out.status,
3202                    String::from_utf8_lossy(&out.stdout),
3203                    String::from_utf8_lossy(&out.stderr)
3204                );
3205            }
3206            return;
3207        };
3208        extern "C" {
3209            fn omp_set_num_threads(n: i32);
3210            fn omp_get_thread_limit() -> i32;
3211            fn omp_get_num_procs() -> i32;
3212            fn getloadavg(loadavg: *mut f64, nelem: i32) -> i32;
3213        }
3214        let dynamic = || {
3215            let mut load = [0.0f64; 3];
3216            let busy = if unsafe { getloadavg(load.as_mut_ptr(), 3) } == 3 {
3217                (load[2] + 0.1) as i32
3218            } else {
3219                0
3220            };
3221            let procs = unsafe { omp_get_num_procs() }.min(4);
3222            if busy >= procs {
3223                1
3224            } else {
3225                (procs - busy) as usize
3226            }
3227        };
3228        let stack = 12usize << 20;
3229        let cell = Cell::ortho(30.0, 30.0, 30.0).unwrap();
3230        let xyz = periodic(&cell, 64, 9);
3231        // Another thread holds a 12 MiB stack through the query. No thread
3232        // exits before it, so no cached stack can stand in for a worker's.
3233        let (release, held) = std::sync::mpsc::channel::<()>();
3234        let holder = std::thread::Builder::new()
3235            .stack_size(stack)
3236            .spawn(move || {
3237                let _ = held.recv();
3238            })
3239            .unwrap();
3240        // A team of one warms everything else up and leaves no worker
3241        // stack in glibc's cache of joined threads.
3242        unsafe { omp_set_num_threads(1) };
3243        let _ = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
3244        assert_eq!(super::knearest_team_threads(), 1);
3245        unsafe { omp_set_num_threads(4) };
3246        let before = task_count();
3247        let expect = match mode.to_str() {
3248            Some("2") => vec![2],
3249            Some("1") => vec![1],
3250            _ => vec![dynamic()],
3251        };
3252        assert!(
3253            mode != "dyn" || expect[0] <= 4,
3254            "dynamic size above nthreads-var"
3255        );
3256        let _ = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
3257        let team = super::knearest_team_threads();
3258        if mode == "dyn" {
3259            assert!(
3260                team == expect[0] || team == dynamic(),
3261                "OMP_DYNAMIC team {team}, load-average size {expect:?}"
3262            );
3263        } else {
3264            assert_eq!(unsafe { omp_get_thread_limit() }, expect[0] as i32);
3265            assert_eq!(team, expect[0], "OMP_THREAD_LIMIT={}", expect[0]);
3266        }
3267        let workers = if team > 1 { team } else { 0 };
3268        let mid = task_count();
3269        assert_eq!(
3270            mid,
3271            before + workers,
3272            "team {team}: before {before} mid {mid}\n{}",
3273            task_names()
3274        );
3275        assert_eq!(
3276            team_stacks(),
3277            vec![stack; workers],
3278            "OMP_STACKSIZE=12m stacks for a team of {team}"
3279        );
3280        for slot in 0..workers {
3281            let guard = team_guard(slot as i32);
3282            assert!(guard > 0, "worker {slot} guard size {guard}");
3283        }
3284        super::shutdown_knearest_team();
3285        let after = wait_tasks(before);
3286        assert_eq!(after, before, "shutdown left threads\n{}", task_names());
3287        assert_eq!(team_stacks(), Vec::<usize>::new(), "stacks after shutdown");
3288        assert_eq!(team_guard(0), 0, "guard after shutdown");
3289        drop(release);
3290        holder.join().unwrap();
3291    }
3292
3293    /// `OMP_STACKSIZE=1k` is below `PTHREAD_STACK_MIN`, and the mid size is
3294    /// one page above it, still below the stack floor. Both run the workers
3295    /// on the floor and warn once. `2^63` bytes is larger than the user
3296    /// address space. `pthread_attr_setstacksize` accepts it and
3297    /// `pthread_create` fails, so the query stays on the caller, the
3298    /// process warns once, and the next query tries again.
3299    #[test]
3300    fn small_stack_is_raised_and_a_refused_stack_stays_on_the_caller() {
3301        extern "C" {
3302            fn omp_set_num_threads(n: i32);
3303            fn omp_set_dynamic(dynamic_threads: i32);
3304            fn lc_knn_pthread_stack_min() -> usize;
3305            fn lc_knn_stack_floor() -> usize;
3306            fn lc_knn_stack_starts() -> usize;
3307        }
3308        let Some(mode) = std::env::var_os("LC_STACK_PROBE") else {
3309            let exe = std::env::current_exe().unwrap();
3310            let min = unsafe { lc_knn_pthread_stack_min() };
3311            let floor = unsafe { lc_knn_stack_floor() };
3312            let mut probes = vec![("small", "1k".to_string())];
3313            // One page above the minimum: pthread accepts it, and it sits in
3314            // the range where the fold frame can reach the guard.
3315            let mid = min + 4096;
3316            if mid < floor {
3317                probes.push(("mid", format!("{mid}b")));
3318            }
3319            // 2^63 bytes. Larger than a 57-bit virtual address space, so
3320            // the mapping cannot succeed under any overcommit setting.
3321            // glibc's pthread_attr_setstacksize accepts it.
3322            probes.push(("huge", "9223372036854775808b".to_string()));
3323            for (mode, stack) in probes {
3324                let out = std::process::Command::new(&exe)
3325                    .arg(
3326                        "knearest::fused_agree::small_stack_is_raised_and_a_refused_stack_stays_on_the_caller",
3327                    )
3328                    .args(["--exact", "--test-threads", "1", "--nocapture"])
3329                    .env_remove("OMP_THREAD_LIMIT")
3330                    .env_remove("OMP_DYNAMIC")
3331                    .env_remove("GOMP_STACKSIZE")
3332                    .env("OMP_DYNAMIC", "false")
3333                    .env("OMP_STACKSIZE", &stack)
3334                    .env("LC_STACK_PROBE", mode)
3335                    .output()
3336                    .unwrap();
3337                let err = String::from_utf8_lossy(&out.stderr);
3338                assert!(
3339                    out.status.success(),
3340                    "probe {mode} status {:?}\n{}{err}",
3341                    out.status,
3342                    String::from_utf8_lossy(&out.stdout)
3343                );
3344                let raised = err.matches("below the worker stack floor").count();
3345                let refused = err.matches("was refused").count();
3346                let create_failed = err.matches("could not start a worker").count();
3347                if mode != "huge" {
3348                    assert_eq!(raised, 1, "{err}");
3349                    assert_eq!(refused, 0, "{err}");
3350                    assert_eq!(create_failed, 0, "{err}");
3351                } else {
3352                    assert_eq!(create_failed, 1, "{err}");
3353                    assert_eq!(refused, 0, "{err}");
3354                    assert_eq!(raised, 0, "{err}");
3355                }
3356            }
3357            return;
3358        };
3359        let cell = Cell::ortho(30.0, 30.0, 30.0).unwrap();
3360        let xyz = periodic(&cell, 64, 9);
3361        unsafe {
3362            omp_set_dynamic(0);
3363            omp_set_num_threads(1);
3364        }
3365        let reference = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
3366        assert_eq!(super::knearest_team_threads(), 1);
3367        unsafe { omp_set_num_threads(4) };
3368        let first = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
3369        let second = with_fused(|| buffers(&xyz, &cell, 4, Some(3.0)));
3370        assert_same("first query", &first, &reference);
3371        assert_same("second query", &second, &reference);
3372        let team = super::knearest_team_threads();
3373        let starts = unsafe { lc_knn_stack_starts() };
3374        if mode != "huge" {
3375            assert!(team > 1, "raised stack started no team");
3376            let min = unsafe { lc_knn_pthread_stack_min() };
3377            let floor = unsafe { lc_knn_stack_floor() };
3378            assert!(
3379                floor >= min,
3380                "floor {floor} is below PTHREAD_STACK_MIN {min}"
3381            );
3382            let stacks = team_stacks();
3383            assert_eq!(stacks.len(), team, "raised stack workers");
3384            for (slot, size) in stacks.iter().copied().enumerate() {
3385                assert!(
3386                    size >= min,
3387                    "worker {slot} stack {size} is below PTHREAD_STACK_MIN {min}"
3388                );
3389                assert_eq!(size, floor, "worker {slot} stack {size}");
3390            }
3391            assert_eq!(starts, 1, "raised stack was started twice");
3392        } else {
3393            assert_eq!(team, 1, "huge stack started a team");
3394            assert!(team_stacks().is_empty(), "huge stack left workers");
3395            assert_eq!(starts, 2, "pthread_create failure was remembered");
3396        }
3397        super::shutdown_knearest_team();
3398    }
3399}
3400
3401#[cfg(test)]
3402mod graph_tests {
3403    use super::*;
3404
3405    /// The graph from the nominations one slot at a time: an accepted slot
3406    /// `(i, t) -> j` appends `j` to row `i` and `i` to row `j`. Mutual rows
3407    /// are the lower partners ascending, then the higher ones in row order.
3408    #[cfg(feature = "parallel")]
3409    fn reference(nom: &[i32], n: usize, k: usize, mutual: bool) -> (Vec<i32>, Vec<i32>) {
3410        let listed = |j: usize, i: usize| nom[j * k..(j + 1) * k].contains(&(i as i32));
3411        let mut rows = vec![Vec::new(); n];
3412        if mutual {
3413            for (i, row) in rows.iter_mut().enumerate() {
3414                let keep: Vec<i32> = nom[i * k..(i + 1) * k]
3415                    .iter()
3416                    .copied()
3417                    .filter(|&j| j >= 0 && (j as usize) != i && listed(j as usize, i))
3418                    .collect();
3419                let mut low: Vec<i32> =
3420                    keep.iter().copied().filter(|&j| (j as usize) < i).collect();
3421                low.sort_unstable();
3422                row.extend(low);
3423                row.extend(keep.iter().copied().filter(|&j| (j as usize) > i));
3424            }
3425        } else {
3426            for i in 0..n {
3427                for t in 0..k {
3428                    let j = nom[i * k + t];
3429                    if j < 0 || j as usize == i {
3430                        continue;
3431                    }
3432                    let j = j as usize;
3433                    if i < j || !listed(j, i) {
3434                        rows[i].push(j as i32);
3435                        rows[j].push(i as i32);
3436                    }
3437                }
3438            }
3439        }
3440        let mut offsets = vec![0i32];
3441        let mut cols = Vec::new();
3442        for row in rows {
3443            cols.extend(row);
3444            offsets.push(cols.len() as i32);
3445        }
3446        (offsets, cols)
3447    }
3448
3449    #[cfg(feature = "parallel")]
3450    fn points(n: usize, cell: &Cell, state: &mut u64) -> Vec<[f64; 3]> {
3451        let mut next = || {
3452            *state ^= *state << 13;
3453            *state ^= *state >> 7;
3454            *state ^= *state << 17;
3455            (*state >> 11) as f64 / (1u64 << 53) as f64
3456        };
3457        (0..n)
3458            .map(|_| {
3459                let s = [next(), next(), next()];
3460                let (a, b, c) = (cell.a(), cell.b(), cell.c());
3461                std::array::from_fn(|x| s[0] * a[x] + s[1] * b[x] + s[2] * c[x])
3462            })
3463            .collect()
3464    }
3465
3466    #[cfg(feature = "parallel")]
3467    fn in_pool<R: Send>(width: usize, f: impl FnOnce() -> R + Send) -> R {
3468        rayon::ThreadPoolBuilder::new()
3469            .num_threads(width)
3470            .build()
3471            .unwrap()
3472            .install(f)
3473    }
3474
3475    /// Every width, cell shape, mask, and k gives the graph the
3476    /// nominations define, row for row.
3477    #[cfg(feature = "parallel")]
3478    #[test]
3479    fn csr_rows_follow_the_nominations_at_every_width() {
3480        let mut state = 0x2545_f491_4f6c_dd1du64;
3481        let cells = [
3482            Cell::ortho(41.0, 37.0, 45.0).unwrap(),
3483            Cell::from_vectors(
3484                [40.0, 0.0, 0.0],
3485                [6.0, 38.0, 0.0],
3486                [-5.0, 4.0, 42.0],
3487                [0.0; 3],
3488            )
3489            .unwrap(),
3490            Cell::from_vectors(
3491                [30.0, 9.0, 2.0],
3492                [-4.0, 33.0, 7.0],
3493                [3.0, -6.0, 36.0],
3494                [1.0, 2.0, 3.0],
3495            )
3496            .unwrap(),
3497        ];
3498        for cell in &cells {
3499            let xyz = points(9_000, cell, &mut state);
3500            let mask: Vec<bool> = (0..xyz.len()).map(|i| i % 7 != 3).collect();
3501            for k in [1usize, 4, 12] {
3502                for masked in [false, true] {
3503                    let m = masked.then_some(&mask[..]);
3504                    let mut nom = vec![0i32; xyz.len() * k];
3505                    knearest_into(&xyz, cell, k, m, Some(3.0), &mut nom).unwrap();
3506                    for mutual in [false, true] {
3507                        let want = reference(&nom, xyz.len(), k, mutual);
3508                        for width in [1usize, 2, 3, 8] {
3509                            let got = in_pool(width, || {
3510                                knearest_csr(&xyz, cell, k, m, Some(3.0), mutual).unwrap()
3511                            });
3512                            assert!(
3513                                got == want,
3514                                "k={k} masked={masked} mutual={mutual} width={width}"
3515                            );
3516                        }
3517                    }
3518                }
3519            }
3520        }
3521    }
3522
3523    /// One or no active point, and a box of two, leave every row empty
3524    /// or give the single pair.
3525    #[test]
3526    fn csr_of_tiny_inputs() {
3527        let cell = Cell::ortho(10.0, 10.0, 10.0).unwrap();
3528        let one = [[1.0, 1.0, 1.0]];
3529        assert_eq!(
3530            knearest_csr(&one, &cell, 3, None, None, false).unwrap(),
3531            (vec![0, 0], vec![])
3532        );
3533        let two = [[1.0, 1.0, 1.0], [2.0, 1.0, 1.0]];
3534        let off = [false, true];
3535        assert_eq!(
3536            knearest_csr(&two, &cell, 3, Some(&off), None, true).unwrap(),
3537            (vec![0, 0, 0], vec![])
3538        );
3539        assert_eq!(
3540            knearest_csr(&two, &cell, 3, None, None, false).unwrap(),
3541            (vec![0, 1, 2], vec![1, 0])
3542        );
3543    }
3544}