1use 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
34fn 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#[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 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 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 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 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 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 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#[derive(Clone, Debug, Default, PartialEq)]
253pub struct Neighbors {
254 pub indices: Vec<usize>,
256 pub dist2: Vec<f64>,
258}
259
260pub 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
293pub 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#[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#[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
419const GRAPH_ROWS: usize = 2048;
421
422#[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#[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#[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 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 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 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 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 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: °ree,
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
691pub 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
722pub 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
784static TEAM: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
786
787static PIN_LEAST_LOADED: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
789
790pub fn pin_knearest_to_least_loaded(enabled: bool) {
798 PIN_LEAST_LOADED.store(enabled, std::sync::atomic::Ordering::Relaxed);
799}
800
801pub fn knearest_team_threads() -> usize {
811 TEAM.load(std::sync::atomic::Ordering::Relaxed)
812}
813
814pub fn shutdown_knearest_team() {
820 #[cfg(all(feature = "parallel", linkcell_openmp))]
821 unsafe {
822 lc_knn_shutdown_impl();
823 }
824}
825
826#[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#[derive(Default)]
871pub(crate) struct Scratch {
872 cand: Candidates,
873 heap: Option<KHeap>,
874 pub(crate) rows: Vec<i32>,
876}
877
878fn 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 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 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 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 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#[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 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#[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
1178fn 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#[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 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#[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
1276fn 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#[cfg(test)]
1291static NO_BLOCKS: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
1292
1293#[derive(Default)]
1296struct Candidates {
1297 x: Vec<f64>,
1298 y: Vec<f64>,
1299 z: Vec<f64>,
1300 id: Vec<u64>,
1301 #[cfg_attr(
1303 not(any(target_arch = "x86_64", target_arch = "aarch64")),
1304 allow(dead_code)
1305 )]
1306 d2: Vec<f64>,
1307}
1308
1309#[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#[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 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 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#[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 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 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
1548fn 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
1560fn 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
1578fn 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 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 unsafe { scan_avx2(cand, pi, i, heap) };
1602 }
1603 #[cfg(target_arch = "aarch64")]
1604 crate::simd::Path::Neon => {
1605 unsafe { scan_neon(cand, pi, i, heap) };
1608 }
1609 _ => scan(cand, pi, i, heap),
1610 }
1611}
1612
1613fn 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#[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 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#[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#[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#[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 #[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#[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 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#[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 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 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
2084pub 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 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 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 #[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#[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 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 if n > 3 {
2652 xyz[1][0] += cell.a()[0];
2653 xyz[2][1] -= cell.b()[1];
2654 }
2655 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 #[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 const TEAM_NAME: &str = "linkcell-knn";
2789
2790 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 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 #[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 #[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 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 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 #[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 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 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 #[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 let mid = min + 4096;
3316 if mid < floor {
3317 probes.push(("mid", format!("{mid}b")));
3318 }
3319 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 #[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 #[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 #[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}