1use crate::bins::{self, axis_gap};
15use crate::cell::Cell;
16use crate::simd::Path;
17use crate::Error;
18
19#[path = "pair_wide.rs"]
20mod wide;
21
22const MAX_IMAGES: i64 = 1 << 24;
23
24#[derive(Clone, Copy, Debug, PartialEq)]
26pub struct Pair {
27 pub i: usize,
29 pub j: usize,
31 pub shift: [i32; 3],
33 pub dist2: f64,
35}
36
37pub(crate) fn keep_half(i: usize, j: usize, shift: [i32; 3]) -> bool {
38 if i != j {
39 return i < j;
40 }
41 for s in shift {
42 if s != 0 {
43 return s < 0;
44 }
45 }
46 true
47}
48
49pub fn pairs_within(
55 xyz: &[[f64; 3]],
56 simbox: &Cell,
57 cutoff: f64,
58 mask: Option<&[bool]>,
59 cell_hint: Option<f64>,
60 half: bool,
61) -> Result<Vec<Pair>, Error> {
62 let est = hit_estimate(xyz.len(), simbox, cutoff);
63 if walk_threads(est) == 1 {
64 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
65 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
66 if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
67 return Ok(plan.fused_rows(&words));
68 }
69 return Ok(plan.search().into_pairs());
70 }
71 let rows_guess = row_guess(est, half);
74 let mut out: Vec<Pair> = Vec::with_capacity(rows_guess);
75 advise_huge(&mut out);
76 let base = RowPtr(out.as_mut_ptr() as *mut std::mem::MaybeUninit<Pair>);
77 let (rows, rest) = in_pool(est, || -> Result<(usize, Option<Found>), Error> {
78 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
79 #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
84 if let Some(words) = plan.fused_split().filter(|_| knobs::fused()) {
85 let ranges = cell_ranges(&plan.grid.offsets, plan.threads);
86 let per = rows_guess / ranges.len().max(1);
89 if ranges.len() > 1
90 && ranges.len() <= crate::pool_width()
91 && ahead(per, std::mem::size_of::<Pair>())
92 {
93 let off = plan.fused_offsets(&words, &ranges);
94 let rows = off[ranges.len()];
95 if rows <= rows_guess {
96 unsafe { plan.fused_fill(&words, base, &ranges, &off) };
98 return Ok((rows, None));
99 }
100 }
101 }
102 let found = plan.search();
103 let rows = found.rows();
104 if rows > rows_guess {
105 return Ok((rows, Some(found)));
106 }
107 unsafe { found.write_pairs(base.ptr()) };
109 Ok((rows, None))
110 })?;
111 if let Some(found) = rest {
112 out.reserve(rows);
113 unsafe { found.write_pairs(out.as_mut_ptr()) };
115 }
116 unsafe { out.set_len(rows) };
118 Ok(out)
119}
120
121pub fn pairs_within_count(
128 xyz: &[[f64; 3]],
129 simbox: &Cell,
130 cutoff: f64,
131 mask: Option<&[bool]>,
132 cell_hint: Option<f64>,
133 half: bool,
134) -> Result<usize, Error> {
135 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
136 #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
137 if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
138 return Ok(plan.count_rows(&words));
139 }
140 Ok(plan.search().rows())
141}
142
143pub fn pairs_within_into(
149 xyz: &[[f64; 3]],
150 simbox: &Cell,
151 cutoff: f64,
152 mask: Option<&[bool]>,
153 cell_hint: Option<f64>,
154 half: bool,
155 out: &mut Vec<Pair>,
156) -> Result<(), Error> {
157 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
158 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
159 if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
160 plan.fused_into_vec(&words, out);
161 return Ok(());
162 }
163 *out = plan.search().into_pairs();
164 Ok(())
165}
166
167fn advise_huge<T>(buf: &mut Vec<T>) {
172 #[cfg(all(
173 target_os = "linux",
174 any(target_arch = "x86_64", target_arch = "aarch64")
175 ))]
176 {
177 const HUGE: usize = 1 << 21;
178 const MADV_HUGEPAGE: std::ffi::c_int = 14;
179 extern "C" {
180 fn madvise(
181 addr: *mut std::ffi::c_void,
182 len: usize,
183 advice: std::ffi::c_int,
184 ) -> std::ffi::c_int;
185 }
186 let bytes = buf.capacity().saturating_mul(std::mem::size_of::<T>());
187 if bytes < 2 * HUGE {
188 return;
189 }
190 let start = buf.as_mut_ptr() as usize;
191 let lo = (start + HUGE - 1) & !(HUGE - 1);
192 let hi = (start + bytes) & !(HUGE - 1);
193 if hi > lo {
194 unsafe { madvise(lo as *mut std::ffi::c_void, hi - lo, MADV_HUGEPAGE) };
197 }
198 }
199 #[cfg(not(all(
200 target_os = "linux",
201 any(target_arch = "x86_64", target_arch = "aarch64")
202 )))]
203 let _ = buf;
204}
205
206fn row_guess(hits: usize, half: bool) -> usize {
209 let rows = if half { hits } else { hits.saturating_mul(2) };
210 rows.saturating_add(rows / 4).saturating_add(64)
211}
212
213pub fn pairs_within_columns(
221 xyz: &[[f64; 3]],
222 simbox: &Cell,
223 cutoff: f64,
224 mask: Option<&[bool]>,
225 cell_hint: Option<f64>,
226 half: bool,
227 out: &mut PairColumns,
228) -> Result<(), Error> {
229 if xyz.len() > i32::MAX as usize {
230 return Err(Error::Overflow);
231 }
232 let est = hit_estimate(xyz.len(), simbox, cutoff);
233 if walk_threads(est) == 1 {
234 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
235 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
236 if plan.fused().is_some() && knobs::fused() {
237 plan.fused_columns(out);
238 return Ok(());
239 }
240 plan.search().fill_columns(out);
241 return Ok(());
242 }
243 let rows_guess = row_guess(est, half);
246 out.i.clear();
247 out.j.clear();
248 out.shift.clear();
249 out.dist2.clear();
250 out.i.reserve(rows_guess);
251 out.j.reserve(rows_guess);
252 out.shift.reserve(rows_guess);
253 out.dist2.reserve(rows_guess);
254 out.advise_huge();
255 let ptrs = ColumnPtrs {
256 i: RowPtr(out.i.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
257 j: RowPtr(out.j.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
258 shift: RowPtr(out.shift.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
259 d2: RowPtr(out.dist2.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>),
260 };
261 let (rows, rest) = in_pool(est, || -> Result<(usize, Option<Found>), Error> {
262 let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
263 #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
267 if let Some(words) = plan.fused_split_columns().filter(|_| knobs::fused()) {
268 let ranges = cell_ranges(&plan.grid.offsets, plan.threads);
269 let per = rows_guess / ranges.len().max(1);
270 let dense = est / xyz.len().max(1) >= 64;
274 if dense
275 && ranges.len() > 1
276 && ranges.len() <= crate::pool_width()
277 && ahead(per, COLUMN_BYTES)
278 {
279 let off = plan.fused_offsets(&words, &ranges);
280 let rows = off[ranges.len()];
281 if rows <= rows_guess {
282 unsafe { plan.fused_fill_columns(&words, ptrs, &ranges, &off) };
284 return Ok((rows, None));
285 }
286 }
287 }
288 let found = plan.search();
289 let rows = found.rows();
290 if rows > rows_guess {
291 return Ok((rows, Some(found)));
292 }
293 unsafe { found.write_columns(ptrs.i.ptr(), ptrs.j.ptr(), ptrs.shift.ptr(), ptrs.d2.ptr()) };
295 Ok((rows, None))
296 })?;
297 match rest {
298 Some(found) => found.fill_columns(out),
299 None => unsafe {
301 out.i.set_len(rows);
302 out.j.set_len(rows);
303 out.shift.set_len(rows);
304 out.dist2.set_len(rows);
305 },
306 }
307 Ok(())
308}
309
310pub(crate) fn in_pool<R: Send>(hits: usize, work: impl FnOnce() -> R + Send) -> R {
319 #[cfg(feature = "parallel")]
320 if walk_threads(hits) > 1 && rayon::current_thread_index().is_none() {
321 return rayon::scope(|_| work());
322 }
323 let _ = hits;
324 work()
325}
326
327pub(crate) fn default_edge(simbox: &Cell, n: usize, cutoff: f64) -> f64 {
338 const VISIT_COST: f64 = 8.0;
339 let mut per = n as f64;
340 for width in simbox.widths() {
341 let cells = (width / cutoff).floor().clamp(1.0, 1.0e7);
342 per /= cells;
343 }
344 let k = (per / (2.0 * VISIT_COST)).powf(0.25);
345 let k = if k.is_finite() {
346 k.round().clamp(1.0, 6.0)
347 } else {
348 1.0
349 };
350 let edge = cutoff / k;
351 if edge.is_finite() && edge > 0.0 {
352 edge
353 } else {
354 cutoff
355 }
356}
357
358pub(crate) fn hit_estimate(n: usize, simbox: &Cell, cutoff: f64) -> usize {
360 let w = simbox.widths();
361 let volume = (w[0] * w[1] * w[2]).max(1.0e-30);
362 let shell = 4.1887902047863905 * cutoff * cutoff * cutoff;
363 let pairs = 0.5 * (n as f64) * (n as f64) * shell / volume;
364 if pairs.is_finite() {
365 pairs.min(usize::MAX as f64 / 2.0) as usize
366 } else {
367 0
368 }
369}
370
371#[derive(Clone, Debug, Default, PartialEq)]
373pub struct PairColumns {
374 pub i: Vec<i32>,
376 pub j: Vec<i32>,
378 pub shift: Vec<[i32; 3]>,
380 pub dist2: Vec<f64>,
382}
383
384impl PairColumns {
385 pub fn len(&self) -> usize {
387 self.i.len()
388 }
389
390 pub fn is_empty(&self) -> bool {
392 self.i.is_empty()
393 }
394
395 fn advise_huge(&mut self) {
397 advise_huge(&mut self.i);
398 advise_huge(&mut self.j);
399 advise_huge(&mut self.shift);
400 advise_huge(&mut self.dist2);
401 }
402}
403
404#[derive(Clone, Default)]
407struct ImageOffsets(Option<std::sync::Arc<Vec<[i64; 3]>>>);
408
409impl ImageOffsets {
410 fn new(
411 xyz: &[[f64; 3]],
412 cell: &Cell,
413 active: Option<&[usize]>,
414 repeats: [i32; 3],
415 ) -> Result<Self, Error> {
416 let inverse = cell.hinv();
417 let mut reference = None;
418 let mut images = Vec::new();
419 let mut low = [0i64; 3];
420 let mut high = [0i64; 3];
421 let count = active.map_or(xyz.len(), |indices| indices.len());
422 for at in 0..count {
423 let i = active.map_or(at, |indices| indices[at]);
424 let wrapped = cell.cartesian(cell.fractional(xyz[i]));
425 let delta = [
426 xyz[i][0] - wrapped[0],
427 xyz[i][1] - wrapped[1],
428 xyz[i][2] - wrapped[2],
429 ];
430 let image: [f64; 3] = std::array::from_fn(|a| {
431 (inverse[0][a] * delta[0] + inverse[1][a] * delta[1] + inverse[2][a] * delta[2])
432 .round()
433 });
434 let base = reference.get_or_insert(image);
435 let mut relative = [0i64; 3];
436 for a in 0..3 {
437 let value = image[a] - base[a];
438 if !value.is_finite() || value.abs() > i32::MAX as f64 {
439 return Err(Error::Overflow);
440 }
441 relative[a] = value as i64;
442 low[a] = low[a].min(relative[a]);
443 high[a] = high[a].max(relative[a]);
444 if high[a] - low[a] + i64::from(repeats[a]) > i64::from(i32::MAX) {
445 return Err(Error::Overflow);
446 }
447 }
448 if images.is_empty() && relative != [0; 3] {
449 images.resize(xyz.len(), [0; 3]);
450 }
451 if !images.is_empty() {
452 images[i] = relative;
453 }
454 }
455 Ok(Self(
456 (!images.is_empty()).then(|| std::sync::Arc::new(images)),
457 ))
458 }
459
460 fn shift(&self, i: usize, j: usize, wrapped: [i32; 3]) -> [i32; 3] {
461 match &self.0 {
462 None => wrapped,
463 Some(images) => std::array::from_fn(|a| {
464 (i64::from(wrapped[a]) + images[i][a] - images[j][a]) as i32
466 }),
467 }
468 }
469}
470
471pub(crate) struct Plan {
473 images: ImageOffsets,
474 grid: Grid,
475 partners: std::sync::Arc<PartnerList>,
476 cut2: f64,
477 margin: f64,
478 path: Path,
480 half: bool,
481 threads: usize,
482}
483
484impl Plan {
485 fn walk(&self) -> Walk<'_> {
486 Walk {
487 grid: &self.grid,
488 cut2: self.cut2,
489 margin: self.margin,
490 partners: &self.partners,
491 path: self.path,
492 }
493 }
494
495 pub(crate) fn search(&self) -> Found {
497 Found {
498 images: self.images.clone(),
499 chunks: self.walk().collect(self.threads),
500 half: self.half,
501 path: self.path,
502 }
503 }
504
505 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
508 fn fused(&self) -> Option<RowWords> {
509 if self.threads == 1 && self.path == Path::Avx512 && self.images.0.is_none() {
510 RowWords::of_pair()
511 } else {
512 None
513 }
514 }
515}
516
517#[cfg_attr(not(feature = "capi"), allow(dead_code))]
519pub(crate) fn search(
520 xyz: &[[f64; 3]],
521 simbox: &Cell,
522 cutoff: f64,
523 mask: Option<&[bool]>,
524 cell_hint: Option<f64>,
525 half: bool,
526) -> Result<Found, Error> {
527 Ok(plan(xyz, simbox, cutoff, mask, cell_hint, half)?.search())
528}
529
530pub(crate) fn plan(
531 xyz: &[[f64; 3]],
532 simbox: &Cell,
533 cutoff: f64,
534 mask: Option<&[bool]>,
535 cell_hint: Option<f64>,
536 half: bool,
537) -> Result<Plan, Error> {
538 if !cutoff.is_finite() || cutoff <= 0.0 {
539 return Err(Error::BadCutoff);
540 }
541 if xyz.is_empty() {
542 return Err(Error::Empty);
543 }
544 let n = xyz.len();
545 if n > u32::MAX as usize {
546 return Err(Error::Overflow);
547 }
548 if let Some(m) = mask {
549 if m.len() != n {
550 return Err(Error::MaskLen);
551 }
552 }
553 let active: Option<Vec<usize>> = mask.map(|m| (0..n).filter(|&i| m[i]).collect());
554 let n_act = active.as_ref().map_or(n, |a| a.len());
555 if n_act == 0 {
556 return Ok(Plan {
557 images: ImageOffsets::default(),
558 grid: Grid::empty(),
559 partners: std::sync::Arc::new(PartnerList {
560 key: ([0; 12], [1, 1, 1], [0; 3], 0),
561 off: vec![0],
562 items: Vec::new(),
563 s_max: 0.0,
564 d_max: 0.0,
565 }),
566 cut2: cutoff * cutoff,
567 margin: 0.0,
568 path: Path::Scalar,
569 half,
570 threads: 1,
571 });
572 }
573 retain_pair_pages();
574
575 let w = simbox.widths();
576 let mut image_count: i64 = 1;
577 let mut repeats = [0i32; 3];
578 for a in 0..3 {
579 let r = (cutoff / w[a]).ceil();
580 if !r.is_finite() || r > i32::MAX as f64 {
581 return Err(Error::TooManyImages);
582 }
583 repeats[a] = r as i32;
584 let factor = 2 * i64::from(repeats[a]) + 1;
585 if image_count > MAX_IMAGES / factor {
586 return Err(Error::TooManyImages);
587 }
588 image_count *= factor;
589 }
590
591 let edge = bins::target_edge(simbox, cell_hint, default_edge(simbox, n_act, cutoff));
592 let dims = bins::grid_dims(simbox, edge)?;
593 let cell_min = (w[0] / f64::from(dims[0]))
594 .min(w[1] / f64::from(dims[1]))
595 .min(w[2] / f64::from(dims[2]));
596 let reach_cut = (cutoff / cell_min).ceil();
597 if !reach_cut.is_finite() || reach_cut > i32::MAX as f64 {
598 return Err(Error::TooManyImages);
599 }
600 let max_reach = (reach_cut as i32)
601 .max(repeats[0] * dims[0])
602 .max(repeats[1] * dims[1])
603 .max(repeats[2] * dims[2])
604 .max(1);
605 let cut2 = cutoff * cutoff;
606 let reach = uniform_reach(dims, w, cut2, max_reach);
610 let threads = walk_threads(hit_estimate(n_act, simbox, cutoff));
611 let grid_threads = if n_act >= knobs::grid_atoms() {
612 threads
613 } else {
614 1
615 };
616 let path = crate::simd::select();
619 let grid = Grid::build(xyz, simbox, active.as_deref(), dims, grid_threads, path);
620 let partners = partners_for(&grid, simbox, reach, cut2);
621 let margin = expanded_margin(&grid, &partners, cutoff);
622 Ok(Plan {
623 images: ImageOffsets::new(xyz, simbox, active.as_deref(), repeats)?,
624 grid,
625 partners,
626 cut2,
627 margin,
628 path,
629 half,
630 threads,
631 })
632}
633
634fn walk_threads(hits: usize) -> usize {
637 #[cfg(feature = "parallel")]
638 {
639 let threads = crate::pool_width().max(1);
640 if threads > 1 && hits >= knobs::split_pairs() {
641 return threads;
642 }
643 }
644 let _ = hits;
645 1
646}
647
648fn retain_pair_pages() {
652 #[cfg(all(target_os = "linux", target_env = "gnu"))]
653 {
654 use std::sync::Once;
655 static ONCE: Once = Once::new();
656 ONCE.call_once(|| {
657 unsafe {
659 extern "C" {
660 fn mallopt(param: i32, value: i32) -> i32;
661 }
662 let _ = mallopt(-1, -1);
668 let _ = mallopt(-4, 0);
669 }
670 });
671 }
672}
673
674struct Partner {
675 jc: usize,
677 shift_s: [i32; 3],
678 shift: [f64; 3],
679 delta: [f64; 3],
683}
684
685struct PartnerList {
689 key: PartnerKey,
690 off: Vec<usize>,
691 items: Vec<Partner>,
692 s_max: f64,
694 d_max: f64,
695}
696
697type PartnerKey = ([u64; 12], [i32; 3], [i32; 3], u64);
700
701static PARTNERS: std::sync::Mutex<Option<std::sync::Arc<PartnerList>>> =
702 std::sync::Mutex::new(None);
703
704fn partners_for(
706 grid: &Grid,
707 simbox: &Cell,
708 reach: [i32; 3],
709 cut2: f64,
710) -> std::sync::Arc<PartnerList> {
711 let h = simbox.h();
712 let o = simbox.origin();
713 let mut boxbits = [0u64; 12];
714 for a in 0..3 {
715 for b in 0..3 {
716 boxbits[3 * a + b] = h[a][b].to_bits();
717 }
718 boxbits[9 + a] = o[a].to_bits();
719 }
720 let key: PartnerKey = (boxbits, grid.n, reach, cut2.to_bits());
721 if let Ok(slot) = PARTNERS.lock() {
722 if let Some(list) = slot.as_ref() {
723 if list.key == key {
724 return std::sync::Arc::clone(list);
725 }
726 }
727 }
728 let built = std::sync::Arc::new(build_partners(grid, simbox, reach, cut2, key));
729 if let Ok(mut slot) = PARTNERS.lock() {
730 *slot = Some(std::sync::Arc::clone(&built));
731 }
732 built
733}
734
735fn bin_gap(src: i32, dst: i32, width: f64) -> f64 {
736 let lo_s = f64::from(src) * width;
737 let hi_s = f64::from(src + 1) * width;
738 let lo_d = f64::from(dst) * width;
739 let hi_d = f64::from(dst + 1) * width;
740 if hi_s <= lo_d {
741 lo_d - hi_s
742 } else if hi_d <= lo_s {
743 lo_s - hi_d
744 } else {
745 0.0
746 }
747}
748
749fn bins_too_far(ortho: bool, src: [i32; 3], dst: [i32; 3], width: [f64; 3], cut2: f64) -> bool {
750 let gap = [
751 bin_gap(src[0], dst[0], width[0]),
752 bin_gap(src[1], dst[1], width[1]),
753 bin_gap(src[2], dst[2], width[2]),
754 ];
755 let bound = if ortho {
756 let d = (gap[0] * gap[0] + gap[1] * gap[1] + gap[2] * gap[2]).sqrt();
757 let d = bins::certify(d);
758 d * d
759 } else {
760 let d = bins::certify(gap[0].max(gap[1]).max(gap[2]));
761 d * d
762 };
763 bound >= cut2
764}
765
766fn build_partners(
767 grid: &Grid,
768 simbox: &Cell,
769 reach: [i32; 3],
770 cut2: f64,
771 key: PartnerKey,
772) -> PartnerList {
773 let [nx, ny, nz] = grid.n;
774 let ncell = (nx as usize) * (ny as usize) * (nz as usize);
775 let width = [
776 grid.widths[0] / f64::from(nx),
777 grid.widths[1] / f64::from(ny),
778 grid.widths[2] / f64::from(nz),
779 ];
780 let ortho = simbox.is_ortho();
781 let [rx, ry, rz] = reach;
782 let mut off = vec![0usize; ncell + 1];
783 let mut items = Vec::new();
784 let (mut s_max, mut d_max) = (0.0f64, 0.0f64);
785 for iz in 0..nz {
786 for iy in 0..ny {
787 for ix in 0..nx {
788 let cell = ((iz * ny + iy) * nx + ix) as usize;
789 let src = [ix, iy, iz];
790 for dz in -rz..=rz {
791 for dy in -ry..=ry {
792 for dx in -rx..=rx {
793 if !keep_dir(dx, dy, dz) {
794 continue;
795 }
796 let dst = [ix + dx, iy + dy, iz + dz];
797 if bins_too_far(ortho, src, dst, width, cut2) {
798 continue;
799 }
800 let jc = bins::wrap_cell(dst, grid.n);
801 let shift_s = [
802 dst[0].div_euclid(nx),
803 dst[1].div_euclid(ny),
804 dst[2].div_euclid(nz),
805 ];
806 let shift = simbox.lattice_shift(shift_s[0], shift_s[1], shift_s[2]);
807 let (a, b) = (grid.corners[cell], grid.corners[jc]);
808 let delta = [
809 a[0] - b[0] - shift[0],
810 a[1] - b[1] - shift[1],
811 a[2] - b[2] - shift[2],
812 ];
813 for k in 0..3 {
814 s_max = s_max.max(shift[k].abs());
815 d_max = d_max.max(delta[k].abs());
816 }
817 items.push(Partner {
818 jc,
819 shift_s,
820 shift,
821 delta,
822 });
823 }
824 }
825 }
826 off[cell + 1] = items.len();
827 }
828 }
829 }
830 let list = PartnerList {
831 key,
832 off,
833 items,
834 s_max,
835 d_max,
836 };
837 crate::open_cell::note_stencil_build();
838 list
839}
840
841#[derive(Default)]
842struct Coords {
843 x: Vec<f64>,
844 y: Vec<f64>,
845 z: Vec<f64>,
846 rx: Vec<f64>,
848 ry: Vec<f64>,
849 rz: Vec<f64>,
850 r2: Vec<f64>,
852 id: Vec<u32>,
854}
855
856impl Coords {
857 fn clear_for(&mut self, nslot: usize) {
859 for v in [
860 &mut self.x,
861 &mut self.y,
862 &mut self.z,
863 &mut self.rx,
864 &mut self.ry,
865 &mut self.rz,
866 &mut self.r2,
867 ] {
868 v.clear();
869 v.reserve(nslot);
870 }
871 self.id.clear();
872 self.id.reserve(nslot);
873 }
874
875 unsafe fn set_len(&mut self, nslot: usize) {
878 for v in [
879 &mut self.x,
880 &mut self.y,
881 &mut self.z,
882 &mut self.rx,
883 &mut self.ry,
884 &mut self.rz,
885 &mut self.r2,
886 ] {
887 v.set_len(nslot);
888 }
889 self.id.set_len(nslot);
890 }
891}
892
893#[derive(Default)]
896struct GridBufs {
897 offsets: Vec<usize>,
898 corners: Vec<[f64; 3]>,
899 coords: Coords,
900 fold: FoldCols,
901 tally: Vec<u32>,
902 order: Vec<u32>,
903 boxes: Boxes,
904}
905
906#[derive(Default)]
912struct Boxes {
913 on: bool,
916 vstart: Vec<usize>,
919 gstart: Vec<usize>,
920 v: [Vec<f64>; 6],
923 g: [Vec<f64>; 6],
925}
926
927impl Boxes {
928 fn starts(&mut self, offsets: &[usize], on: bool) {
930 self.on = on;
931 self.vstart.clear();
932 self.gstart.clear();
933 if !on {
934 self.vstart.resize(offsets.len(), 0);
935 self.gstart.resize(offsets.len(), 0);
936 return;
937 }
938 let (mut v, mut g) = (0usize, 0usize);
939 for w in offsets.windows(2) {
940 self.vstart.push(v);
941 self.gstart.push(g);
942 let n = w[1] - w[0];
943 v += (n + 7) / 8;
944 g += (n + 3) / 4;
945 }
946 self.vstart.push(v);
947 self.gstart.push(g);
948 for a in self.v.iter_mut() {
952 a.clear();
953 a.reserve(v + 8);
954 unsafe { std::ptr::write_bytes(a.as_mut_ptr().add(v), 0, 8) };
956 }
957 for a in self.g.iter_mut() {
958 a.clear();
959 a.reserve(g);
960 }
961 }
962
963 fn ptrs(&mut self) -> BoxPtrs {
964 let raw = |a: &mut Vec<f64>| RowPtr(a.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
965 let [v0, v1, v2, v3, v4, v5] = &mut self.v;
966 let [g0, g1, g2, g3, g4, g5] = &mut self.g;
967 BoxPtrs {
968 v: [raw(v0), raw(v1), raw(v2), raw(v3), raw(v4), raw(v5)],
969 g: [raw(g0), raw(g1), raw(g2), raw(g3), raw(g4), raw(g5)],
970 }
971 }
972}
973
974#[derive(Clone, Copy)]
976struct BoxPtrs {
977 v: [RowPtr<f64>; 6],
978 g: [RowPtr<f64>; 6],
979}
980
981impl BoxPtrs {
982 unsafe fn fill(self, slots: SlotPtrs, lo: usize, hi: usize, v0: usize, g0: usize) {
989 let (rx, ry, rz) = (slots.rx.ptr(), slots.ry.ptr(), slots.rz.ptr());
990 let mut last = ([0.0f64; 3], [0.0f64; 3]);
992 for (m, a) in (lo..hi).step_by(4).enumerate() {
993 let (mut l, mut h) = ([f64::INFINITY; 3], [f64::NEG_INFINITY; 3]);
994 for s in a..(a + 4).min(hi) {
995 let r = [*rx.add(s), *ry.add(s), *rz.add(s)];
996 for ax in 0..3 {
997 l[ax] = l[ax].min(r[ax]);
998 h[ax] = h[ax].max(r[ax]);
999 }
1000 }
1001 for ax in 0..3 {
1002 (*self.g[ax].at(g0 + m)).write(l[ax]);
1003 (*self.g[3 + ax].at(g0 + m)).write(h[ax]);
1004 }
1005 let odd = m % 2 == 1;
1006 if odd {
1007 for ax in 0..3 {
1008 l[ax] = l[ax].min(last.0[ax]);
1009 h[ax] = h[ax].max(last.1[ax]);
1010 }
1011 }
1012 if odd || a + 4 >= hi {
1013 for ax in 0..3 {
1014 (*self.v[ax].at(v0 + m / 2)).write(l[ax]);
1015 (*self.v[3 + ax].at(v0 + m / 2)).write(h[ax]);
1016 }
1017 }
1018 last = (l, h);
1019 }
1020 }
1021}
1022
1023static GRID_POOL: std::sync::Mutex<Option<GridBufs>> = std::sync::Mutex::new(None);
1024
1025fn take_grid_bufs() -> GridBufs {
1026 GRID_POOL
1027 .lock()
1028 .ok()
1029 .and_then(|mut slot| slot.take())
1030 .unwrap_or_default()
1031}
1032
1033fn give_grid_bufs(bufs: GridBufs) {
1034 const MAX_KEEP: usize = 1 << 20;
1035 if bufs.coords.x.capacity() > MAX_KEEP || bufs.offsets.capacity() > MAX_KEEP {
1036 return;
1037 }
1038 if let Ok(mut slot) = GRID_POOL.lock() {
1039 if slot.is_none() {
1040 *slot = Some(bufs);
1041 }
1042 }
1043}
1044
1045struct Grid {
1050 n: [i32; 3],
1051 widths: [f64; 3],
1052 offsets: Vec<usize>,
1053 corners: Vec<[f64; 3]>,
1055 coords: Coords,
1056 max_abs: f64,
1058 max_rel: f64,
1059 fold: FoldCols,
1061 tally: Vec<u32>,
1062 order: Vec<u32>,
1063 boxes: Boxes,
1064}
1065
1066impl Drop for Grid {
1067 fn drop(&mut self) {
1068 give_grid_bufs(GridBufs {
1069 offsets: std::mem::take(&mut self.offsets),
1070 corners: std::mem::take(&mut self.corners),
1071 coords: std::mem::take(&mut self.coords),
1072 fold: std::mem::take(&mut self.fold),
1073 tally: std::mem::take(&mut self.tally),
1074 order: std::mem::take(&mut self.order),
1075 boxes: std::mem::take(&mut self.boxes),
1076 });
1077 }
1078}
1079
1080#[cfg(feature = "parallel")]
1083#[derive(Clone, Copy, Default)]
1084struct Staged {
1085 p: [f64; 3],
1086 sub: u32,
1087 atom: u32,
1088}
1089
1090#[derive(Default)]
1092struct FoldCols {
1093 x: Vec<f64>,
1094 y: Vec<f64>,
1095 z: Vec<f64>,
1096 key: Vec<u32>,
1097}
1098
1099impl FoldCols {
1100 fn clear_for(&mut self, n: usize) {
1101 for v in [&mut self.x, &mut self.y, &mut self.z] {
1102 v.clear();
1103 v.reserve(n);
1104 }
1105 self.key.clear();
1106 self.key.reserve(n);
1107 }
1108
1109 fn ptrs(&mut self) -> FoldPtrs {
1110 let raw = |v: &mut Vec<f64>| RowPtr(v.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
1111 FoldPtrs {
1112 x: raw(&mut self.x),
1113 y: raw(&mut self.y),
1114 z: raw(&mut self.z),
1115 key: RowPtr(self.key.as_mut_ptr() as *mut std::mem::MaybeUninit<u32>),
1116 }
1117 }
1118}
1119
1120#[derive(Clone, Copy)]
1122struct FoldPtrs {
1123 x: RowPtr<f64>,
1124 y: RowPtr<f64>,
1125 z: RowPtr<f64>,
1126 key: RowPtr<u32>,
1127}
1128
1129impl FoldPtrs {
1130 #[inline(always)]
1133 unsafe fn put(self, k: usize, p: [f64; 3], key: usize) {
1134 (*self.x.at(k)).write(p[0]);
1135 (*self.y.at(k)).write(p[1]);
1136 (*self.z.at(k)).write(p[2]);
1137 (*self.key.at(k)).write(key as u32);
1138 }
1139
1140 #[inline(always)]
1143 unsafe fn get(self, k: usize) -> ([f64; 3], usize) {
1144 (
1145 [
1146 (*self.x.at(k)).assume_init(),
1147 (*self.y.at(k)).assume_init(),
1148 (*self.z.at(k)).assume_init(),
1149 ],
1150 (*self.key.at(k)).assume_init() as usize,
1151 )
1152 }
1153}
1154
1155#[derive(Clone, Copy)]
1159struct Keys {
1160 n: [i32; 3],
1161 sub: i32,
1162}
1163
1164impl Keys {
1165 fn sub_for(n_act: usize, ncell: usize) -> i32 {
1169 let per_bin = n_act / ncell.max(1);
1170 if per_bin >= 48 {
1171 4
1172 } else if per_bin >= 6 {
1173 2
1174 } else {
1175 1
1176 }
1177 }
1178
1179 fn fine(self) -> [i32; 3] {
1181 [
1182 self.n[0] * self.sub,
1183 self.n[1] * self.sub,
1184 self.n[2] * self.sub,
1185 ]
1186 }
1187
1188 fn per_bin(self) -> usize {
1190 (self.sub * self.sub * self.sub) as usize
1191 }
1192
1193 #[inline(always)]
1196 fn key(self, b: [i32; 3]) -> usize {
1197 let shift = self.sub.trailing_zeros();
1198 let low = self.sub - 1;
1199 let coarse = bins::flat_cell([b[0] >> shift, b[1] >> shift, b[2] >> shift], self.n);
1200 let spread = |v: i32| {
1202 let v = (v & low) as usize;
1203 (v & 1) | ((v & 2) << 2) | ((v & 4) << 4)
1204 };
1205 let m = spread(b[0]) | (spread(b[1]) << 1) | (spread(b[2]) << 2);
1206 coarse * self.per_bin() + m
1207 }
1208}
1209
1210#[allow(clippy::too_many_arguments)]
1214fn fold_range(
1215 simbox: &Cell,
1216 xyz: &[[f64; 3]],
1217 active: Option<&[usize]>,
1218 keys: Keys,
1219 by_bin: bool,
1220 path: Path,
1221 lo: usize,
1222 hi: usize,
1223 fold: FoldPtrs,
1224 count: &mut [u32],
1225) {
1226 let shift = if by_bin {
1227 keys.per_bin().trailing_zeros()
1228 } else {
1229 0
1230 };
1231 #[allow(unused_mut)]
1232 let mut slot = lo;
1233 #[cfg(not(all(target_arch = "x86_64", linkcell_avx512)))]
1234 let _ = path;
1235 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1236 if active.is_none() && path == Path::Avx512 {
1237 slot = unsafe { fold_avx512(simbox, xyz, keys, shift, lo, hi, fold, count) };
1240 }
1241 let fine = keys.fine();
1242 for k in slot..hi {
1243 let i = active.map_or(k, |a| a[k]);
1244 let (q, b) = bins::fold_point(simbox, xyz[i], fine);
1245 let key = keys.key(b);
1246 count[key >> shift] += 1;
1247 unsafe { fold.put(k, q, key) };
1249 }
1250}
1251
1252#[allow(clippy::incompatible_msrv, clippy::too_many_arguments)]
1259#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1260#[target_feature(enable = "avx512f")]
1261unsafe fn fold_avx512(
1262 simbox: &Cell,
1263 xyz: &[[f64; 3]],
1264 keys: Keys,
1265 shift: u32,
1266 lo: usize,
1267 hi: usize,
1268 fold: FoldPtrs,
1269 count: &mut [u32],
1270) -> usize {
1271 use std::arch::x86_64::{
1272 __m256i, _mm256_add_epi32, _mm256_and_si256, _mm256_mullo_epi32, _mm256_or_si256,
1273 _mm256_set1_epi32, _mm256_sll_epi32, _mm256_slli_epi32, _mm256_srl_epi32,
1274 _mm256_storeu_si256, _mm512_storeu_pd, _mm_cvtsi32_si128,
1275 };
1276 let f = bins::Fold8::new(simbox, keys.fine());
1277 let flat = xyz.as_ptr() as *const f64;
1278 let bits = keys.sub.trailing_zeros() as i32;
1279 let down = _mm_cvtsi32_si128(bits);
1280 let up = _mm_cvtsi32_si128(3 * bits);
1281 let (nx, ny) = (_mm256_set1_epi32(keys.n[0]), _mm256_set1_epi32(keys.n[1]));
1282 let low = _mm256_set1_epi32(keys.sub - 1);
1283 let (one, two, four) = (
1284 _mm256_set1_epi32(1),
1285 _mm256_set1_epi32(2),
1286 _mm256_set1_epi32(4),
1287 );
1288 let spread = |v: __m256i| {
1289 let v = _mm256_and_si256(v, low);
1290 _mm256_or_si256(
1291 _mm256_and_si256(v, one),
1292 _mm256_or_si256(
1293 _mm256_slli_epi32::<2>(_mm256_and_si256(v, two)),
1294 _mm256_slli_epi32::<4>(_mm256_and_si256(v, four)),
1295 ),
1296 )
1297 };
1298 let mut lane = [0u32; 8];
1299 let mut k = lo;
1300 while k + 8 <= hi {
1301 let (_, p, b) = bins::fold8_regs(&f, flat.add(3 * k));
1302 let coarse = _mm256_add_epi32(
1303 _mm256_mullo_epi32(
1304 _mm256_add_epi32(
1305 _mm256_mullo_epi32(_mm256_srl_epi32(b[2], down), ny),
1306 _mm256_srl_epi32(b[1], down),
1307 ),
1308 nx,
1309 ),
1310 _mm256_srl_epi32(b[0], down),
1311 );
1312 let m = _mm256_or_si256(
1313 spread(b[0]),
1314 _mm256_or_si256(
1315 _mm256_slli_epi32::<1>(spread(b[1])),
1316 _mm256_slli_epi32::<2>(spread(b[2])),
1317 ),
1318 );
1319 let key = _mm256_or_si256(_mm256_sll_epi32(coarse, up), m);
1320 _mm512_storeu_pd(fold.x.ptr().add(k), p[0]);
1321 _mm512_storeu_pd(fold.y.ptr().add(k), p[1]);
1322 _mm512_storeu_pd(fold.z.ptr().add(k), p[2]);
1323 _mm256_storeu_si256(fold.key.ptr().add(k) as *mut _, key);
1324 _mm256_storeu_si256(lane.as_mut_ptr() as *mut _, key);
1325 for &c in &lane {
1326 count[(c >> shift) as usize] += 1;
1327 }
1328 k += 8;
1329 }
1330 k
1331}
1332
1333#[derive(Clone, Copy)]
1335struct SlotPtrs {
1336 x: RowPtr<f64>,
1337 y: RowPtr<f64>,
1338 z: RowPtr<f64>,
1339 rx: RowPtr<f64>,
1340 ry: RowPtr<f64>,
1341 rz: RowPtr<f64>,
1342 r2: RowPtr<f64>,
1343 id: RowPtr<u32>,
1344}
1345
1346impl SlotPtrs {
1347 fn of(c: &mut Coords) -> Self {
1348 let raw = |v: &mut Vec<f64>| RowPtr(v.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
1349 SlotPtrs {
1350 x: raw(&mut c.x),
1351 y: raw(&mut c.y),
1352 z: raw(&mut c.z),
1353 rx: raw(&mut c.rx),
1354 ry: raw(&mut c.ry),
1355 rz: raw(&mut c.rz),
1356 r2: raw(&mut c.r2),
1357 id: RowPtr(c.id.as_mut_ptr() as *mut std::mem::MaybeUninit<u32>),
1358 }
1359 }
1360
1361 #[inline(always)]
1367 unsafe fn put(self, slot: usize, i: usize, p: [f64; 3], o: [f64; 3]) -> (f64, f64) {
1368 let (rx, ry, rz) = (p[0] - o[0], p[1] - o[1], p[2] - o[2]);
1369 (*self.x.at(slot)).write(p[0]);
1370 (*self.y.at(slot)).write(p[1]);
1371 (*self.z.at(slot)).write(p[2]);
1372 (*self.rx.at(slot)).write(rx);
1373 (*self.ry.at(slot)).write(ry);
1374 (*self.rz.at(slot)).write(rz);
1375 (*self.r2.at(slot)).write(rx * rx + ry * ry + rz * rz);
1376 (*self.id.at(slot)).write(i as u32);
1377 (
1378 p[0].abs().max(p[1].abs()).max(p[2].abs()),
1379 rx.abs().max(ry.abs()).max(rz.abs()),
1380 )
1381 }
1382}
1383
1384impl Grid {
1385 fn build(
1392 xyz: &[[f64; 3]],
1393 simbox: &Cell,
1394 active: Option<&[usize]>,
1395 n: [i32; 3],
1396 threads: usize,
1397 path: Path,
1398 ) -> Grid {
1399 let ncell = (n[0] as usize) * (n[1] as usize) * (n[2] as usize);
1400 let n_act = active.map_or(xyz.len(), |a| a.len());
1401 let atom = |k: usize| active.map_or(k, |a| a[k]);
1402 let GridBufs {
1406 mut offsets,
1407 mut corners,
1408 mut coords,
1409 mut fold,
1410 mut tally,
1411 mut order,
1412 mut boxes,
1413 } = take_grid_bufs();
1414 offsets.clear();
1415 offsets.reserve(ncell + 1);
1416 corners.clear();
1417 corners.reserve(ncell);
1418 coords.clear_for(n_act);
1419 fold.clear_for(n_act);
1421 let fp = fold.ptrs();
1422 let cp = RowPtr(corners.as_mut_ptr() as *mut std::mem::MaybeUninit<[f64; 3]>);
1423 let slots = SlotPtrs::of(&mut coords);
1424 let corners_of = |lo: usize, hi: usize| {
1427 let (nx, ny) = (n[0] as usize, n[1] as usize);
1428 let (mut ix, mut iy, mut iz) = (lo % nx, (lo / nx) % ny, lo / (nx * ny));
1429 for c in lo..hi {
1430 let corner = simbox.cartesian([
1431 f64::from(ix as i32) / f64::from(n[0]),
1432 f64::from(iy as i32) / f64::from(n[1]),
1433 f64::from(iz as i32) / f64::from(n[2]),
1434 ]);
1435 unsafe { (*cp.at(c)).write(corner) };
1437 ix += 1;
1438 if ix == nx {
1439 ix = 0;
1440 iy += 1;
1441 if iy == ny {
1442 iy = 0;
1443 iz += 1;
1444 }
1445 }
1446 }
1447 };
1448 let (mut max_abs, mut max_rel) = (0.0f64, 0.0f64);
1449 let keys = Keys {
1450 n,
1451 sub: Keys::sub_for(n_act, ncell),
1452 };
1453 let per = keys.per_bin();
1454 let nkey = ncell * per;
1455 let cull = path != Path::Scalar && n_act >= 8 * CULL_RUNS * ncell && !no_cull();
1456 #[cfg(feature = "parallel")]
1457 let parallel = threads > 1;
1458 #[cfg(not(feature = "parallel"))]
1459 let parallel = {
1460 let _ = threads;
1461 false
1462 };
1463 if parallel {
1464 #[cfg(feature = "parallel")]
1465 {
1466 let p = crate::pool_width().max(1);
1467 let block = |k: usize, len: usize| (k * len / p, (k + 1) * len / p);
1468 let shift = per.trailing_zeros();
1469 let staged: Vec<(Vec<Staged>, Vec<usize>)> = rayon::broadcast(|ctx| {
1473 let _timer = crate::pop::JobTimer::new();
1474 let k = ctx.index();
1475 let (lo, hi) = block(k, n_act);
1476 let mut count = vec![0u32; ncell];
1477 fold_range(
1479 simbox, xyz, active, keys, true, path, lo, hi, fp, &mut count,
1480 );
1481 let mut first = Vec::with_capacity(ncell + 1);
1482 let mut at = 0usize;
1483 for &c in &count {
1484 first.push(at);
1485 at += c as usize;
1486 }
1487 first.push(at);
1488 let mut next = first.clone();
1489 let mut stage = vec![Staged::default(); hi - lo];
1490 for slot in lo..hi {
1491 let (p, key) = unsafe { fp.get(slot) };
1493 let c = key >> shift;
1494 stage[next[c]] = Staged {
1495 p,
1496 sub: (key & (per - 1)) as u32,
1497 atom: atom(slot) as u32,
1498 };
1499 next[c] += 1;
1500 }
1501 let (clo, chi) = block(k, ncell);
1502 corners_of(clo, chi);
1504 (stage, first)
1505 });
1506 unsafe { corners.set_len(ncell) };
1508 let mut at = 0usize;
1510 for c in 0..ncell {
1511 offsets.push(at);
1512 for (_, first) in &staged {
1513 at += first[c + 1] - first[c];
1514 }
1515 }
1516 offsets.push(at);
1517 boxes.starts(&offsets, cull);
1518 let bp = boxes.ptrs();
1519 let (vstart, gstart) = (&boxes.vstart, &boxes.gstart);
1520 let ranges = cell_ranges(&offsets, p);
1527 let (staged, corners, offsets, ranges) = (&staged, &corners, &offsets, &ranges);
1528 let maxima: Vec<(f64, f64)> = rayon::broadcast(|ctx| {
1529 let _timer = crate::pop::JobTimer::new();
1530 let (mut ma, mut mr) = (0.0f64, 0.0f64);
1531 let Some(&(clo, chi)) = ranges.get(ctx.index()) else {
1532 return (ma, mr);
1533 };
1534 let mut bucket = vec![0usize; per + 1];
1535 for c in clo..chi {
1536 bucket.iter_mut().for_each(|b| *b = 0);
1537 for (stage, first) in staged {
1538 for e in &stage[first[c]..first[c + 1]] {
1539 bucket[e.sub as usize + 1] += 1;
1540 }
1541 }
1542 let mut acc = offsets[c];
1543 for b in bucket.iter_mut() {
1544 acc += *b;
1545 *b = acc;
1546 }
1547 for (stage, first) in staged {
1548 for e in &stage[first[c]..first[c + 1]] {
1549 let dest = bucket[e.sub as usize];
1550 bucket[e.sub as usize] += 1;
1551 let (a, r) =
1554 unsafe { slots.put(dest, e.atom as usize, e.p, corners[c]) };
1555 ma = ma.max(a);
1556 mr = mr.max(r);
1557 }
1558 }
1559 if cull {
1560 unsafe {
1562 bp.fill(slots, offsets[c], offsets[c + 1], vstart[c], gstart[c])
1563 };
1564 }
1565 }
1566 (ma, mr)
1567 });
1568 for (a, r) in maxima {
1569 max_abs = max_abs.max(a);
1570 max_rel = max_rel.max(r);
1571 }
1572 }
1573 } else {
1574 let _timer = crate::pop::JobTimer::new();
1575 tally.clear();
1576 tally.resize(nkey, 0);
1577 fold_range(
1578 simbox, xyz, active, keys, false, path, 0, n_act, fp, &mut tally,
1579 );
1580 corners_of(0, ncell);
1581 unsafe { corners.set_len(ncell) };
1583 let mut at = 0usize;
1585 for bin in tally.chunks_exact_mut(per) {
1586 offsets.push(at);
1587 for t in bin {
1588 let count = *t as usize;
1589 *t = at as u32;
1590 at += count;
1591 }
1592 }
1593 offsets.push(at);
1594 order.clear();
1598 order.reserve(n_act);
1599 let op = order.as_mut_ptr();
1600 for k in 0..n_act {
1601 unsafe {
1604 let key = (*fp.key.at(k)).assume_init() as usize;
1605 let dest = tally[key] as usize;
1606 tally[key] += 1;
1607 op.add(dest).write(k as u32);
1608 }
1609 }
1610 boxes.starts(&offsets, cull);
1611 let bp = boxes.ptrs();
1612 for c in 0..ncell {
1613 let corner = corners[c];
1614 for dest in offsets[c]..offsets[c + 1] {
1615 let (a, r) = unsafe {
1618 let k = *op.add(dest) as usize;
1619 let (p, _) = fp.get(k);
1620 slots.put(dest, atom(k), p, corner)
1621 };
1622 max_abs = max_abs.max(a);
1623 max_rel = max_rel.max(r);
1624 }
1625 if cull {
1626 unsafe {
1628 bp.fill(
1629 slots,
1630 offsets[c],
1631 offsets[c + 1],
1632 boxes.vstart[c],
1633 boxes.gstart[c],
1634 )
1635 };
1636 }
1637 }
1638 }
1639 unsafe { coords.set_len(n_act) };
1641 Grid {
1642 n,
1643 widths: simbox.widths(),
1644 offsets,
1645 corners,
1646 coords,
1647 max_abs,
1648 max_rel,
1649 fold,
1650 tally,
1651 order,
1652 boxes,
1653 }
1654 }
1655
1656 fn atoms(&self) -> usize {
1657 self.coords.id.len()
1658 }
1659
1660 fn empty() -> Grid {
1662 Grid {
1663 n: [1, 1, 1],
1664 widths: [0.0; 3],
1665 offsets: vec![0],
1666 corners: Vec::new(),
1667 coords: Coords::default(),
1668 max_abs: 0.0,
1669 max_rel: 0.0,
1670 fold: FoldCols::default(),
1671 tally: Vec::new(),
1672 order: Vec::new(),
1673 boxes: Boxes {
1674 vstart: vec![0],
1675 gstart: vec![0],
1676 ..Boxes::default()
1677 },
1678 }
1679 }
1680}
1681
1682fn expanded_margin(grid: &Grid, partners: &PartnerList, cutoff: f64) -> f64 {
1694 let (a, r) = (grid.max_abs, grid.max_rel);
1695 let (s, d) = (partners.s_max, partners.d_max);
1696 let span = 2.0 * a + s + 2.0 * r + d + cutoff;
1697 192.0 * f64::EPSILON * 0.5 * span * span
1698}
1699
1700fn keep_dir(dx: i32, dy: i32, dz: i32) -> bool {
1702 if dx != 0 {
1703 return dx > 0;
1704 }
1705 if dy != 0 {
1706 return dy > 0;
1707 }
1708 if dz != 0 {
1709 return dz > 0;
1710 }
1711 false
1712}
1713
1714fn uniform_reach(nbin: [i32; 3], widths: [f64; 3], cut2: f64, max_reach: i32) -> [i32; 3] {
1715 let mut reach = [1i32; 3];
1716 loop {
1717 let mut grew = false;
1718 for a in 0..3 {
1719 let n = nbin[a];
1720 let w = widths[a];
1721 let nf = f64::from(n);
1722 let s_hi = (1.0 - 1.0e-12) / nf;
1723 let gap = bins::certify(
1724 axis_gap(0.0, 0, reach[a], n, w).min(axis_gap(s_hi, 0, reach[a], n, w)),
1725 );
1726 let bound = if gap > 0.0 && gap.is_finite() {
1727 gap * gap
1728 } else {
1729 0.0
1730 };
1731 if bound < cut2 && reach[a] < max_reach {
1732 reach[a] += 1;
1733 grew = true;
1734 }
1735 }
1736 if !grew {
1737 break;
1738 }
1739 }
1740 reach
1741}
1742
1743struct Walk<'a> {
1744 grid: &'a Grid,
1745 cut2: f64,
1746 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1748 margin: f64,
1749 partners: &'a PartnerList,
1750 path: Path,
1753}
1754
1755#[derive(Clone, Copy)]
1756struct Block {
1757 i_lo: usize,
1758 i_hi: usize,
1759 j_lo: usize,
1760 j_hi: usize,
1761 shift_s: [i32; 3],
1762 shift: [f64; 3],
1763 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1765 delta: [f64; 3],
1766 tri: bool,
1768 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1771 jv: usize,
1772 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1773 ig: usize,
1774}
1775
1776#[cfg(feature = "parallel")]
1784const PARALLEL_PAIRS: usize = 2_000;
1785
1786const PARALLEL_GRID: usize = 1_024;
1791
1792pub(crate) mod knobs {
1796 #[cfg(feature = "tune")]
1798 pub(crate) const SPLIT_PAIRS: usize = 0;
1799 #[cfg(feature = "tune")]
1800 pub(crate) const GRID_ATOMS: usize = 1;
1801 #[cfg(feature = "tune")]
1802 pub(crate) const FUSED: usize = 2;
1803 #[cfg(feature = "tune")]
1804 pub(crate) const CHUNKS: usize = 3;
1805 #[cfg(feature = "tune")]
1806 pub(crate) const AHEAD_FROM: usize = 4;
1807
1808 #[cfg(feature = "tune")]
1809 pub(crate) static VALUES: [std::sync::atomic::AtomicUsize; 5] = [
1810 std::sync::atomic::AtomicUsize::new(super::DEFAULT_SPLIT_PAIRS),
1811 std::sync::atomic::AtomicUsize::new(super::PARALLEL_GRID),
1812 std::sync::atomic::AtomicUsize::new(1),
1813 std::sync::atomic::AtomicUsize::new(1),
1814 std::sync::atomic::AtomicUsize::new(super::AHEAD_FROM),
1815 ];
1816
1817 #[cfg(feature = "tune")]
1818 fn get(key: usize) -> usize {
1819 VALUES[key].load(std::sync::atomic::Ordering::Relaxed)
1820 }
1821
1822 #[cfg(feature = "parallel")]
1824 pub(crate) fn split_pairs() -> usize {
1825 #[cfg(feature = "tune")]
1826 return get(SPLIT_PAIRS);
1827 #[cfg(not(feature = "tune"))]
1828 super::PARALLEL_PAIRS
1829 }
1830
1831 pub(crate) fn grid_atoms() -> usize {
1833 #[cfg(feature = "tune")]
1834 return get(GRID_ATOMS);
1835 #[cfg(not(feature = "tune"))]
1836 super::PARALLEL_GRID
1837 }
1838
1839 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1841 pub(crate) fn fused() -> bool {
1842 #[cfg(feature = "tune")]
1843 return get(FUSED) != 0;
1844 #[cfg(not(feature = "tune"))]
1845 true
1846 }
1847
1848 #[cfg_attr(not(feature = "parallel"), allow(dead_code))]
1850 pub(crate) fn chunks() -> usize {
1851 #[cfg(feature = "tune")]
1852 return get(CHUNKS).max(1);
1853 #[cfg(not(feature = "tune"))]
1854 1
1855 }
1856
1857 pub(crate) fn ahead_from() -> usize {
1859 #[cfg(feature = "tune")]
1860 return get(AHEAD_FROM);
1861 #[cfg(not(feature = "tune"))]
1862 super::AHEAD_FROM
1863 }
1864}
1865
1866#[cfg(feature = "tune")]
1868#[cfg(feature = "parallel")]
1869const DEFAULT_SPLIT_PAIRS: usize = PARALLEL_PAIRS;
1870#[cfg(feature = "tune")]
1871#[cfg(not(feature = "parallel"))]
1872const DEFAULT_SPLIT_PAIRS: usize = usize::MAX;
1873
1874struct Scratch {
1877 atom: Vec<u32>,
1878 js: Vec<u32>,
1879 d2: Vec<f64>,
1880 run_shift: Vec<[i32; 3]>,
1881 run_end: Vec<usize>,
1882}
1883
1884impl Scratch {
1885 fn new() -> Self {
1886 Self {
1887 atom: Vec::new(),
1888 js: Vec::new(),
1889 d2: Vec::new(),
1890 run_shift: Vec::new(),
1891 run_end: Vec::new(),
1892 }
1893 }
1894
1895 fn reserve_more(&mut self, extra: usize) {
1896 let need = self.js.len().saturating_add(extra);
1897 if self.js.capacity() < need {
1898 self.atom.reserve(extra);
1899 self.js.reserve(extra);
1900 self.d2.reserve(extra);
1901 }
1902 }
1903
1904 #[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
1905 fn finish(&mut self, n: usize) {
1906 debug_assert!(n <= self.js.capacity());
1907 unsafe {
1908 self.atom.set_len(n);
1909 self.js.set_len(n);
1910 self.d2.set_len(n);
1911 }
1912 }
1913
1914 fn push(&mut self, atom: u32, j: u32, d2: f64) {
1915 self.atom.push(atom);
1916 self.js.push(j);
1917 self.d2.push(d2);
1918 }
1919
1920 fn note(&mut self, before: usize, shift: [i32; 3]) {
1921 let after = self.js.len();
1922 if after > before {
1923 self.run_shift.push(shift);
1924 self.run_end.push(after);
1925 }
1926 }
1927}
1928
1929pub(crate) struct Found {
1932 images: ImageOffsets,
1933 chunks: Vec<Scratch>,
1934 half: bool,
1935 #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1937 path: Path,
1938}
1939
1940impl Found {
1941 fn rows_of(&self, chunk: &Scratch) -> usize {
1942 if self.half {
1943 chunk.js.len()
1944 } else {
1945 chunk.js.len() * 2
1946 }
1947 }
1948
1949 pub(crate) fn rows(&self) -> usize {
1951 self.chunks.iter().map(|c| self.rows_of(c)).sum()
1952 }
1953
1954 fn offsets(&self) -> Vec<usize> {
1955 let mut off = Vec::with_capacity(self.chunks.len() + 1);
1956 off.push(0usize);
1957 for chunk in &self.chunks {
1958 off.push(off.last().copied().unwrap_or(0) + self.rows_of(chunk));
1959 }
1960 off
1961 }
1962
1963 fn into_pairs(self) -> Vec<Pair> {
1964 let total = self.rows();
1965 let mut found: Vec<Pair> = Vec::with_capacity(total);
1966 unsafe {
1968 self.write_pairs(found.as_mut_ptr());
1969 found.set_len(total);
1970 }
1971 found
1972 }
1973
1974 unsafe fn write_pairs(&self, out: *mut Pair) {
1979 if self.images.0.is_some() {
1980 unsafe {
1981 self.write_rows(out, |i, j, shift, dist2| Pair {
1982 i: i as usize,
1983 j: j as usize,
1984 shift,
1985 dist2,
1986 });
1987 }
1988 return;
1989 }
1990 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1991 let words = if self.path == Path::Avx512 {
1992 RowWords::of_pair()
1993 } else {
1994 None
1995 };
1996 let base = RowPtr(out as *mut std::mem::MaybeUninit<Pair>);
1997 self.each_chunk(|t, off, chunk| {
2000 let rows = self.rows_of(chunk);
2001 if rows == 0 {
2002 return;
2003 }
2004 let dst = unsafe { std::slice::from_raw_parts_mut(base.at(off[t]), rows) };
2005 let ahead = ahead(rows, std::mem::size_of::<Pair>());
2006 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2007 if let Some(words) = words {
2008 let at = dst.as_mut_ptr();
2009 unsafe {
2013 match (self.half, ahead) {
2014 (false, true) => write_full_avx512::<true>(at, chunk, &words),
2015 (false, false) => write_full_avx512::<false>(at, chunk, &words),
2016 (true, true) => write_half_avx512::<true>(at, chunk, &words),
2017 (true, false) => write_half_avx512::<false>(at, chunk, &words),
2018 }
2019 };
2020 return;
2021 }
2022 if self.half {
2023 write_half(
2024 dst,
2025 &chunk.atom,
2026 &chunk.js,
2027 &chunk.d2,
2028 &chunk.run_shift,
2029 &chunk.run_end,
2030 ahead,
2031 );
2032 return;
2033 }
2034 write_full(
2035 dst,
2036 &chunk.atom,
2037 &chunk.js,
2038 &chunk.d2,
2039 &chunk.run_shift,
2040 &chunk.run_end,
2041 ahead,
2042 );
2043 });
2044 }
2045
2046 pub(crate) fn fill_columns(&self, out: &mut PairColumns) {
2048 let total = self.rows();
2049 out.i.clear();
2050 out.j.clear();
2051 out.shift.clear();
2052 out.dist2.clear();
2053 out.i.reserve(total);
2054 out.j.reserve(total);
2055 out.shift.reserve(total);
2056 out.dist2.reserve(total);
2057 unsafe {
2059 self.write_columns(
2060 out.i.as_mut_ptr(),
2061 out.j.as_mut_ptr(),
2062 out.shift.as_mut_ptr() as *mut i32,
2063 out.dist2.as_mut_ptr(),
2064 );
2065 out.i.set_len(total);
2066 out.j.set_len(total);
2067 out.shift.set_len(total);
2068 out.dist2.set_len(total);
2069 }
2070 }
2071
2072 pub(crate) unsafe fn write_columns(
2076 &self,
2077 i: *mut i32,
2078 j: *mut i32,
2079 shift: *mut i32,
2080 d2: *mut f64,
2081 ) {
2082 let cols = ColumnPtrs {
2083 i: RowPtr(i as *mut std::mem::MaybeUninit<i32>),
2084 j: RowPtr(j as *mut std::mem::MaybeUninit<i32>),
2085 shift: RowPtr(shift as *mut std::mem::MaybeUninit<i32>),
2086 d2: RowPtr(d2 as *mut std::mem::MaybeUninit<f64>),
2087 };
2088 self.each_chunk(|t, off, chunk| {
2089 let rows = self.rows_of(chunk);
2090 if rows == 0 {
2091 return;
2092 }
2093 let at = off[t];
2094 let (ci, cj, cs, cd) = unsafe {
2095 (
2096 std::slice::from_raw_parts_mut(cols.i.at(at), rows),
2097 std::slice::from_raw_parts_mut(cols.j.at(at), rows),
2098 std::slice::from_raw_parts_mut(cols.shift.at(3 * at), 3 * rows),
2099 std::slice::from_raw_parts_mut(cols.d2.at(at), rows),
2100 )
2101 };
2102 let ahead = ahead(rows, COLUMN_BYTES);
2103 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2104 if self.path == Path::Avx512 {
2105 unsafe {
2109 match (self.half, ahead) {
2110 (false, true) => write_columns_avx512::<true>(ci, cj, cs, cd, chunk),
2111 (false, false) => write_columns_avx512::<false>(ci, cj, cs, cd, chunk),
2112 (true, true) => write_half_columns_avx512::<true>(ci, cj, cs, cd, chunk),
2113 (true, false) => write_half_columns_avx512::<false>(ci, cj, cs, cd, chunk),
2114 }
2115 };
2116 return;
2117 }
2118 write_columns(ci, cj, cs, cd, chunk, self.half, ahead);
2119 });
2120 if self.images.0.is_some() {
2121 for at in 0..self.rows() {
2122 unsafe {
2124 let old = [
2125 *shift.add(3 * at),
2126 *shift.add(3 * at + 1),
2127 *shift.add(3 * at + 2),
2128 ];
2129 let corrected =
2130 self.images
2131 .shift(*i.add(at) as usize, *j.add(at) as usize, old);
2132 for (a, value) in corrected.into_iter().enumerate() {
2133 *shift.add(3 * at + a) = value;
2134 }
2135 }
2136 }
2137 }
2138 }
2139
2140 #[cfg_attr(not(feature = "capi"), allow(dead_code))]
2145 pub(crate) unsafe fn write_rows<R, F>(&self, out: *mut R, row: F)
2146 where
2147 R: Send,
2148 F: Fn(i32, i32, [i32; 3], f64) -> R + Sync,
2149 {
2150 let base = RowPtr(out as *mut std::mem::MaybeUninit<R>);
2151 self.each_chunk(|t, off, chunk| {
2152 let rows = self.rows_of(chunk);
2153 if rows == 0 {
2154 return;
2155 }
2156 let dst = unsafe { std::slice::from_raw_parts_mut(base.at(off[t]), rows) };
2157 let ahead = ahead(rows, std::mem::size_of::<R>());
2158 let mut at = 0usize;
2159 let mut lo = 0usize;
2160 for (r, &hi) in chunk.run_end.iter().enumerate() {
2161 for k in lo..hi {
2162 let a = chunk.atom[k] as i32;
2163 let b = chunk.js[k] as i32;
2164 let shift = self
2165 .images
2166 .shift(a as usize, b as usize, chunk.run_shift[r]);
2167 let neg = [-shift[0], -shift[1], -shift[2]];
2168 let d = chunk.d2[k];
2169 if ahead {
2170 prefetch(dst.as_ptr().wrapping_add(at + AHEAD_ROWS));
2171 if !self.half {
2172 prefetch(dst.as_ptr().wrapping_add(at + AHEAD_ROWS + 1));
2173 }
2174 }
2175 if self.half {
2176 if keep_half(a as usize, b as usize, shift) {
2177 dst[at].write(row(a, b, shift, d));
2178 } else {
2179 dst[at].write(row(b, a, neg, d));
2180 }
2181 at += 1;
2182 } else {
2183 dst[at].write(row(a, b, shift, d));
2184 dst[at + 1].write(row(b, a, neg, d));
2185 at += 2;
2186 }
2187 }
2188 lo = hi;
2189 }
2190 });
2191 }
2192
2193 fn each_chunk<F>(&self, job: F)
2196 where
2197 F: Fn(usize, &[usize], &Scratch) + Sync,
2198 {
2199 let off = self.offsets();
2200 #[cfg(feature = "parallel")]
2201 if self.chunks.len() > 1 {
2202 if self.chunks.len() <= crate::pool_width() {
2205 rayon::broadcast(|ctx| {
2206 if let Some(chunk) = self.chunks.get(ctx.index()) {
2207 let _timer = crate::pop::JobTimer::new();
2208 job(ctx.index(), &off, chunk);
2209 }
2210 });
2211 } else {
2212 use rayon::prelude::*;
2213 self.chunks.par_iter().enumerate().for_each(|(t, chunk)| {
2214 let _timer = crate::pop::JobTimer::new();
2215 job(t, &off, chunk);
2216 });
2217 }
2218 return;
2219 }
2220 for (t, chunk) in self.chunks.iter().enumerate() {
2221 let _timer = crate::pop::JobTimer::new();
2222 job(t, &off, chunk);
2223 }
2224 }
2225}
2226
2227struct RowPtr<T>(*mut std::mem::MaybeUninit<T>);
2231impl<T> Clone for RowPtr<T> {
2232 fn clone(&self) -> Self {
2233 *self
2234 }
2235}
2236impl<T> Copy for RowPtr<T> {}
2237unsafe impl<T: Send> Send for RowPtr<T> {}
2238unsafe impl<T: Send> Sync for RowPtr<T> {}
2239impl<T> RowPtr<T> {
2240 unsafe fn at(self, index: usize) -> *mut std::mem::MaybeUninit<T> {
2241 self.0.add(index)
2242 }
2243
2244 fn ptr(self) -> *mut T {
2247 self.0 as *mut T
2248 }
2249}
2250
2251#[derive(Clone, Copy)]
2252struct ColumnPtrs {
2253 i: RowPtr<i32>,
2254 j: RowPtr<i32>,
2255 shift: RowPtr<i32>,
2256 d2: RowPtr<f64>,
2257}
2258
2259const AHEAD_ROWS: usize = 52;
2264
2265const AHEAD_FROM: usize = 3 << 20;
2268
2269#[cfg(test)]
2272static AHEAD_TEST: std::sync::atomic::AtomicU8 = std::sync::atomic::AtomicU8::new(0);
2273#[cfg(test)]
2275static FUSED_FILLS: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
2276
2277fn ahead(rows: usize, bytes: usize) -> bool {
2279 #[cfg(test)]
2280 match AHEAD_TEST.load(std::sync::atomic::Ordering::Relaxed) {
2281 1 => return false,
2282 2 => return true,
2283 _ => {}
2284 }
2285 rows.saturating_mul(bytes) >= knobs::ahead_from()
2286}
2287
2288const COLUMN_BYTES: usize =
2290 2 * std::mem::size_of::<i32>() + std::mem::size_of::<[i32; 3]>() + std::mem::size_of::<f64>();
2291
2292#[inline(always)]
2295fn prefetch<T>(p: *const T) {
2296 #[cfg(target_arch = "x86_64")]
2297 unsafe {
2300 std::arch::x86_64::_mm_prefetch::<{ std::arch::x86_64::_MM_HINT_ET0 }>(p as *const i8)
2305 };
2306 #[cfg(not(target_arch = "x86_64"))]
2307 let _ = p;
2308}
2309
2310#[inline(never)]
2311fn write_columns(
2312 ci: &mut [std::mem::MaybeUninit<i32>],
2313 cj: &mut [std::mem::MaybeUninit<i32>],
2314 cs: &mut [std::mem::MaybeUninit<i32>],
2315 cd: &mut [std::mem::MaybeUninit<f64>],
2316 chunk: &Scratch,
2317 half: bool,
2318 ahead: bool,
2319) {
2320 let mut out = 0usize;
2321 let mut lo = 0usize;
2322 for (r, &hi) in chunk.run_end.iter().enumerate() {
2323 let shift = chunk.run_shift[r];
2324 let neg = [-shift[0], -shift[1], -shift[2]];
2325 for k in lo..hi {
2326 let a = chunk.atom[k] as i32;
2327 let b = chunk.js[k] as i32;
2328 let d = chunk.d2[k];
2329 if ahead && out % 8 == 0 {
2332 let at = out + AHEAD_ROWS;
2333 prefetch(ci.as_ptr().wrapping_add(at));
2334 prefetch(cj.as_ptr().wrapping_add(at));
2335 prefetch(cd.as_ptr().wrapping_add(at));
2336 prefetch(cs.as_ptr().wrapping_add(3 * at));
2337 prefetch(cs.as_ptr().wrapping_add(3 * at + 16));
2338 }
2339 if half {
2340 let (i, j, s) = if keep_half(a as usize, b as usize, shift) {
2341 (a, b, shift)
2342 } else {
2343 (b, a, neg)
2344 };
2345 ci[out].write(i);
2346 cj[out].write(j);
2347 cs[3 * out].write(s[0]);
2348 cs[3 * out + 1].write(s[1]);
2349 cs[3 * out + 2].write(s[2]);
2350 cd[out].write(d);
2351 out += 1;
2352 } else {
2353 ci[out].write(a);
2354 cj[out].write(b);
2355 cs[3 * out].write(shift[0]);
2356 cs[3 * out + 1].write(shift[1]);
2357 cs[3 * out + 2].write(shift[2]);
2358 cd[out].write(d);
2359 ci[out + 1].write(b);
2360 cj[out + 1].write(a);
2361 cs[3 * out + 3].write(neg[0]);
2362 cs[3 * out + 4].write(neg[1]);
2363 cs[3 * out + 5].write(neg[2]);
2364 cd[out + 1].write(d);
2365 out += 2;
2366 }
2367 }
2368 lo = hi;
2369 }
2370}
2371
2372#[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
2374const STORE_SLACK: usize = 16;
2375
2376#[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
2378const MAX_SCRATCH: usize = 1 << 20;
2379
2380#[inline(never)]
2381fn write_full(
2382 dst: &mut [std::mem::MaybeUninit<Pair>],
2383 atom: &[u32],
2384 js: &[u32],
2385 d2: &[f64],
2386 shifts: &[[i32; 3]],
2387 ends: &[usize],
2388 ahead: bool,
2389) {
2390 let dp = dst.as_mut_ptr();
2391 let ap = atom.as_ptr();
2392 let jp = js.as_ptr();
2393 let yp = d2.as_ptr();
2394 let mut out = 0usize;
2395 let mut lo = 0usize;
2396 for (r, &hi) in ends.iter().enumerate() {
2397 let shift = shifts[r];
2398 let neg = [-shift[0], -shift[1], -shift[2]];
2399 for k in lo..hi {
2400 unsafe {
2401 let i = (*ap.add(k)) as usize;
2402 let j = (*jp.add(k)) as usize;
2403 let dist2 = *yp.add(k);
2404 if ahead {
2405 prefetch(dp.add(out).wrapping_add(AHEAD_ROWS));
2408 prefetch(dp.add(out).wrapping_add(AHEAD_ROWS + 1));
2409 }
2410 (*dp.add(out)).write(Pair { i, j, shift, dist2 });
2411 (*dp.add(out + 1)).write(Pair {
2412 i: j,
2413 j: i,
2414 shift: neg,
2415 dist2,
2416 });
2417 }
2418 out += 2;
2419 }
2420 lo = hi;
2421 }
2422}
2423
2424#[inline(never)]
2425fn write_half(
2426 dst: &mut [std::mem::MaybeUninit<Pair>],
2427 atom: &[u32],
2428 js: &[u32],
2429 d2: &[f64],
2430 shifts: &[[i32; 3]],
2431 ends: &[usize],
2432 ahead: bool,
2433) {
2434 let dp = dst.as_mut_ptr();
2435 let ap = atom.as_ptr();
2436 let jp = js.as_ptr();
2437 let yp = d2.as_ptr();
2438 let mut out = 0usize;
2439 let mut lo = 0usize;
2440 for (r, &hi) in ends.iter().enumerate() {
2441 let shift = shifts[r];
2442 let neg = [-shift[0], -shift[1], -shift[2]];
2443 for k in lo..hi {
2444 unsafe {
2445 let i = (*ap.add(k)) as usize;
2446 let j = (*jp.add(k)) as usize;
2447 let dist2 = *yp.add(k);
2448 if ahead {
2449 prefetch(dp.add(out).wrapping_add(AHEAD_ROWS));
2450 }
2451 let pair = if keep_half(i, j, shift) {
2452 Pair { i, j, shift, dist2 }
2453 } else {
2454 Pair {
2455 i: j,
2456 j: i,
2457 shift: neg,
2458 dist2,
2459 }
2460 };
2461 (*dp.add(out)).write(pair);
2462 }
2463 out += 1;
2464 }
2465 lo = hi;
2466 }
2467}
2468
2469#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2472#[derive(Clone, Copy)]
2473struct RowWords {
2474 index: [[u64; 8]; 5],
2476 index32: [[[u32; 16]; 5]; 2],
2479 half32: [[[u32; 16]; 5]; 2],
2483 rows_ij: [[u32; 16]; 5],
2490 rows_keep: [u16; 5],
2491 rows_s: [[u32; 16]; 5],
2492 rows_n: [[u32; 16]; 5],
2493}
2494
2495#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2499static MIRROR32: [[u16; 5]; 256] = mirror_masks(10);
2500
2501#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2504static MIRROR3: [u32; 256] = {
2505 let m = mirror_masks(3);
2506 let mut out = [0u32; 256];
2507 let mut b = 0;
2508 while b < 256 {
2509 out[b] = m[b][0] as u32 | ((m[b][1] as u32 & 0xff) << 16);
2510 b += 1;
2511 }
2512 out
2513};
2514
2515#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2518const fn mirror_masks(dwords: usize) -> [[u16; 5]; 256] {
2519 let mut out = [[0u16; 5]; 256];
2520 let mut b = 0;
2521 while b < 256 {
2522 let mut t = 0;
2523 while t < 80 {
2524 let row = t / dwords;
2525 if row < 8 && (b >> row) & 1 == 1 {
2526 out[b][t / 16] |= 1 << (t % 16);
2527 }
2528 t += 1;
2529 }
2530 b += 1;
2531 }
2532 out
2533}
2534
2535#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2536impl RowWords {
2537 fn of_pair() -> Option<Self> {
2540 let p = Pair {
2541 i: 0,
2542 j: 0,
2543 shift: [0; 3],
2544 dist2: 0.0,
2545 };
2546 let base = &p as *const Pair as usize;
2547 let at = |a: usize| a - base;
2548 let off = [
2549 at(&p.i as *const usize as usize),
2550 at(&p.j as *const usize as usize),
2551 at(&p.dist2 as *const f64 as usize),
2552 at(&p.shift as *const [i32; 3] as usize),
2553 ];
2554 if std::mem::size_of::<Pair>() != 40 || off.iter().any(|o| o % 8 != 0) {
2555 return None;
2556 }
2557 let (wi, wj, wd, ws) = (off[0] / 8, off[1] / 8, off[2] / 8, off[3] / 8);
2558 let mut seen = [false; 5];
2559 for w in [wi, wj, wd, ws, ws + 1] {
2560 if w >= 5 || seen[w] {
2561 return None;
2562 }
2563 seen[w] = true;
2564 }
2565 let mut index = [[0u64; 8]; 5];
2568 let mut index32 = [[[0u32; 16]; 5]; 2];
2571 for r in 0..8 {
2572 let (k, mirror) = ((r / 2) as u64, r % 2 == 1);
2573 let mut row = [0u64; 5];
2574 row[wi] = if mirror { 4 + k } else { k };
2575 row[wj] = if mirror { k } else { 4 + k };
2576 row[wd] = 8 + k;
2577 row[ws] = if mirror { 14 } else { 12 };
2578 row[ws + 1] = if mirror { 15 } else { 13 };
2579 for (w, &v) in row.iter().enumerate() {
2580 let t = 5 * r + w;
2581 index[t / 8][t % 8] = v;
2582 }
2583 for (g, table) in index32.iter_mut().enumerate() {
2584 let h = (4 * g + r / 2) as u32;
2585 let mut row = [[0u32; 2]; 5];
2586 row[wi] = if mirror { [h, 9] } else { [8, 9] };
2587 row[wj] = if mirror { [8, 9] } else { [h, 9] };
2588 row[wd] = [16 + 2 * h, 17 + 2 * h];
2589 row[ws] = if mirror { [13, 14] } else { [10, 11] };
2590 row[ws + 1] = if mirror { [15, 9] } else { [12, 9] };
2591 for (w, pair) in row.iter().enumerate() {
2592 for (half, &v) in pair.iter().enumerate() {
2593 let q = 10 * r + 2 * w + half;
2594 table[q / 16][q % 16] = v;
2595 }
2596 }
2597 }
2598 }
2599 let mut half32 = [[[0u32; 16]; 5]; 2];
2601 for (side, table) in half32.iter_mut().enumerate() {
2602 let mirror = side == 1;
2603 for h in 0..8u32 {
2604 let mut row = [[0u32; 2]; 5];
2605 row[wi] = if mirror { [h, 9] } else { [8, 9] };
2606 row[wj] = if mirror { [8, 9] } else { [h, 9] };
2607 row[wd] = [16 + 2 * h, 17 + 2 * h];
2608 row[ws] = if mirror { [13, 14] } else { [10, 11] };
2609 row[ws + 1] = if mirror { [15, 9] } else { [12, 9] };
2610 for (w, pair) in row.iter().enumerate() {
2611 for (half, &v) in pair.iter().enumerate() {
2612 let q = 10 * h as usize + 2 * w + half;
2613 table[q / 16][q % 16] = v;
2614 }
2615 }
2616 }
2617 }
2618 let mut rows_ij = [[0u32; 16]; 5];
2619 let mut rows_keep = [0u16; 5];
2620 let mut rows_s = [[6u32; 16]; 5];
2621 let mut rows_n = [[6u32; 16]; 5];
2622 for h in 0..8u32 {
2623 let at = |w: usize, half: usize| {
2624 let q = 10 * h as usize + 2 * w + half;
2625 (q / 16, q % 16)
2626 };
2627 for (w, src) in [(wi, h), (wj, 8 + h)] {
2628 let (m, d) = at(w, 0);
2629 rows_ij[m][d] = src;
2630 rows_keep[m] |= 1 << d;
2631 }
2632 for half in 0..2 {
2633 let (m, d) = at(wd, half);
2634 rows_ij[m][d] = 16 + 2 * h + half as u32;
2635 rows_keep[m] |= 1 << d;
2636 }
2637 for (w, half, k) in [(ws, 0, 0u32), (ws, 1, 1), (ws + 1, 0, 2)] {
2638 let (m, d) = at(w, half);
2639 rows_s[m][d] = k;
2640 rows_n[m][d] = 3 + k;
2641 }
2642 }
2643 Some(Self {
2644 index,
2645 index32,
2646 half32,
2647 rows_ij,
2648 rows_keep,
2649 rows_s,
2650 rows_n,
2651 })
2652 }
2653}
2654
2655#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2657fn shift_words(s: [i32; 3]) -> (u64, u64) {
2658 (
2659 u64::from(s[0] as u32) | (u64::from(s[1] as u32) << 32),
2660 u64::from(s[2] as u32),
2661 )
2662}
2663
2664#[allow(clippy::incompatible_msrv)]
2670#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2671#[target_feature(enable = "avx512f")]
2672#[inline(never)]
2673unsafe fn write_full_avx512<const AHEAD: bool>(
2674 dst: *mut std::mem::MaybeUninit<Pair>,
2675 chunk: &Scratch,
2676 words: &RowWords,
2677) {
2678 use std::arch::x86_64::{
2679 __m128i, __m512i, _mm256_cvtepu32_epi64, _mm256_set_epi64x, _mm512_castsi256_si512,
2680 _mm512_inserti64x4, _mm512_loadu_si512, _mm512_permutex2var_epi64, _mm512_storeu_si512,
2681 _mm_loadu_si128,
2682 };
2683 let idx: [__m512i; 5] = [
2684 _mm512_loadu_si512(words.index[0].as_ptr() as *const _),
2685 _mm512_loadu_si512(words.index[1].as_ptr() as *const _),
2686 _mm512_loadu_si512(words.index[2].as_ptr() as *const _),
2687 _mm512_loadu_si512(words.index[3].as_ptr() as *const _),
2688 _mm512_loadu_si512(words.index[4].as_ptr() as *const _),
2689 ];
2690 let ap = chunk.atom.as_ptr();
2691 let jp = chunk.js.as_ptr();
2692 let dp = chunk.d2.as_ptr();
2693 let mut row = dst;
2694 let mut lo = 0usize;
2695 for (r, &hi) in chunk.run_end.iter().enumerate() {
2696 let shift = chunk.run_shift[r];
2697 let neg = [-shift[0], -shift[1], -shift[2]];
2698 let (s01, s2) = shift_words(shift);
2699 let (n01, n2) = shift_words(neg);
2700 let sh = _mm256_set_epi64x(n2 as i64, n01 as i64, s2 as i64, s01 as i64);
2701 let mut k = lo;
2702 while k + 4 <= hi {
2703 let a = _mm256_cvtepu32_epi64(_mm_loadu_si128(ap.add(k) as *const __m128i));
2704 let b = _mm256_cvtepu32_epi64(_mm_loadu_si128(jp.add(k) as *const __m128i));
2705 let ab = _mm512_inserti64x4(_mm512_castsi256_si512(a), b, 1);
2706 let d = _mm512_loadu_si512(dp.add(k) as *const _);
2707 let ds = _mm512_inserti64x4(d, sh, 1);
2708 let out = row as *mut u64;
2709 for (m, ix) in idx.iter().enumerate() {
2710 if AHEAD {
2711 prefetch(out.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
2712 }
2713 _mm512_storeu_si512(
2714 out.add(8 * m) as *mut _,
2715 _mm512_permutex2var_epi64(ab, *ix, ds),
2716 );
2717 }
2718 row = row.add(8);
2719 k += 4;
2720 }
2721 while k < hi {
2722 let i = *ap.add(k) as usize;
2723 let j = *jp.add(k) as usize;
2724 let dist2 = *dp.add(k);
2725 (*row).write(Pair { i, j, shift, dist2 });
2726 (*row.add(1)).write(Pair {
2727 i: j,
2728 j: i,
2729 shift: neg,
2730 dist2,
2731 });
2732 row = row.add(2);
2733 k += 1;
2734 }
2735 lo = hi;
2736 }
2737}
2738
2739#[allow(clippy::incompatible_msrv)]
2745#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2746#[target_feature(enable = "avx512f")]
2747#[inline(never)]
2748unsafe fn write_columns_avx512<const AHEAD: bool>(
2749 ci: &mut [std::mem::MaybeUninit<i32>],
2750 cj: &mut [std::mem::MaybeUninit<i32>],
2751 cs: &mut [std::mem::MaybeUninit<i32>],
2752 cd: &mut [std::mem::MaybeUninit<f64>],
2753 chunk: &Scratch,
2754) {
2755 use std::arch::x86_64::{
2756 __m256i, _mm256_loadu_si256, _mm512_castsi256_si512, _mm512_loadu_pd, _mm512_loadu_si512,
2757 _mm512_permutex2var_epi32, _mm512_permutexvar_epi32, _mm512_permutexvar_pd,
2758 _mm512_setr_epi32, _mm512_setr_epi64, _mm512_storeu_pd, _mm512_storeu_si512,
2759 };
2760 let ab = _mm512_setr_epi32(0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23);
2762 let ba = _mm512_setr_epi32(16, 0, 17, 1, 18, 2, 19, 3, 20, 4, 21, 5, 22, 6, 23, 7);
2763 let dup_lo = _mm512_setr_epi64(0, 0, 1, 1, 2, 2, 3, 3);
2764 let dup_hi = _mm512_setr_epi64(4, 4, 5, 5, 6, 6, 7, 7);
2765 let pat = [
2767 _mm512_setr_epi32(0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3),
2768 _mm512_setr_epi32(4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1),
2769 _mm512_setr_epi32(2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5),
2770 ];
2771 let ap = chunk.atom.as_ptr();
2772 let jp = chunk.js.as_ptr();
2773 let dp = chunk.d2.as_ptr();
2774 let ip = ci.as_mut_ptr() as *mut i32;
2775 let jo = cj.as_mut_ptr() as *mut i32;
2776 let sp = cs.as_mut_ptr() as *mut i32;
2777 let dq = cd.as_mut_ptr() as *mut f64;
2778 let mut out = 0usize;
2779 let mut lo = 0usize;
2780 for (r, &hi) in chunk.run_end.iter().enumerate() {
2781 let s = chunk.run_shift[r];
2782 let six = [
2783 s[0], s[1], s[2], -s[0], -s[1], -s[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2784 ];
2785 let src = _mm512_loadu_si512(six.as_ptr() as *const _);
2786 let sv = [
2787 _mm512_permutexvar_epi32(pat[0], src),
2788 _mm512_permutexvar_epi32(pat[1], src),
2789 _mm512_permutexvar_epi32(pat[2], src),
2790 ];
2791 let mut k = lo;
2792 while k + 8 <= hi {
2793 if AHEAD {
2794 let at = out + AHEAD_ROWS;
2795 prefetch(ip.wrapping_add(at));
2796 prefetch(jo.wrapping_add(at));
2797 prefetch(dq.wrapping_add(at));
2798 prefetch(dq.wrapping_add(at + 8));
2799 prefetch(sp.wrapping_add(3 * at));
2800 prefetch(sp.wrapping_add(3 * at + 16));
2801 prefetch(sp.wrapping_add(3 * at + 32));
2802 }
2803 let a = _mm512_castsi256_si512(_mm256_loadu_si256(ap.add(k) as *const __m256i));
2804 let b = _mm512_castsi256_si512(_mm256_loadu_si256(jp.add(k) as *const __m256i));
2805 _mm512_storeu_si512(ip.add(out) as *mut _, _mm512_permutex2var_epi32(a, ab, b));
2806 _mm512_storeu_si512(jo.add(out) as *mut _, _mm512_permutex2var_epi32(a, ba, b));
2807 let d = _mm512_loadu_pd(dp.add(k));
2808 _mm512_storeu_pd(dq.add(out), _mm512_permutexvar_pd(dup_lo, d));
2809 _mm512_storeu_pd(dq.add(out + 8), _mm512_permutexvar_pd(dup_hi, d));
2810 let so = sp.add(3 * out);
2811 _mm512_storeu_si512(so as *mut _, sv[0]);
2812 _mm512_storeu_si512(so.add(16) as *mut _, sv[1]);
2813 _mm512_storeu_si512(so.add(32) as *mut _, sv[2]);
2814 out += 16;
2815 k += 8;
2816 }
2817 while k < hi {
2818 let a = *ap.add(k) as i32;
2819 let b = *jp.add(k) as i32;
2820 let d = *dp.add(k);
2821 *ip.add(out) = a;
2822 *jo.add(out) = b;
2823 *dq.add(out) = d;
2824 *ip.add(out + 1) = b;
2825 *jo.add(out + 1) = a;
2826 *dq.add(out + 1) = d;
2827 let so = sp.add(3 * out);
2828 *so = s[0];
2829 *so.add(1) = s[1];
2830 *so.add(2) = s[2];
2831 *so.add(3) = -s[0];
2832 *so.add(4) = -s[1];
2833 *so.add(5) = -s[2];
2834 out += 2;
2835 k += 1;
2836 }
2837 lo = hi;
2838 }
2839}
2840
2841#[allow(clippy::incompatible_msrv)]
2849#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2850#[target_feature(enable = "avx512f,avx512vl")]
2851#[inline(never)]
2852unsafe fn write_half_avx512<const AHEAD: bool>(
2853 dst: *mut std::mem::MaybeUninit<Pair>,
2854 chunk: &Scratch,
2855 words: &RowWords,
2856) {
2857 use std::arch::x86_64::{
2858 __m256i, __m512i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
2859 _mm256_mask_blend_epi32, _mm512_castsi256_si512, _mm512_inserti64x4, _mm512_loadu_si512,
2860 _mm512_mask_blend_epi32, _mm512_maskz_permutex2var_epi32, _mm512_or_si512,
2861 _mm512_permutexvar_epi32, _mm512_setr_epi32, _mm512_storeu_si512, _MM_CMPINT_LT,
2862 };
2863 let load = |t: &[u32; 16]| _mm512_loadu_si512(t.as_ptr() as *const _);
2864 let ij: [__m512i; 5] = std::array::from_fn(|m| load(&words.rows_ij[m]));
2865 let ap = chunk.atom.as_ptr();
2866 let jp = chunk.js.as_ptr();
2867 let dp = chunk.d2.as_ptr();
2868 let mut out = 0usize;
2869 let mut lo = 0usize;
2870 for (r, &hi) in chunk.run_end.iter().enumerate() {
2871 let s = chunk.run_shift[r];
2872 let neg = [-s[0], -s[1], -s[2]];
2873 let self_fwd: u8 = if keep_half(0, 0, s) { 0xff } else { 0 };
2874 let six = _mm512_setr_epi32(
2875 s[0], s[1], s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2876 );
2877 let fs: [__m512i; 5] =
2878 std::array::from_fn(|m| _mm512_permutexvar_epi32(load(&words.rows_s[m]), six));
2879 let ns: [__m512i; 5] =
2880 std::array::from_fn(|m| _mm512_permutexvar_epi32(load(&words.rows_n[m]), six));
2881 let mut k = lo;
2882 while k + 8 <= hi {
2883 let a = _mm256_loadu_si256(ap.add(k) as *const __m256i);
2884 let b = _mm256_loadu_si256(jp.add(k) as *const __m256i);
2885 let fwd = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(a, b)
2888 | (_mm256_cmpeq_epi32_mask(a, b) & self_fwd);
2889 let sides = _mm512_inserti64x4::<1>(
2890 _mm512_castsi256_si512(_mm256_mask_blend_epi32(fwd, b, a)),
2891 _mm256_mask_blend_epi32(fwd, a, b),
2892 );
2893 let d = _mm512_loadu_si512(dp.add(k) as *const _);
2894 let pick = &MIRROR32[!fwd as usize];
2895 let row = dst.add(out) as *mut u64;
2896 for m in 0..5 {
2897 if AHEAD {
2898 prefetch(row.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
2899 }
2900 let v = _mm512_maskz_permutex2var_epi32(words.rows_keep[m], sides, ij[m], d);
2901 let sh = _mm512_mask_blend_epi32(pick[m], fs[m], ns[m]);
2902 _mm512_storeu_si512(row.add(8 * m) as *mut _, _mm512_or_si512(v, sh));
2903 }
2904 out += 8;
2905 k += 8;
2906 }
2907 while k < hi {
2908 let (i, j, dist2) = (*ap.add(k) as usize, *jp.add(k) as usize, *dp.add(k));
2909 let pair = if keep_half(i, j, s) {
2910 Pair {
2911 i,
2912 j,
2913 shift: s,
2914 dist2,
2915 }
2916 } else {
2917 Pair {
2918 i: j,
2919 j: i,
2920 shift: neg,
2921 dist2,
2922 }
2923 };
2924 (*dst.add(out)).write(pair);
2925 out += 1;
2926 k += 1;
2927 }
2928 lo = hi;
2929 }
2930}
2931
2932#[allow(clippy::incompatible_msrv)]
2939#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2940#[target_feature(enable = "avx512f,avx512vl")]
2941#[inline(never)]
2942unsafe fn write_half_columns_avx512<const AHEAD: bool>(
2943 ci: &mut [std::mem::MaybeUninit<i32>],
2944 cj: &mut [std::mem::MaybeUninit<i32>],
2945 cs: &mut [std::mem::MaybeUninit<i32>],
2946 cd: &mut [std::mem::MaybeUninit<f64>],
2947 chunk: &Scratch,
2948) {
2949 use std::arch::x86_64::{
2950 __m256i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
2951 _mm256_mask_blend_epi32, _mm256_storeu_si256, _mm512_castsi512_si256, _mm512_loadu_pd,
2952 _mm512_mask_blend_epi32, _mm512_permutexvar_epi32, _mm512_setr_epi32, _mm512_storeu_pd,
2953 _mm512_storeu_si512, _MM_CMPINT_LT,
2954 };
2955 let ap = chunk.atom.as_ptr();
2956 let jp = chunk.js.as_ptr();
2957 let dp = chunk.d2.as_ptr();
2958 let ip = ci.as_mut_ptr() as *mut i32;
2959 let jo = cj.as_mut_ptr() as *mut i32;
2960 let sp = cs.as_mut_ptr() as *mut i32;
2961 let dq = cd.as_mut_ptr() as *mut f64;
2962 let mut out = 0usize;
2963 let mut lo = 0usize;
2964 for (r, &hi) in chunk.run_end.iter().enumerate() {
2965 let s = chunk.run_shift[r];
2966 let neg = [-s[0], -s[1], -s[2]];
2967 let self_fwd: u8 = if keep_half(0, 0, s) { 0xff } else { 0 };
2968 let six = _mm512_setr_epi32(
2969 s[0], s[1], s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2970 );
2971 let s_lo = _mm512_permutexvar_epi32(
2974 _mm512_setr_epi32(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0),
2975 six,
2976 );
2977 let n_lo = _mm512_permutexvar_epi32(
2978 _mm512_setr_epi32(3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3),
2979 six,
2980 );
2981 let s_hi = _mm512_castsi512_si256(_mm512_permutexvar_epi32(
2982 _mm512_setr_epi32(1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0),
2983 six,
2984 ));
2985 let n_hi = _mm512_castsi512_si256(_mm512_permutexvar_epi32(
2986 _mm512_setr_epi32(4, 5, 3, 4, 5, 3, 4, 5, 3, 3, 3, 3, 3, 3, 3, 3),
2987 six,
2988 ));
2989 let mut k = lo;
2990 while k + 8 <= hi {
2991 if AHEAD {
2992 let at = out + AHEAD_ROWS;
2993 prefetch(ip.wrapping_add(at));
2994 prefetch(jo.wrapping_add(at));
2995 prefetch(dq.wrapping_add(at));
2996 prefetch(sp.wrapping_add(3 * at));
2997 prefetch(sp.wrapping_add(3 * at + 16));
2998 }
2999 let a = _mm256_loadu_si256(ap.add(k) as *const __m256i);
3000 let b = _mm256_loadu_si256(jp.add(k) as *const __m256i);
3001 let fwd = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(a, b)
3004 | (_mm256_cmpeq_epi32_mask(a, b) & self_fwd);
3005 _mm256_storeu_si256(ip.add(out) as *mut _, _mm256_mask_blend_epi32(fwd, b, a));
3006 _mm256_storeu_si256(jo.add(out) as *mut _, _mm256_mask_blend_epi32(fwd, a, b));
3007 _mm512_storeu_pd(dq.add(out), _mm512_loadu_pd(dp.add(k)));
3008 let m3 = MIRROR3[!fwd as usize];
3009 _mm512_storeu_si512(
3010 sp.add(3 * out) as *mut _,
3011 _mm512_mask_blend_epi32(m3 as u16, s_lo, n_lo),
3012 );
3013 _mm256_storeu_si256(
3014 sp.add(3 * out + 16) as *mut _,
3015 _mm256_mask_blend_epi32((m3 >> 16) as u8, s_hi, n_hi),
3016 );
3017 out += 8;
3018 k += 8;
3019 }
3020 while k < hi {
3021 let (a, b, d) = (*ap.add(k), *jp.add(k), *dp.add(k));
3022 let (i, j, t) = if keep_half(a as usize, b as usize, s) {
3023 (a, b, s)
3024 } else {
3025 (b, a, neg)
3026 };
3027 *ip.add(out) = i as i32;
3028 *jo.add(out) = j as i32;
3029 *dq.add(out) = d;
3030 let so = sp.add(3 * out);
3031 *so = t[0];
3032 *so.add(1) = t[1];
3033 *so.add(2) = t[2];
3034 out += 1;
3035 k += 1;
3036 }
3037 lo = hi;
3038 }
3039}
3040
3041const CULL_RUNS: usize = 4;
3045
3046#[cfg(test)]
3049static NO_CULL: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
3050#[cfg(test)]
3051static CULL_SKIPS: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
3052
3053fn no_cull() -> bool {
3054 #[cfg(test)]
3055 return NO_CULL.load(std::sync::atomic::Ordering::Relaxed);
3056 #[cfg(not(test))]
3057 false
3058}
3059
3060#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3072macro_rules! near_runs {
3073 ($c:expr, $block:expr, $nvec:expr, $ox:expr, $oy:expr, $oz:expr, $cut:expr, $zero:expr,
3074 $s:expr, $slot:ident, $body:block) => {{
3075 use std::arch::x86_64::{
3076 _mm512_fmadd_pd, _mm512_loadu_pd, _mm512_mask_cmp_pd_mask, _mm512_max_pd,
3077 _mm512_set1_pd, _mm512_sub_pd, _CMP_LT_OQ,
3078 };
3079 let g = $block.ig + ($s - $block.i_lo) / 4;
3080 let lo = [
3081 _mm512_set1_pd(*$c.gb[0].add(g) + $ox),
3082 _mm512_set1_pd(*$c.gb[1].add(g) + $oy),
3083 _mm512_set1_pd(*$c.gb[2].add(g) + $oz),
3084 ];
3085 let hi = [
3086 _mm512_set1_pd(*$c.gb[3].add(g) + $ox),
3087 _mm512_set1_pd(*$c.gb[4].add(g) + $oy),
3088 _mm512_set1_pd(*$c.gb[5].add(g) + $oz),
3089 ];
3090 let mut m0 = 0usize;
3091 while m0 < $nvec {
3092 let v = $block.jv + m0;
3093 let mut d2 = $zero;
3094 for ax in 0..3 {
3095 let gap = _mm512_max_pd(
3096 _mm512_max_pd(
3097 _mm512_sub_pd(_mm512_loadu_pd($c.vb[ax].add(v)), hi[ax]),
3098 _mm512_sub_pd(lo[ax], _mm512_loadu_pd($c.vb[3 + ax].add(v))),
3099 ),
3100 $zero,
3101 );
3102 d2 = _mm512_fmadd_pd(gap, gap, d2);
3103 }
3104 let valid: u8 = if $nvec - m0 >= 8 {
3105 0xff
3106 } else {
3107 ((1u32 << ($nvec - m0)) - 1) as u8
3108 };
3109 let mut near: u8 = _mm512_mask_cmp_pd_mask(valid, d2, $cut, _CMP_LT_OQ);
3110 #[cfg(test)]
3111 CULL_SKIPS.fetch_add(
3112 (valid & !near).count_ones() as usize,
3113 std::sync::atomic::Ordering::Relaxed,
3114 );
3115 while near != 0 {
3116 let $slot = $block.j_lo + 8 * (m0 + near.trailing_zeros() as usize);
3117 near &= near - 1;
3118 $body
3119 }
3120 m0 += 8;
3121 }
3122 }};
3123}
3124
3125#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3130struct FusedOut {
3131 rows: *mut u64,
3132 ci: *mut i32,
3133 cj: *mut i32,
3134 cs: *mut i32,
3135 cd: *mut f64,
3136 n: usize,
3137 limit: usize,
3140}
3141
3142#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3148const INLINE_BLOCKS: usize = 8;
3149
3150#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3153trait FusedSink {
3154 fn room(&mut self, n: usize, room: usize) -> FusedOut;
3155}
3156
3157#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3158impl FusedSink for Vec<Pair> {
3159 fn room(&mut self, n: usize, room: usize) -> FusedOut {
3160 if self.capacity() - n < room {
3161 unsafe { self.set_len(n) };
3163 self.reserve(room);
3164 }
3165 FusedOut {
3166 rows: self.as_mut_ptr() as *mut u64,
3167 ci: std::ptr::null_mut(),
3168 cj: std::ptr::null_mut(),
3169 cs: std::ptr::null_mut(),
3170 cd: std::ptr::null_mut(),
3171 n,
3172 limit: usize::MAX,
3173 }
3174 }
3175}
3176
3177#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3178impl FusedSink for PairColumns {
3179 fn room(&mut self, n: usize, room: usize) -> FusedOut {
3180 let cap = self
3181 .i
3182 .capacity()
3183 .min(self.j.capacity())
3184 .min(self.shift.capacity())
3185 .min(self.dist2.capacity());
3186 if cap - n < room {
3187 unsafe {
3189 self.i.set_len(n);
3190 self.j.set_len(n);
3191 self.shift.set_len(n);
3192 self.dist2.set_len(n);
3193 }
3194 self.i.reserve(room);
3195 self.j.reserve(room);
3196 self.shift.reserve(room);
3197 self.dist2.reserve(room);
3198 }
3199 FusedOut {
3200 rows: std::ptr::null_mut(),
3201 ci: self.i.as_mut_ptr(),
3202 cj: self.j.as_mut_ptr(),
3203 cs: self.shift.as_mut_ptr() as *mut i32,
3204 cd: self.dist2.as_mut_ptr(),
3205 n,
3206 limit: usize::MAX,
3207 }
3208 }
3209}
3210
3211#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3213struct Counter;
3214
3215#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3216impl FusedSink for Counter {
3217 fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3218 FusedOut {
3219 rows: std::ptr::null_mut(),
3220 ci: std::ptr::null_mut(),
3221 cj: std::ptr::null_mut(),
3222 cs: std::ptr::null_mut(),
3223 cd: std::ptr::null_mut(),
3224 n,
3225 limit: usize::MAX,
3226 }
3227 }
3228}
3229
3230#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3233struct FixedCols {
3234 ci: *mut i32,
3235 cj: *mut i32,
3236 cs: *mut i32,
3237 cd: *mut f64,
3238 limit: usize,
3239}
3240
3241#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3242impl FusedSink for FixedCols {
3243 fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3244 FusedOut {
3245 rows: std::ptr::null_mut(),
3246 ci: self.ci,
3247 cj: self.cj,
3248 cs: self.cs,
3249 cd: self.cd,
3250 n,
3251 limit: self.limit,
3252 }
3253 }
3254}
3255
3256#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3259struct Fixed {
3260 rows: *mut u64,
3261 limit: usize,
3262}
3263
3264#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3265impl FusedSink for Fixed {
3266 fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3267 FusedOut {
3268 rows: self.rows,
3269 ci: std::ptr::null_mut(),
3270 cj: std::ptr::null_mut(),
3271 cs: std::ptr::null_mut(),
3272 cd: std::ptr::null_mut(),
3273 n,
3274 limit: self.limit,
3275 }
3276 }
3277}
3278
3279#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3283const PLAIN: u8 = 0;
3284#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3285const COUNT: u8 = 1;
3286#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3287const BOUNDED: u8 = 2;
3288
3289#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3291const FUSED_SLACK: usize = 16;
3292
3293#[allow(clippy::incompatible_msrv)]
3306#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3307#[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
3308#[inline]
3309unsafe fn avx512_fused<
3310 const COLS: bool,
3311 const INLINED: bool,
3312 const AHEAD: bool,
3313 const HALF: bool,
3314 const MODE: u8,
3315>(
3316 c: TileCols,
3317 cut2: f64,
3318 margin: f64,
3319 block: &Block,
3320 words: &RowWords,
3321 out: &mut FusedOut,
3322) {
3323 use std::arch::x86_64::{
3324 __m256i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
3325 _mm256_mask_blend_epi32, _mm256_maskz_compress_epi32, _mm256_maskz_loadu_epi32,
3326 _mm256_set1_epi32, _mm256_storeu_si256, _mm512_add_pd, _mm512_castpd_si512,
3327 _mm512_castsi256_si512, _mm512_castsi512_si256, _mm512_loadu_pd, _mm512_loadu_si512,
3328 _mm512_mask_blend_epi32, _mm512_mask_cmp_pd_mask, _mm512_mask_set1_epi32,
3329 _mm512_mask_storeu_epi64, _mm512_maskz_compress_pd, _mm512_maskz_loadu_pd, _mm512_mul_pd,
3330 _mm512_permutex2var_epi32, _mm512_permutexvar_epi32, _mm512_permutexvar_pd,
3331 _mm512_set1_epi32, _mm512_set1_pd, _mm512_setr_epi32, _mm512_setr_epi64, _mm512_storeu_pd,
3332 _mm512_storeu_si512, _mm512_sub_pd, _CMP_LT_OQ, _MM_CMPINT_LT,
3333 };
3334 let [sx, sy, sz] = block.shift;
3335 let [ox, oy, oz] = block.delta;
3336 let shift_s = block.shift_s;
3337 let neg = [-shift_s[0], -shift_s[1], -shift_s[2]];
3338 let consts = _mm512_setr_epi32(
3340 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, shift_s[0], shift_s[1], shift_s[2], neg[0], neg[1], neg[2],
3341 );
3342 let ij = _mm512_setr_epi32(0, 16, 0, 17, 0, 18, 0, 19, 0, 20, 0, 21, 0, 22, 0, 23);
3344 let ji = _mm512_setr_epi32(16, 0, 17, 0, 18, 0, 19, 0, 20, 0, 21, 0, 22, 0, 23, 0);
3345 let dup_lo = _mm512_setr_epi64(0, 0, 1, 1, 2, 2, 3, 3);
3346 let dup_hi = _mm512_setr_epi64(4, 4, 5, 5, 6, 6, 7, 7);
3347 let six = [
3348 shift_s[0], shift_s[1], shift_s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3349 ];
3350 let six = _mm512_loadu_si512(six.as_ptr() as *const _);
3351 let sv = [
3352 _mm512_permutexvar_epi32(
3353 _mm512_setr_epi32(0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3),
3354 six,
3355 ),
3356 _mm512_permutexvar_epi32(
3357 _mm512_setr_epi32(4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1),
3358 six,
3359 ),
3360 _mm512_permutexvar_epi32(
3361 _mm512_setr_epi32(2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5),
3362 six,
3363 ),
3364 ];
3365 let cut_exact = _mm512_set1_pd(cut2);
3366 let mut n = out.n;
3367 let own_image = !block.tri && block.j_lo == block.i_lo;
3371 let self_fwd: u8 = if own_image && keep_half(0, 0, shift_s) {
3372 0xff
3373 } else {
3374 0
3375 };
3376 let (s_lo, n_lo, s_hi, n_hi) = (
3379 _mm512_permutexvar_epi32(
3380 _mm512_setr_epi32(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0),
3381 six,
3382 ),
3383 _mm512_permutexvar_epi32(
3384 _mm512_setr_epi32(3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3),
3385 six,
3386 ),
3387 _mm512_castsi512_si256(_mm512_permutexvar_epi32(
3388 _mm512_setr_epi32(1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0),
3389 six,
3390 )),
3391 _mm512_castsi512_si256(_mm512_permutexvar_epi32(
3392 _mm512_setr_epi32(4, 5, 3, 4, 5, 3, 4, 5, 3, 3, 3, 3, 3, 3, 3, 3),
3393 six,
3394 )),
3395 );
3396
3397 macro_rules! emit {
3398 ($lo:expr, $iu:expr, $d2v:expr, $jids:expr) => {{
3399 let lo: u8 = $lo;
3400 let k = lo.count_ones() as usize;
3401 if MODE == COUNT {
3402 n += if HALF { k } else { 2 * k };
3403 } else {
3404 let dc = _mm512_maskz_compress_pd(lo, $d2v);
3405 let jc = _mm256_maskz_compress_epi32(lo, $jids);
3406 if HALF {
3407 let iv8 = _mm256_set1_epi32($iu as i32);
3410 let mut fwd: u8 = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(iv8, jc);
3411 if self_fwd != 0 {
3412 fwd |= _mm256_cmpeq_epi32_mask(iv8, jc);
3413 }
3414 let mir = !fwd;
3415 if COLS {
3416 if AHEAD {
3417 let at = n + AHEAD_ROWS;
3418 prefetch(out.ci.wrapping_add(at));
3419 prefetch(out.cj.wrapping_add(at));
3420 prefetch(out.cd.wrapping_add(at));
3421 prefetch(out.cs.wrapping_add(3 * at));
3422 }
3423 let bi = _mm256_mask_blend_epi32(fwd, jc, iv8);
3424 let bj = _mm256_mask_blend_epi32(fwd, iv8, jc);
3425 let m3 = MIRROR3[mir as usize];
3426 let slo = _mm512_mask_blend_epi32(m3 as u16, s_lo, n_lo);
3427 let shi = _mm256_mask_blend_epi32((m3 >> 16) as u8, s_hi, n_hi);
3428 if MODE == BOUNDED && n + 8 > out.limit {
3433 let mut ii = [0i32; 8];
3434 let mut jj = [0i32; 8];
3435 let mut dd = [0f64; 8];
3436 let mut ss = [0i32; 24];
3437 _mm256_storeu_si256(ii.as_mut_ptr() as *mut _, bi);
3438 _mm256_storeu_si256(jj.as_mut_ptr() as *mut _, bj);
3439 _mm512_storeu_pd(dd.as_mut_ptr(), dc);
3440 _mm512_storeu_si512(ss.as_mut_ptr() as *mut _, slo);
3441 _mm256_storeu_si256(ss.as_mut_ptr().add(16) as *mut _, shi);
3442 let keep = k.min(out.limit.saturating_sub(n));
3443 for h in 0..keep {
3444 *out.ci.add(n + h) = ii[h];
3445 *out.cj.add(n + h) = jj[h];
3446 *out.cd.add(n + h) = dd[h];
3447 let dst = out.cs.add(3 * (n + h));
3448 *dst = ss[3 * h];
3449 *dst.add(1) = ss[3 * h + 1];
3450 *dst.add(2) = ss[3 * h + 2];
3451 }
3452 } else {
3453 _mm256_storeu_si256(out.ci.add(n) as *mut _, bi);
3454 _mm256_storeu_si256(out.cj.add(n) as *mut _, bj);
3455 _mm512_storeu_pd(out.cd.add(n), dc);
3456 _mm512_storeu_si512(out.cs.add(3 * n) as *mut _, slo);
3457 _mm256_storeu_si256(out.cs.add(3 * n + 16) as *mut _, shi);
3458 }
3459 } else {
3460 let at = out.rows.add(5 * n);
3461 let a = _mm512_mask_blend_epi32(
3462 0x00ff,
3463 _mm512_mask_set1_epi32(consts, 0x0100, $iu as i32),
3464 _mm512_castsi256_si512(jc),
3465 );
3466 let b = _mm512_castpd_si512(dc);
3467 let pick = &MIRROR32[mir as usize];
3468 let regs = (5 * k + 7) / 8;
3469 for m in 0..regs {
3470 if AHEAD {
3471 prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3472 }
3473 let ix = _mm512_mask_blend_epi32(
3474 pick[m],
3475 _mm512_loadu_si512(words.half32[0][m].as_ptr() as *const _),
3476 _mm512_loadu_si512(words.half32[1][m].as_ptr() as *const _),
3477 );
3478 _mm512_storeu_si512(
3479 at.add(8 * m) as *mut _,
3480 _mm512_permutex2var_epi32(a, ix, b),
3481 );
3482 }
3483 }
3484 n += k;
3485 } else {
3486 if COLS {
3487 let at = n + AHEAD_ROWS;
3488 if AHEAD {
3489 prefetch(out.ci.wrapping_add(at));
3490 prefetch(out.cj.wrapping_add(at));
3491 prefetch(out.cd.wrapping_add(at));
3492 prefetch(out.cs.wrapping_add(3 * at));
3493 }
3494 let iv = _mm512_set1_epi32($iu as i32);
3495 let jz = _mm512_castsi256_si512(jc);
3496 _mm512_storeu_si512(
3497 out.ci.add(n) as *mut _,
3498 _mm512_permutex2var_epi32(iv, ij, jz),
3499 );
3500 _mm512_storeu_si512(
3501 out.cj.add(n) as *mut _,
3502 _mm512_permutex2var_epi32(iv, ji, jz),
3503 );
3504 _mm512_storeu_pd(out.cd.add(n), _mm512_permutexvar_pd(dup_lo, dc));
3505 let so = out.cs.add(3 * n);
3506 _mm512_storeu_si512(so as *mut _, sv[0]);
3507 if k > 2 {
3508 if AHEAD {
3509 prefetch(out.cs.wrapping_add(3 * at + 16));
3510 }
3511 _mm512_storeu_si512(so.add(16) as *mut _, sv[1]);
3512 }
3513 if k > 4 {
3514 if AHEAD {
3515 prefetch(out.cd.wrapping_add(at + 8));
3516 }
3517 _mm512_storeu_pd(out.cd.add(n + 8), _mm512_permutexvar_pd(dup_hi, dc));
3518 }
3519 if k > 5 {
3520 if AHEAD {
3521 prefetch(out.cs.wrapping_add(3 * at + 32));
3522 }
3523 _mm512_storeu_si512(so.add(32) as *mut _, sv[2]);
3524 }
3525 } else {
3526 let at = out.rows.add(5 * n);
3530 let a = _mm512_mask_blend_epi32(
3531 0x00ff,
3532 _mm512_mask_set1_epi32(consts, 0x0100, $iu as i32),
3533 _mm512_castsi256_si512(jc),
3534 );
3535 let b = _mm512_castpd_si512(dc);
3536 if MODE == BOUNDED && n + 2 * k + 2 > out.limit {
3537 for g in 0..2 {
3540 let words_left = (10 * k).saturating_sub(40 * g);
3541 for (m, ix) in words.index32[g].iter().enumerate() {
3542 let valid = words_left.saturating_sub(8 * m).min(8);
3543 if valid == 0 {
3544 break;
3545 }
3546 _mm512_mask_storeu_epi64(
3547 at.add(40 * g + 8 * m) as *mut _,
3548 ((1u32 << valid) - 1) as u8,
3549 _mm512_permutex2var_epi32(
3550 a,
3551 _mm512_loadu_si512(ix.as_ptr() as *const _),
3552 b,
3553 ),
3554 );
3555 }
3556 }
3557 } else {
3558 let regs = if k >= 4 { 5 } else { (10 * k + 7) / 8 };
3561 for (m, ix) in words.index32[0].iter().enumerate().take(regs) {
3562 if AHEAD {
3563 prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3564 }
3565 _mm512_storeu_si512(
3566 at.add(8 * m) as *mut _,
3567 _mm512_permutex2var_epi32(
3568 a,
3569 _mm512_loadu_si512(ix.as_ptr() as *const _),
3570 b,
3571 ),
3572 );
3573 }
3574 if k > 4 {
3575 let at = at.add(40);
3576 let regs = if k >= 8 { 5 } else { (10 * (k - 4) + 7) / 8 };
3577 for (m, ix) in words.index32[1].iter().enumerate().take(regs) {
3578 if AHEAD {
3579 prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3580 }
3581 _mm512_storeu_si512(
3582 at.add(8 * m) as *mut _,
3583 _mm512_permutex2var_epi32(
3584 a,
3585 _mm512_loadu_si512(ix.as_ptr() as *const _),
3586 b,
3587 ),
3588 );
3589 }
3590 }
3591 }
3592 }
3593 n += 2 * k;
3594 }
3595 }
3596 }};
3597 }
3598 macro_rules! direct_vec {
3601 ($s:expr, $slot:expr, $tm:expr) => {{
3602 let s = $s;
3603 let px = *c.x.add(s) - sx;
3604 let py = *c.y.add(s) - sy;
3605 let pz = *c.z.add(s) - sz;
3606 let (bx, by, bz) = (_mm512_set1_pd(px), _mm512_set1_pd(py), _mm512_set1_pd(pz));
3607 let (jx, jy, jz) = if $tm == 0xff {
3608 (
3609 _mm512_loadu_pd(c.x.add($slot)),
3610 _mm512_loadu_pd(c.y.add($slot)),
3611 _mm512_loadu_pd(c.z.add($slot)),
3612 )
3613 } else {
3614 (
3615 _mm512_maskz_loadu_pd($tm, c.x.add($slot)),
3616 _mm512_maskz_loadu_pd($tm, c.y.add($slot)),
3617 _mm512_maskz_loadu_pd($tm, c.z.add($slot)),
3618 )
3619 };
3620 let dx = _mm512_sub_pd(jx, bx);
3621 let dy = _mm512_sub_pd(jy, by);
3622 let dz = _mm512_sub_pd(jz, bz);
3623 _mm512_add_pd(
3624 _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
3625 _mm512_mul_pd(dz, dz),
3626 )
3627 }};
3628 }
3629 macro_rules! lanes {
3632 ($s:expr, $slot:expr, $tm:expr, $jids:expr) => {{
3633 let d2v = direct_vec!($s, $slot, $tm);
3634 let lo: u8 = _mm512_mask_cmp_pd_mask($tm, d2v, cut_exact, _CMP_LT_OQ);
3635 if lo != 0 {
3636 let iu = *c.id.add($s);
3637 emit!(lo, iu, d2v, $jids);
3638 }
3639 }};
3640 }
3641 macro_rules! load {
3642 ($slot:expr, $j_hi:expr) => {{
3643 let slot = $slot;
3644 if slot + 8 <= $j_hi {
3645 (0xffu8, _mm256_loadu_si256(c.id.add(slot) as *const __m256i))
3646 } else {
3647 let tm: u8 = ((1u32 << ($j_hi - slot)) - 1) as u8;
3648 (
3649 tm,
3650 _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
3651 )
3652 }
3653 }};
3654 }
3655 let j_hi = block.j_hi;
3656 let nvec = (j_hi - block.j_lo + 7) / 8;
3657 const QUAD: usize = 4;
3664 const QUAD_CAP: usize = 192;
3665 let quad = !block.tri && block.i_hi - block.i_lo >= QUAD && j_hi - block.j_lo <= QUAD_CAP;
3666 let cull_box = !block.tri && c.cull && nvec >= CULL_RUNS;
3667 macro_rules! quad_hits {
3670 ($s0:expr, $ns:expr, $slot:expr, $cnt:expr, $idb:expr, $d2b:expr) => {{
3671 let slot = $slot;
3672 let (tm, jx, jy, jz, jids) = if slot + 8 <= j_hi {
3673 (
3674 0xffu8,
3675 _mm512_loadu_pd(c.x.add(slot)),
3676 _mm512_loadu_pd(c.y.add(slot)),
3677 _mm512_loadu_pd(c.z.add(slot)),
3678 _mm256_loadu_si256(c.id.add(slot) as *const __m256i),
3679 )
3680 } else {
3681 let tm: u8 = ((1u32 << (j_hi - slot)) - 1) as u8;
3682 (
3683 tm,
3684 _mm512_maskz_loadu_pd(tm, c.x.add(slot)),
3685 _mm512_maskz_loadu_pd(tm, c.y.add(slot)),
3686 _mm512_maskz_loadu_pd(tm, c.z.add(slot)),
3687 _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
3688 )
3689 };
3690 for k in 0..$ns {
3691 let sk = $s0 + k;
3692 let px = *c.x.add(sk) - sx;
3693 let py = *c.y.add(sk) - sy;
3694 let pz = *c.z.add(sk) - sz;
3695 let dx = _mm512_sub_pd(jx, _mm512_set1_pd(px));
3696 let dy = _mm512_sub_pd(jy, _mm512_set1_pd(py));
3697 let dz = _mm512_sub_pd(jz, _mm512_set1_pd(pz));
3698 let d2v = _mm512_add_pd(
3699 _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
3700 _mm512_mul_pd(dz, dz),
3701 );
3702 let lo: u8 = _mm512_mask_cmp_pd_mask(tm, d2v, cut_exact, _CMP_LT_OQ);
3703 if lo != 0 {
3704 let knt = lo.count_ones() as usize;
3705 let at = $cnt[k];
3706 _mm512_storeu_pd(
3707 ($d2b[k].as_mut_ptr() as *mut f64).add(at),
3708 _mm512_maskz_compress_pd(lo, d2v),
3709 );
3710 _mm256_storeu_si256(
3711 ($idb[k].as_mut_ptr() as *mut i32).add(at) as *mut _,
3712 _mm256_maskz_compress_epi32(lo, jids),
3713 );
3714 $cnt[k] = at + knt;
3715 }
3716 }
3717 }};
3718 }
3719 macro_rules! quad_flush {
3720 ($s0:expr, $ns:expr, $cnt:expr, $idb:expr, $d2b:expr) => {{
3721 for k in 0..$ns {
3722 let iu = *c.id.add($s0 + k);
3723 let mut h = 0usize;
3724 while h < $cnt[k] {
3725 let m = ($cnt[k] - h).min(8);
3726 let d2v = _mm512_loadu_pd(($d2b[k].as_ptr() as *const f64).add(h));
3727 let jids = _mm256_loadu_si256(
3728 ($idb[k].as_ptr() as *const i32).add(h) as *const __m256i
3729 );
3730 let mask = ((1u32 << m) - 1) as u8;
3731 emit!(mask, iu, d2v, jids);
3732 h += m;
3733 }
3734 }
3735 }};
3736 }
3737 if quad && cull_box {
3738 let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
3739 let zero = std::arch::x86_64::_mm512_setzero_pd();
3740 let mut s = block.i_lo;
3741 while s + QUAD <= block.i_hi {
3742 let mut cnt = [0usize; QUAD];
3743 let mut idb = [std::mem::MaybeUninit::<[i32; QUAD_CAP + 8]>::uninit(); QUAD];
3746 let mut d2b = [std::mem::MaybeUninit::<[f64; QUAD_CAP + 8]>::uninit(); QUAD];
3747 near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3748 quad_hits!(s, QUAD, slot, cnt, idb, d2b);
3749 });
3750 quad_flush!(s, QUAD, cnt, idb, d2b);
3751 s += QUAD;
3752 }
3753 for s in s..block.i_hi {
3754 near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3755 let (tm, jids) = load!(slot, j_hi);
3756 lanes!(s, slot, tm, jids);
3757 });
3758 }
3759 } else if cull_box {
3760 let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
3761 let zero = std::arch::x86_64::_mm512_setzero_pd();
3762 for s in block.i_lo..block.i_hi {
3763 near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3764 let (tm, jids) = load!(slot, j_hi);
3765 lanes!(s, slot, tm, jids);
3766 });
3767 }
3768 } else if quad {
3769 let mut s = block.i_lo;
3770 while s + QUAD <= block.i_hi {
3771 let mut cnt = [0usize; QUAD];
3772 let mut idb = [std::mem::MaybeUninit::<[i32; QUAD_CAP + 8]>::uninit(); QUAD];
3773 let mut d2b = [std::mem::MaybeUninit::<[f64; QUAD_CAP + 8]>::uninit(); QUAD];
3774 let mut slot = block.j_lo;
3775 while slot < j_hi {
3776 quad_hits!(s, QUAD, slot, cnt, idb, d2b);
3777 slot += 8;
3778 }
3779 quad_flush!(s, QUAD, cnt, idb, d2b);
3780 s += QUAD;
3781 }
3782 for s in s..block.i_hi {
3783 let mut slot = block.j_lo;
3784 while slot < j_hi {
3785 let (tm, jids) = load!(slot, j_hi);
3786 lanes!(s, slot, tm, jids);
3787 slot += 8;
3788 }
3789 }
3790 } else if !block.tri {
3791 for s in block.i_lo..block.i_hi {
3792 let mut slot = block.j_lo;
3793 while slot < j_hi {
3794 let (tm, jids) = load!(slot, j_hi);
3795 lanes!(s, slot, tm, jids);
3796 slot += 8;
3797 }
3798 }
3799 } else {
3800 for s in block.i_lo..block.i_hi {
3801 let mut slot = s + 1;
3802 while slot < j_hi {
3803 let (tm, jids) = load!(slot, j_hi);
3804 lanes!(s, slot, tm, jids);
3805 slot += 8;
3806 }
3807 }
3808 }
3809 out.n = n;
3810}
3811
3812#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3813impl Plan {
3814 fn tile_cols(&self) -> TileCols {
3815 TileCols::of(&self.grid)
3816 }
3817
3818 fn each_block_in(&self, c_lo: usize, c_hi: usize, mut visit: impl FnMut(&Block)) {
3821 for cell in c_lo..c_hi {
3822 let lo = self.grid.offsets[cell];
3823 let hi = self.grid.offsets[cell + 1];
3824 if lo == hi {
3825 continue;
3826 }
3827 if hi - lo >= 2 {
3828 visit(&Block {
3829 i_lo: lo,
3830 i_hi: hi,
3831 j_lo: lo,
3832 j_hi: hi,
3833 shift_s: [0, 0, 0],
3834 shift: [0.0; 3],
3835 delta: [0.0; 3],
3836 tri: true,
3837 jv: self.grid.boxes.vstart[cell],
3838 ig: self.grid.boxes.gstart[cell],
3839 });
3840 }
3841 let (p0, p1) = (self.partners.off[cell], self.partners.off[cell + 1]);
3842 for p in &self.partners.items[p0..p1] {
3843 let (j_lo, j_hi) = (self.grid.offsets[p.jc], self.grid.offsets[p.jc + 1]);
3844 if j_lo == j_hi {
3845 continue;
3846 }
3847 visit(&Block {
3848 i_lo: lo,
3849 i_hi: hi,
3850 j_lo,
3851 j_hi,
3852 shift_s: p.shift_s,
3853 shift: p.shift,
3854 delta: p.delta,
3855 tri: false,
3856 jv: self.grid.boxes.vstart[p.jc],
3857 ig: self.grid.boxes.gstart[cell],
3858 });
3859 }
3860 }
3861 }
3862
3863 fn block_room<const HALF: bool>(block: &Block) -> usize {
3865 let pairs = (block.i_hi - block.i_lo) * (block.j_hi - block.j_lo);
3866 if HALF {
3867 pairs + FUSED_SLACK
3868 } else {
3869 2 * pairs + FUSED_SLACK
3870 }
3871 }
3872
3873 fn fused_guess(&self) -> usize {
3876 let hits = self.walk().guess_hits(self.grid.atoms());
3877 if self.half {
3878 hits + FUSED_SLACK
3879 } else {
3880 2 * hits + FUSED_SLACK
3881 }
3882 }
3883
3884 fn fused_rows(&self, words: &RowWords) -> Vec<Pair> {
3886 let _timer = crate::pop::JobTimer::new();
3887 let guess = self.fused_guess();
3888 let mut out: Vec<Pair> = Vec::with_capacity(guess);
3889 advise_huge(&mut out);
3890 let ahead = ahead(guess, std::mem::size_of::<Pair>());
3891 let n = self.fused_sink::<false, _>(words, &mut out, ahead);
3892 unsafe { out.set_len(n) };
3894 out
3895 }
3896
3897 fn fused_into_vec(&self, words: &RowWords, out: &mut Vec<Pair>) {
3899 let _timer = crate::pop::JobTimer::new();
3900 let guess = self.fused_guess();
3901 out.clear();
3902 if out.capacity() < guess {
3903 out.reserve(guess - out.len());
3904 }
3905 advise_huge(out);
3906 let ahead = ahead(out.capacity(), std::mem::size_of::<Pair>());
3907 let n = self.fused_sink::<false, _>(words, out, ahead);
3908 unsafe { out.set_len(n) };
3910 }
3911
3912 #[cfg(feature = "parallel")]
3914 fn count_rows(&self, words: &RowWords) -> usize {
3915 let mut counter = Counter;
3916 let all = (0, self.grid.offsets.len() - 1, 0);
3917 if self.half {
3918 self.fused_side::<false, true, COUNT, _>(words, &mut counter, false, all)
3919 } else {
3920 self.fused_side::<false, false, COUNT, _>(words, &mut counter, false, all)
3921 }
3922 }
3923
3924 fn fused_sink<const COLS: bool, S: FusedSink>(
3929 &self,
3930 words: &RowWords,
3931 sink: &mut S,
3932 ahead: bool,
3933 ) -> usize {
3934 let all = (0, self.grid.offsets.len() - 1, 0);
3935 if self.half {
3936 self.fused_side::<COLS, true, PLAIN, S>(words, sink, ahead, all)
3937 } else {
3938 self.fused_side::<COLS, false, PLAIN, S>(words, sink, ahead, all)
3939 }
3940 }
3941
3942 fn fused_side<const COLS: bool, const HALF: bool, const MODE: u8, S: FusedSink>(
3945 &self,
3946 words: &RowWords,
3947 sink: &mut S,
3948 ahead: bool,
3949 range: (usize, usize, usize),
3950 ) -> usize {
3951 let cols = self.tile_cols();
3952 let inline = self.grid.atoms() < INLINE_BLOCKS * (self.grid.offsets.len() - 1);
3953 let r = range;
3954 unsafe {
3956 match (inline, ahead) {
3957 (true, false) => {
3958 self.fused_into::<COLS, false, HALF, MODE, S>(cols, words, sink, r)
3959 }
3960 (true, true) => self.fused_into::<COLS, true, HALF, MODE, S>(cols, words, sink, r),
3961 (false, false) => {
3962 self.fused_blocks::<COLS, false, HALF, MODE, S>(cols, words, sink, r)
3963 }
3964 (false, true) => {
3965 self.fused_blocks::<COLS, true, HALF, MODE, S>(cols, words, sink, r)
3966 }
3967 }
3968 }
3969 }
3970
3971 unsafe fn fused_blocks<
3976 const COLS: bool,
3977 const AHEAD: bool,
3978 const HALF: bool,
3979 const MODE: u8,
3980 S: FusedSink,
3981 >(
3982 &self,
3983 cols: TileCols,
3984 words: &RowWords,
3985 sink: &mut S,
3986 (c_lo, c_hi, n0): (usize, usize, usize),
3987 ) -> usize {
3988 let mut n = n0;
3989 self.each_block_in(c_lo, c_hi, |block| {
3990 let mut fo = sink.room(n, Self::block_room::<HALF>(block));
3991 unsafe {
3994 avx512_fused::<COLS, false, AHEAD, HALF, MODE>(
3995 cols,
3996 self.cut2,
3997 self.margin,
3998 block,
3999 words,
4000 &mut fo,
4001 )
4002 };
4003 n = fo.n;
4004 });
4005 n
4006 }
4007
4008 #[allow(clippy::incompatible_msrv)]
4016 #[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
4017 unsafe fn fused_into<
4018 const COLS: bool,
4019 const AHEAD: bool,
4020 const HALF: bool,
4021 const MODE: u8,
4022 S: FusedSink,
4023 >(
4024 &self,
4025 cols: TileCols,
4026 words: &RowWords,
4027 sink: &mut S,
4028 (c_lo, c_hi, n0): (usize, usize, usize),
4029 ) -> usize {
4030 let mut n = n0;
4031 for cell in c_lo..c_hi {
4032 let (lo, hi) = (self.grid.offsets[cell], self.grid.offsets[cell + 1]);
4033 if lo == hi {
4034 continue;
4035 }
4036 let (p0, p1) = (self.partners.off[cell], self.partners.off[cell + 1]);
4037 for q in p0..=p1 {
4038 let block = if q == p0 {
4039 if hi - lo < 2 {
4040 continue;
4041 }
4042 Block {
4043 i_lo: lo,
4044 i_hi: hi,
4045 j_lo: lo,
4046 j_hi: hi,
4047 shift_s: [0, 0, 0],
4048 shift: [0.0; 3],
4049 delta: [0.0; 3],
4050 tri: true,
4051 jv: self.grid.boxes.vstart[cell],
4052 ig: self.grid.boxes.gstart[cell],
4053 }
4054 } else {
4055 let p = &self.partners.items[q - 1];
4056 let (j_lo, j_hi) = (self.grid.offsets[p.jc], self.grid.offsets[p.jc + 1]);
4057 if j_lo == j_hi {
4058 continue;
4059 }
4060 Block {
4061 i_lo: lo,
4062 i_hi: hi,
4063 j_lo,
4064 j_hi,
4065 shift_s: p.shift_s,
4066 shift: p.shift,
4067 delta: p.delta,
4068 tri: false,
4069 jv: self.grid.boxes.vstart[p.jc],
4070 ig: self.grid.boxes.gstart[cell],
4071 }
4072 };
4073 let mut fo = sink.room(n, Self::block_room::<HALF>(&block));
4074 avx512_fused::<COLS, true, AHEAD, HALF, MODE>(
4077 cols,
4078 self.cut2,
4079 self.margin,
4080 &block,
4081 words,
4082 &mut fo,
4083 );
4084 n = fo.n;
4085 }
4086 }
4087 n
4088 }
4089
4090 #[cfg(feature = "parallel")]
4093 fn fused_split_columns(&self) -> Option<RowWords> {
4094 if self.threads > 1 && self.half && self.path == Path::Avx512 && self.images.0.is_none() {
4095 RowWords::of_pair()
4096 } else {
4097 None
4098 }
4099 }
4100
4101 #[cfg(feature = "parallel")]
4104 fn fused_split(&self) -> Option<RowWords> {
4105 if self.threads > 1 && !self.half && self.path == Path::Avx512 && self.images.0.is_none() {
4106 RowWords::of_pair()
4107 } else {
4108 None
4109 }
4110 }
4111
4112 #[cfg(feature = "parallel")]
4115 fn fused_offsets(&self, words: &RowWords, ranges: &[(usize, usize)]) -> Vec<usize> {
4116 let counts: Vec<usize> = rayon::broadcast(|ctx| {
4117 ranges.get(ctx.index()).map_or(0, |&(lo, hi)| {
4118 let _timer = crate::pop::JobTimer::new();
4119 if self.half {
4120 self.fused_side::<false, true, COUNT, _>(
4121 words,
4122 &mut Counter,
4123 false,
4124 (lo, hi, 0),
4125 )
4126 } else {
4127 self.fused_side::<false, false, COUNT, _>(
4128 words,
4129 &mut Counter,
4130 false,
4131 (lo, hi, 0),
4132 )
4133 }
4134 })
4135 });
4136 let mut off = Vec::with_capacity(ranges.len() + 1);
4137 off.push(0usize);
4138 for c in counts.iter().take(ranges.len()) {
4139 off.push(off[off.len() - 1] + c);
4140 }
4141 off
4142 }
4143
4144 #[cfg(feature = "parallel")]
4150 unsafe fn fused_fill(
4151 &self,
4152 words: &RowWords,
4153 base: RowPtr<Pair>,
4154 ranges: &[(usize, usize)],
4155 off: &[usize],
4156 ) {
4157 #[cfg(test)]
4158 FUSED_FILLS.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
4159 rayon::broadcast(|ctx| {
4160 let t = ctx.index();
4161 if let Some(&(lo, hi)) = ranges.get(t) {
4162 let _timer = crate::pop::JobTimer::new();
4163 let mut sink = Fixed {
4164 rows: base.ptr() as *mut u64,
4165 limit: off[t + 1],
4166 };
4167 let ahead = ahead(off[t + 1] - off[t], std::mem::size_of::<Pair>());
4168 let n = self.fused_side::<false, false, BOUNDED, _>(
4169 words,
4170 &mut sink,
4171 ahead,
4172 (lo, hi, off[t]),
4173 );
4174 debug_assert_eq!(n, off[t + 1]);
4175 }
4176 });
4177 }
4178
4179 #[cfg(feature = "parallel")]
4186 unsafe fn fused_fill_columns(
4187 &self,
4188 words: &RowWords,
4189 cols: ColumnPtrs,
4190 ranges: &[(usize, usize)],
4191 off: &[usize],
4192 ) {
4193 #[cfg(test)]
4194 FUSED_FILLS.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
4195 rayon::broadcast(|ctx| {
4196 let t = ctx.index();
4197 if let Some(&(lo, hi)) = ranges.get(t) {
4198 let _timer = crate::pop::JobTimer::new();
4199 let mut sink = FixedCols {
4200 ci: cols.i.ptr(),
4201 cj: cols.j.ptr(),
4202 cs: cols.shift.ptr(),
4203 cd: cols.d2.ptr(),
4204 limit: off[t + 1],
4205 };
4206 let ahead = ahead(off[t + 1] - off[t], COLUMN_BYTES);
4207 let n = self.fused_side::<true, true, BOUNDED, _>(
4208 words,
4209 &mut sink,
4210 ahead,
4211 (lo, hi, off[t]),
4212 );
4213 debug_assert_eq!(n, off[t + 1]);
4214 }
4215 });
4216 }
4217
4218 fn fused_columns(&self, out: &mut PairColumns) {
4220 let _timer = crate::pop::JobTimer::new();
4221 let words = match RowWords::of_pair() {
4222 Some(w) => w,
4223 None => return self.search().fill_columns(out),
4224 };
4225 out.i.clear();
4226 out.j.clear();
4227 out.shift.clear();
4228 out.dist2.clear();
4229 let guess = self.fused_guess();
4230 out.i.reserve(guess);
4231 out.j.reserve(guess);
4232 out.shift.reserve(guess);
4233 out.dist2.reserve(guess);
4234 out.advise_huge();
4235 let n = self.fused_sink::<true, _>(&words, out, ahead(guess, COLUMN_BYTES));
4236 unsafe {
4238 out.i.set_len(n);
4239 out.j.set_len(n);
4240 out.shift.set_len(n);
4241 out.dist2.set_len(n);
4242 }
4243 }
4244}
4245
4246impl Walk<'_> {
4247 fn scan_block(&self, scratch: &mut Scratch, block: &Block) {
4248 if block.i_lo >= block.i_hi || block.j_lo >= block.j_hi {
4249 return;
4250 }
4251 let ns = block.i_hi - block.i_lo;
4252 let span = block.j_hi - block.j_lo;
4253 if span < 8 || ns < 4 || ns > MAX_SCRATCH / span {
4257 self.scan_scalar(scratch, block);
4258 return;
4259 }
4260 let before = scratch.js.len();
4261 scratch.reserve_more(ns * span + STORE_SLACK);
4262 match self.path {
4263 #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
4264 Path::Avx512 => {
4265 let cols = TileCols::of(self.grid);
4266 unsafe {
4268 avx512_scan(cols, self.cut2, self.margin, block, scratch);
4269 }
4270 }
4271 #[cfg(target_arch = "x86_64")]
4272 Path::Avx2 => {
4273 let cols = TileCols::of(self.grid);
4274 unsafe {
4276 wide::avx2_scan(cols, self.cut2, self.margin, block, scratch);
4277 }
4278 }
4279 #[cfg(target_arch = "aarch64")]
4280 Path::Neon => {
4281 let cols = TileCols::of(self.grid);
4282 unsafe {
4284 wide::neon_scan(cols, self.cut2, self.margin, block, scratch);
4285 }
4286 }
4287 _ => {
4288 self.scan_scalar(scratch, block);
4289 return;
4290 }
4291 }
4292 scratch.note(before, block.shift_s);
4293 }
4294
4295 fn scan_scalar(&self, scratch: &mut Scratch, block: &Block) {
4296 let before = scratch.js.len();
4297 let sx = block.shift[0];
4298 let sy = block.shift[1];
4299 let sz = block.shift[2];
4300 for s in block.i_lo..block.i_hi {
4301 let j_lo = if block.tri { s + 1 } else { block.j_lo };
4302 if j_lo >= block.j_hi {
4303 continue;
4304 }
4305 let c = &self.grid.coords;
4306 let i = c.id[s];
4307 let px = c.x[s] - sx;
4308 let py = c.y[s] - sy;
4309 let pz = c.z[s] - sz;
4310 for slot in j_lo..block.j_hi {
4311 let dx = c.x[slot] - px;
4312 let dy = c.y[slot] - py;
4313 let dz = c.z[slot] - pz;
4314 let d2 = dx * dx + dy * dy + dz * dz;
4315 if d2 < self.cut2 {
4316 let j = c.id[slot];
4317 if j == i && block.shift_s == [0, 0, 0] {
4318 continue;
4319 }
4320 scratch.push(i, j, d2);
4321 }
4322 }
4323 }
4324 scratch.note(before, block.shift_s);
4325 }
4326
4327 fn append_cell(&self, scratch: &mut Scratch, cell: usize) {
4328 let lo = self.grid.offsets[cell];
4329 let hi = self.grid.offsets[cell + 1];
4330 if lo == hi {
4331 return;
4332 }
4333 if hi - lo >= 2 {
4334 self.scan_block(
4335 scratch,
4336 &Block {
4337 i_lo: lo,
4338 i_hi: hi,
4339 j_lo: lo,
4340 j_hi: hi,
4341 shift_s: [0, 0, 0],
4342 shift: [0.0; 3],
4343 delta: [0.0; 3],
4344 tri: true,
4345 jv: self.grid.boxes.vstart[cell],
4346 ig: self.grid.boxes.gstart[cell],
4347 },
4348 );
4349 }
4350 let p0 = self.partners.off[cell];
4351 let p1 = self.partners.off[cell + 1];
4352 for partner in &self.partners.items[p0..p1] {
4353 let (j_lo, j_hi) = (
4354 self.grid.offsets[partner.jc],
4355 self.grid.offsets[partner.jc + 1],
4356 );
4357 if j_lo == j_hi {
4358 continue;
4359 }
4360 self.scan_block(
4361 scratch,
4362 &Block {
4363 i_lo: lo,
4364 i_hi: hi,
4365 j_lo,
4366 j_hi,
4367 shift_s: partner.shift_s,
4368 shift: partner.shift,
4369 delta: partner.delta,
4370 tri: false,
4371 jv: self.grid.boxes.vstart[partner.jc],
4372 ig: self.grid.boxes.gstart[cell],
4373 },
4374 );
4375 }
4376 }
4377
4378 fn guess_hits(&self, n_src: usize) -> usize {
4381 let w = self.grid.widths;
4382 let full = (w[0] * w[1] * w[2]).max(1.0e-30);
4383 let radius = self.cut2.sqrt();
4384 let shell = 4.1887902047863905 * radius * radius * radius;
4385 let n = self.grid.atoms().max(1) as f64;
4386 let volume = full * self.occupied_fraction();
4390 let neighbors = (n * shell / volume).ceil().max(1.0).min(n);
4391 ((n_src as f64) * neighbors * 0.5 * 1.25) as usize
4392 }
4393
4394 fn occupied_fraction(&self) -> f64 {
4397 let nx = self.grid.n[0];
4398 let ny = self.grid.n[1];
4399 let nz = self.grid.n[2];
4400 if nx <= 0 || ny <= 0 || nz <= 0 {
4401 return 1.0;
4402 }
4403 let ncell = (nx as usize) * (ny as usize) * (nz as usize);
4404 let off = &self.grid.offsets;
4405 if off.len() != ncell + 1 {
4406 return 1.0;
4407 }
4408 let mut min = [i32::MAX; 3];
4409 let mut max = [i32::MIN; 3];
4410 let mut any = false;
4411 for c in 0..ncell {
4412 if off[c + 1] == off[c] {
4413 continue;
4414 }
4415 any = true;
4416 let ix = (c % nx as usize) as i32;
4417 let iy = ((c / nx as usize) % ny as usize) as i32;
4418 let iz = (c / (nx as usize * ny as usize)) as i32;
4419 min[0] = min[0].min(ix);
4420 min[1] = min[1].min(iy);
4421 min[2] = min[2].min(iz);
4422 max[0] = max[0].max(ix);
4423 max[1] = max[1].max(iy);
4424 max[2] = max[2].max(iz);
4425 }
4426 if !any {
4427 return 1.0;
4428 }
4429 let span = [
4430 (max[0] - min[0] + 1) as f64 / f64::from(nx),
4431 (max[1] - min[1] + 1) as f64 / f64::from(ny),
4432 (max[2] - min[2] + 1) as f64 / f64::from(nz),
4433 ];
4434 (span[0] * span[1] * span[2]).clamp(1.0 / ncell as f64, 1.0)
4435 }
4436
4437 fn fill_range(&self, start: usize, end: usize) -> Scratch {
4438 let _timer = crate::pop::JobTimer::new();
4439 let mut scratch = Scratch::new();
4440 let n_src = self.grid.offsets[end] - self.grid.offsets[start];
4441 scratch.reserve_more(self.guess_hits(n_src));
4442 for cell in start..end {
4443 self.append_cell(&mut scratch, cell);
4444 }
4445 scratch
4446 }
4447
4448 fn collect(&self, threads: usize) -> Vec<Scratch> {
4451 let ncell = self.grid.offsets.len() - 1;
4452 #[cfg(feature = "parallel")]
4453 if threads > 1 && ncell > 1 {
4454 let ranges = cell_ranges(&self.grid.offsets, threads * knobs::chunks());
4455 if ranges.len() > 1 && ranges.len() <= crate::pool_width() {
4456 let found: Vec<Option<Scratch>> = rayon::broadcast(|ctx| {
4457 ranges
4458 .get(ctx.index())
4459 .map(|&(start, end)| self.fill_range(start, end))
4460 });
4461 return found.into_iter().flatten().collect();
4462 }
4463 if ranges.len() > 1 {
4464 use rayon::prelude::*;
4465 return ranges
4466 .par_iter()
4467 .map(|&(start, end)| self.fill_range(start, end))
4468 .collect();
4469 }
4470 }
4471 let _ = threads;
4472 vec![self.fill_range(0, ncell)]
4473 }
4474}
4475
4476#[cfg(feature = "parallel")]
4477fn cell_ranges(offsets: &[usize], threads: usize) -> Vec<(usize, usize)> {
4478 let ncell = offsets.len() - 1;
4479 if ncell == 0 {
4480 return Vec::new();
4481 }
4482 let threads = threads.max(1).min(ncell);
4483 if threads == 1 {
4484 return vec![(0, ncell)];
4485 }
4486 let total = offsets[ncell];
4487 if total == 0 {
4488 return vec![(0, ncell)];
4489 }
4490 let mut ranges = Vec::with_capacity(threads);
4491 let mut start = 0usize;
4492 for t in 1..threads {
4493 let target = total * t / threads;
4494 let mut end = start;
4495 while end < ncell && offsets[end] < target {
4496 end += 1;
4497 }
4498 if end == start {
4499 end = (start + 1).min(ncell);
4500 }
4501 if end <= start {
4502 break;
4503 }
4504 ranges.push((start, end));
4505 start = end;
4506 }
4507 if start < ncell {
4508 ranges.push((start, ncell));
4509 }
4510 ranges
4511}
4512
4513#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
4515#[derive(Clone, Copy)]
4516struct TileCols {
4517 x: *const f64,
4518 y: *const f64,
4519 z: *const f64,
4520 rx: *const f64,
4521 ry: *const f64,
4522 rz: *const f64,
4523 r2: *const f64,
4524 id: *const u32,
4525 cull: bool,
4526 vb: [*const f64; 6],
4527 gb: [*const f64; 6],
4528}
4529
4530#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
4531impl TileCols {
4532 fn of(grid: &Grid) -> Self {
4533 let c = &grid.coords;
4534 let b = &grid.boxes;
4535 TileCols {
4536 x: c.x.as_ptr(),
4537 y: c.y.as_ptr(),
4538 z: c.z.as_ptr(),
4539 rx: c.rx.as_ptr(),
4540 ry: c.ry.as_ptr(),
4541 rz: c.rz.as_ptr(),
4542 r2: c.r2.as_ptr(),
4543 id: c.id.as_ptr(),
4544 cull: b.on,
4545 vb: std::array::from_fn(|k| b.v[k].as_ptr()),
4546 gb: std::array::from_fn(|k| b.g[k].as_ptr()),
4547 }
4548 }
4549}
4550
4551#[allow(clippy::incompatible_msrv)]
4562#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
4563#[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
4564#[inline(never)]
4565unsafe fn avx512_scan(c: TileCols, cut2: f64, margin: f64, block: &Block, scratch: &mut Scratch) {
4566 use std::arch::x86_64::{
4567 __m256i, _mm256_loadu_si256, _mm256_maskz_compress_epi32, _mm256_maskz_loadu_epi32,
4568 _mm256_set1_epi32, _mm256_storeu_si256, _mm512_add_pd, _mm512_fmadd_pd, _mm512_loadu_pd,
4569 _mm512_mask_cmp_pd_mask, _mm512_maskz_compress_pd, _mm512_maskz_loadu_pd, _mm512_mul_pd,
4570 _mm512_set1_pd, _mm512_storeu_pd, _mm512_sub_pd, _CMP_LT_OQ,
4571 };
4572 let atom_p = scratch.atom.as_mut_ptr();
4573 let js_p = scratch.js.as_mut_ptr();
4574 let d2_p = scratch.d2.as_mut_ptr();
4575 let mut n = scratch.js.len();
4576 let [sx, sy, sz] = block.shift;
4577 let [ox, oy, oz] = block.delta;
4578 let cut_lo = _mm512_set1_pd(cut2 - margin);
4579 let cut_hi = cut2 + margin;
4580
4581 macro_rules! direct {
4584 ($s:expr, $slot:expr, $mask:expr) => {{
4585 let s = $s;
4586 let iu = *c.id.add(s);
4587 let px = *c.x.add(s) - sx;
4588 let py = *c.y.add(s) - sy;
4589 let pz = *c.z.add(s) - sz;
4590 let mut bits: u32 = u32::from($mask);
4591 while bits != 0 {
4592 let slot = $slot + bits.trailing_zeros() as usize;
4593 bits &= bits - 1;
4594 let dx = *c.x.add(slot) - px;
4595 let dy = *c.y.add(slot) - py;
4596 let dz = *c.z.add(slot) - pz;
4597 let d2 = dx * dx + dy * dy + dz * dz;
4598 if d2 < cut2 {
4599 atom_p.add(n).write(iu);
4600 js_p.add(n).write(*c.id.add(slot));
4601 d2_p.add(n).write(d2);
4602 n += 1;
4603 }
4604 }
4605 }};
4606 }
4607 macro_rules! source {
4609 ($s:expr) => {{
4610 let s = $s;
4611 let px = *c.rx.add(s) + ox;
4612 let py = *c.ry.add(s) + oy;
4613 let pz = *c.rz.add(s) + oz;
4614 let pp = px * px + py * py + pz * pz;
4615 (
4616 _mm256_set1_epi32(*c.id.add(s) as i32),
4617 _mm512_set1_pd(-2.0 * px),
4618 _mm512_set1_pd(-2.0 * py),
4619 _mm512_set1_pd(-2.0 * pz),
4620 _mm512_set1_pd(pp),
4621 _mm512_set1_pd(cut_hi - pp),
4622 )
4623 }};
4624 }
4625 macro_rules! direct_vec {
4633 ($s:expr, $slot:expr, $tm:expr) => {{
4634 let s = $s;
4635 let px = *c.x.add(s) - sx;
4636 let py = *c.y.add(s) - sy;
4637 let pz = *c.z.add(s) - sz;
4638 let (bx, by, bz) = (_mm512_set1_pd(px), _mm512_set1_pd(py), _mm512_set1_pd(pz));
4639 let (jx, jy, jz) = if $tm == 0xff {
4640 (
4641 _mm512_loadu_pd(c.x.add($slot)),
4642 _mm512_loadu_pd(c.y.add($slot)),
4643 _mm512_loadu_pd(c.z.add($slot)),
4644 )
4645 } else {
4646 (
4647 _mm512_maskz_loadu_pd($tm, c.x.add($slot)),
4648 _mm512_maskz_loadu_pd($tm, c.y.add($slot)),
4649 _mm512_maskz_loadu_pd($tm, c.z.add($slot)),
4650 )
4651 };
4652 let dx = _mm512_sub_pd(jx, bx);
4653 let dy = _mm512_sub_pd(jy, by);
4654 let dz = _mm512_sub_pd(jz, bz);
4655 _mm512_add_pd(
4656 _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
4657 _mm512_mul_pd(dz, dz),
4658 )
4659 }};
4660 }
4661 macro_rules! lanes {
4662 ($s:expr, $slot:expr, $tm:expr, $src:expr, $jx:expr, $jy:expr, $jz:expr, $jr:expr, $jids:expr) => {{
4663 let (iv, ax, ay, az, pp, thr) = $src;
4664 let t = _mm512_fmadd_pd(
4665 $jz,
4666 az,
4667 _mm512_fmadd_pd($jy, ay, _mm512_fmadd_pd($jx, ax, $jr)),
4668 );
4669 let hi: u8 = _mm512_mask_cmp_pd_mask($tm, t, thr, _CMP_LT_OQ);
4670 if hi != 0 {
4671 let d2_exp = _mm512_add_pd(t, pp);
4672 let lo: u8 = _mm512_mask_cmp_pd_mask(hi, d2_exp, cut_lo, _CMP_LT_OQ);
4673 if lo == hi {
4674 let d2v = direct_vec!($s, $slot, $tm);
4675 _mm512_storeu_pd(d2_p.add(n), _mm512_maskz_compress_pd(lo, d2v));
4676 _mm256_storeu_si256(
4677 js_p.add(n) as *mut __m256i,
4678 _mm256_maskz_compress_epi32(lo, $jids),
4679 );
4680 _mm256_storeu_si256(atom_p.add(n) as *mut __m256i, iv);
4681 n += lo.count_ones() as usize;
4682 } else {
4683 direct!($s, $slot, hi);
4684 }
4685 }
4686 }};
4687 }
4688 macro_rules! load {
4689 ($slot:expr, $j_hi:expr) => {{
4690 let slot = $slot;
4691 if slot + 8 <= $j_hi {
4692 (
4693 0xffu8,
4694 _mm512_loadu_pd(c.rx.add(slot)),
4695 _mm512_loadu_pd(c.ry.add(slot)),
4696 _mm512_loadu_pd(c.rz.add(slot)),
4697 _mm512_loadu_pd(c.r2.add(slot)),
4698 _mm256_loadu_si256(c.id.add(slot) as *const __m256i),
4699 )
4700 } else {
4701 let tm: u8 = ((1u32 << ($j_hi - slot)) - 1) as u8;
4702 (
4703 tm,
4704 _mm512_maskz_loadu_pd(tm, c.rx.add(slot)),
4705 _mm512_maskz_loadu_pd(tm, c.ry.add(slot)),
4706 _mm512_maskz_loadu_pd(tm, c.rz.add(slot)),
4707 _mm512_maskz_loadu_pd(tm, c.r2.add(slot)),
4708 _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
4709 )
4710 }
4711 }};
4712 }
4713
4714 let j_hi = block.j_hi;
4715 let nvec = (j_hi - block.j_lo + 7) / 8;
4716 let cull_box = !block.tri && c.cull && nvec >= CULL_RUNS;
4719 if cull_box {
4720 let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
4721 let zero = std::arch::x86_64::_mm512_setzero_pd();
4722 for s in block.i_lo..block.i_hi {
4723 let s0 = source!(s);
4724 near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
4725 let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4726 lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4727 });
4728 }
4729 } else if !block.tri {
4730 for s in block.i_lo..block.i_hi {
4731 let s0 = source!(s);
4732 let mut slot = block.j_lo;
4733 while slot < j_hi {
4734 let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4735 lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4736 slot += 8;
4737 }
4738 }
4739 } else {
4740 for s in block.i_lo..block.i_hi {
4741 let s0 = source!(s);
4742 let mut slot = s + 1;
4743 while slot < j_hi {
4744 let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4745 lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4746 slot += 8;
4747 }
4748 }
4749 }
4750 scratch.finish(n);
4751}
4752
4753#[cfg(test)]
4754mod tests {
4755 use super::*;
4756 use crate::Cell;
4757
4758 #[test]
4759 fn tight_cluster_matches_brute_force() {
4760 let n = 520usize;
4764 let mut xyz = vec![[0.0f64; 3]; n];
4765 let g = 9i32;
4766 let mut k = 0usize;
4767 'fill: for z in 0..g {
4768 for y in 0..g {
4769 for x in 0..g {
4770 if k >= n {
4771 break 'fill;
4772 }
4773 xyz[k] = [x as f64 * 0.05, y as f64 * 0.05, z as f64 * 0.05];
4774 k += 1;
4775 }
4776 }
4777 }
4778 let sim = Cell::ortho(80.0, 80.0, 80.0).unwrap();
4779 let cutoff = 2.0;
4780 let cut2 = cutoff * cutoff;
4781 let mut brute: Vec<(usize, usize, f64)> = Vec::new();
4782 for i in 0..n {
4783 for j in (i + 1)..n {
4784 let dx = xyz[j][0] - xyz[i][0];
4785 let dy = xyz[j][1] - xyz[i][1];
4786 let dz = xyz[j][2] - xyz[i][2];
4787 let d2 = dx * dx + dy * dy + dz * dz;
4788 if d2 < cut2 {
4789 brute.push((i, j, d2));
4790 brute.push((j, i, d2));
4791 }
4792 }
4793 }
4794 brute.sort_by_key(|a| (a.0, a.1));
4795 let run = || pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap();
4796 #[cfg(feature = "parallel")]
4797 let got = {
4798 let pool = rayon::ThreadPoolBuilder::new()
4799 .num_threads(4)
4800 .build()
4801 .unwrap();
4802 pool.install(run)
4803 };
4804 #[cfg(not(feature = "parallel"))]
4805 let got = run();
4806 let mut rows: Vec<(usize, usize, f64)> = got.iter().map(|p| (p.i, p.j, p.dist2)).collect();
4807 rows.sort_by_key(|a| (a.0, a.1));
4808 assert_eq!(rows.len(), n * (n - 1));
4809 assert_eq!(rows.len(), brute.len());
4810 for (got_row, brute_row) in rows.iter().zip(brute.iter()) {
4811 assert_eq!(got_row.0, brute_row.0);
4812 assert_eq!(got_row.1, brute_row.1);
4813 assert!((got_row.2 - brute_row.2).abs() < 1e-9);
4814 }
4815 }
4816
4817 fn on_threads<R: Send>(threads: usize, f: impl FnOnce() -> R + Send) -> R {
4819 #[cfg(feature = "parallel")]
4820 {
4821 rayon::ThreadPoolBuilder::new()
4822 .num_threads(threads)
4823 .build()
4824 .unwrap()
4825 .install(f)
4826 }
4827 #[cfg(not(feature = "parallel"))]
4828 {
4829 let _ = threads;
4830 f()
4831 }
4832 }
4833
4834 fn row_keys(rows: &[Pair]) -> Vec<(usize, usize, [i32; 3], u64)> {
4835 let mut k: Vec<_> = rows
4836 .iter()
4837 .map(|p| (p.i, p.j, p.shift, p.dist2.to_bits()))
4838 .collect();
4839 k.sort();
4840 k
4841 }
4842
4843 #[test]
4844 fn one_thread_and_eight_write_the_same_rows() {
4845 let sim = Cell::ortho(18.0, 17.0, 19.0).unwrap();
4848 let mut xyz = Vec::new();
4849 let mut state = 0x9e37_79b9_7f4a_7c15u64;
4850 let mut next = || {
4851 state ^= state << 13;
4852 state ^= state >> 7;
4853 state ^= state << 17;
4854 (state >> 11) as f64 / (1u64 << 53) as f64
4855 };
4856 for iz in 0..10 {
4857 for iy in 0..10 {
4858 for ix in 0..10 {
4859 xyz.push([
4860 (ix as f64 + 0.3 * next()) * 1.8,
4861 (iy as f64 + 0.3 * next()) * 1.7,
4862 (iz as f64 + 0.3 * next()) * 1.9,
4863 ]);
4864 }
4865 }
4866 }
4867 for half in [false, true] {
4868 let one = on_threads(1, || {
4869 pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4870 });
4871 let eight = on_threads(8, || {
4872 pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4873 });
4874 assert_eq!(row_keys(&one), row_keys(&eight), "half={half}");
4875 let mut c1 = PairColumns::default();
4876 let mut c8 = PairColumns::default();
4877 on_threads(1, || {
4878 pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut c1).unwrap()
4879 });
4880 on_threads(8, || {
4881 pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut c8).unwrap()
4882 });
4883 let cols = |c: &PairColumns| {
4884 let mut k: Vec<_> = (0..c.len())
4885 .map(|t| {
4886 (
4887 c.i[t] as usize,
4888 c.j[t] as usize,
4889 c.shift[t],
4890 c.dist2[t].to_bits(),
4891 )
4892 })
4893 .collect();
4894 k.sort();
4895 k
4896 };
4897 assert_eq!(cols(&c1), row_keys(&one), "columns half={half}");
4898 assert_eq!(cols(&c8), row_keys(&one), "columns eight half={half}");
4899 }
4900 }
4901
4902 #[test]
4903 fn sub_cells_keep_the_same_rows_in_the_same_order_on_eight_threads() {
4904 let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
4908 let mut state = 0x5851_f42d_4c95_7f2du64;
4909 let mut next = || {
4910 state ^= state << 13;
4911 state ^= state >> 7;
4912 state ^= state << 17;
4913 state
4914 };
4915 let mut xyz = Vec::new();
4916 for iz in 0..16 {
4917 for iy in 0..16 {
4918 for ix in 0..16 {
4919 let j = |v: u64| 0.3 * ((v >> 11) as f64 / (1u64 << 53) as f64 - 0.5);
4920 xyz.push([
4921 (ix as f64 + 0.5 + j(next())) * 1.125,
4922 (iy as f64 + 0.5 + j(next())) * 1.125,
4923 (iz as f64 + 0.5 + j(next())) * 1.125,
4924 ]);
4925 }
4926 }
4927 }
4928 for i in (1..xyz.len()).rev() {
4929 let k = (next() % (i as u64 + 1)) as usize;
4930 xyz.swap(i, k);
4931 }
4932 assert!(xyz.len() >= PARALLEL_GRID);
4933 for half in [false, true] {
4934 let one = on_threads(1, || {
4935 pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4936 });
4937 let eight = on_threads(8, || {
4938 pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4939 });
4940 assert_eq!(one.len(), eight.len(), "half={half}");
4941 assert!(one == eight, "half={half}: rows differ in content or order");
4942 }
4943 }
4944
4945 #[test]
4946 fn box_culling_keeps_every_row_in_order() {
4947 let mut state = 0x2545_f491_4f6c_dd1du64;
4953 let mut next = || {
4954 state ^= state << 13;
4955 state ^= state >> 7;
4956 state ^= state << 17;
4957 state
4958 };
4959 let mut unit = || (next() >> 11) as f64 / (1u64 << 53) as f64;
4960 let mut systems = Vec::new();
4961 for sim in [
4962 Cell::ortho(9.3, 9.6, 9.9).unwrap(),
4963 Cell::from_vectors(
4964 [9.6, 0.0, 0.0],
4965 [1.2, 9.5, 0.0],
4966 [-0.8, 0.9, 9.7],
4967 [0.5, -0.3, 0.2],
4968 )
4969 .unwrap(),
4970 ] {
4971 let xyz: Vec<[f64; 3]> = (0..1100)
4972 .map(|_| sim.cartesian([1.2 * unit() - 0.1, unit(), 1.1 * unit() - 0.05]))
4973 .collect();
4974 systems.push((sim, xyz, 3.0));
4975 }
4976 let mut lattice = Vec::new();
4977 for iz in 0..10 {
4978 for iy in 0..10 {
4979 for ix in 0..10 {
4980 let mut p = [ix as f64 + 0.5, iy as f64 + 0.5, iz as f64 + 0.5];
4981 for v in p.iter_mut() {
4982 let ulps = (next() % 13) as i64 - 6;
4983 *v = f64::from_bits((v.to_bits() as i64 + ulps) as u64);
4984 }
4985 lattice.push(p);
4986 }
4987 }
4988 }
4989 let shell = 11.0f64.sqrt();
4990 systems.push((Cell::ortho(10.0, 10.0, 10.0).unwrap(), lattice, shell));
4991 let before = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed);
4992 for (sim, xyz, cutoff) in &systems {
4993 let (sim, cutoff) = (sim, *cutoff);
4994 let mask: Vec<bool> = (0..xyz.len()).map(|k| k % 9 != 4).collect();
4995 if cutoff == shell {
4996 let rows = pairs_within(xyz, sim, cutoff, None, None, false).unwrap();
4997 let near = rows
4998 .iter()
4999 .filter(|p| (p.dist2 - cutoff * cutoff).abs() < 1e-12)
5000 .count();
5001 assert!(near > 1000, "only {near} rows near the cutoff");
5002 }
5003 for threads in [1, 8] {
5004 for half in [false, true] {
5005 for mask in [None, Some(mask.as_slice())] {
5006 let run = |cull: bool| {
5007 NO_CULL.store(!cull, std::sync::atomic::Ordering::Relaxed);
5008 let (rows, cols) = on_threads(threads, || {
5009 let rows =
5010 pairs_within(xyz, sim, cutoff, mask, None, half).unwrap();
5011 let mut cols = PairColumns::default();
5012 pairs_within_columns(xyz, sim, cutoff, mask, None, half, &mut cols)
5013 .unwrap();
5014 (rows, cols)
5015 });
5016 NO_CULL.store(false, std::sync::atomic::Ordering::Relaxed);
5017 (rows, cols)
5018 };
5019 let (culled, culled_cols) = run(true);
5020 let (plain, plain_cols) = run(false);
5021 let what = format!("threads={threads} half={half} mask={}", mask.is_some());
5022 assert!(culled.len() > 1000, "{what}");
5023 assert!(culled == plain, "{what}: rows differ in content or order");
5024 assert_eq!(culled_cols.i, plain_cols.i, "{what}");
5025 assert_eq!(culled_cols.j, plain_cols.j, "{what}");
5026 assert_eq!(culled_cols.shift, plain_cols.shift, "{what}");
5027 let bits = |c: &PairColumns| -> Vec<u64> {
5028 c.dist2.iter().map(|d| d.to_bits()).collect()
5029 };
5030 assert_eq!(bits(&culled_cols), bits(&plain_cols), "{what}");
5031 }
5032 }
5033 }
5034 }
5035 let _ = before;
5036 let (sim, xyz, cutoff) = &systems[0];
5037 for path in crate::simd::paths_to_compare() {
5038 if path == Path::Scalar {
5039 continue;
5040 }
5041 let at = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed);
5042 on_threads(1, || {
5043 let _guard = crate::simd::force(path);
5044 let _ = pairs_within(xyz, sim, *cutoff, None, None, false).unwrap();
5045 });
5046 let skipped = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed) - at;
5047 assert!(skipped > 0, "{path:?} skipped no target run");
5048 }
5049 }
5050
5051 #[test]
5052 fn vector_fold_matches_fold_point_bit_for_bit() {
5053 let cells = [
5054 Cell::ortho(18.0, 17.0, 19.0).unwrap(),
5055 Cell::from_vectors(
5056 [10.0, 0.0, 0.0],
5057 [5.0, 8.660254037844386, 0.0],
5058 [1.0, -2.0, 9.5],
5059 [0.3, -1.0, 2.0],
5060 )
5061 .unwrap(),
5062 Cell::from_vectors(
5063 [9.0, 3.0, 2.0],
5064 [1.0, 9.0, -2.0],
5065 [-1.5, 2.0, 9.5],
5066 [0.0; 3],
5067 )
5068 .unwrap(),
5069 ];
5070 let mut state = 0x2545_f491_4f6c_dd1du64;
5071 let mut next = || {
5072 state ^= state << 13;
5073 state ^= state >> 7;
5074 state ^= state << 17;
5075 (state >> 11) as f64 / (1u64 << 53) as f64
5076 };
5077 for sim in &cells {
5078 let mut xyz: Vec<[f64; 3]> = (0..203)
5079 .map(|_| {
5080 [
5081 (next() - 0.3) * 60.0,
5082 (next() - 0.7) * 45.0,
5083 (next() - 0.5) * 80.0,
5084 ]
5085 })
5086 .collect();
5087 let w = sim.widths();
5088 xyz.extend_from_slice(&[
5089 [0.0; 3],
5090 [w[0], w[1], w[2]],
5091 [-0.0, -1e-300, 1e-300],
5092 [w[0] * 0.5, -w[1], 3.0 * w[2]],
5093 ]);
5094 let n = [5, 4, 7];
5095 for sub in [1, 2, 4] {
5096 let keys = Keys { n, sub };
5097 let nkey = 140 * keys.per_bin();
5098 let mut fold = FoldCols::default();
5099 fold.clear_for(xyz.len());
5100 let fp = fold.ptrs();
5101 let mut count = vec![0u32; nkey];
5102 fold_range(
5103 sim,
5104 &xyz,
5105 None,
5106 keys,
5107 false,
5108 crate::simd::select(),
5109 0,
5110 xyz.len(),
5111 fp,
5112 &mut count,
5113 );
5114 let mut want_count = vec![0u32; nkey];
5115 for (k, r) in xyz.iter().enumerate() {
5116 let (q, b) = bins::fold_point(sim, *r, keys.fine());
5117 let key = keys.key(b);
5118 want_count[key] += 1;
5119 let (p, got) = unsafe { fp.get(k) };
5121 assert_eq!(got, key, "atom {k} sub {sub}");
5122 for (a, (got, want)) in p.iter().zip(q).enumerate() {
5123 assert_eq!(got.to_bits(), want.to_bits(), "atom {k} axis {a}");
5124 }
5125 }
5126 assert_eq!(count, want_count);
5127 }
5128 }
5129 }
5130
5131 #[test]
5132 fn dense_cluster_on_several_threads_matches_one() {
5133 let sim = Cell::ortho(20.0, 20.0, 20.0).unwrap();
5137 let mut xyz = Vec::new();
5138 'fill: for z in 0..9 {
5139 for y in 0..9 {
5140 for x in 0..9 {
5141 if xyz.len() == 520 {
5142 break 'fill;
5143 }
5144 xyz.push([
5145 10.0 + x as f64 * 0.05,
5146 10.0 + y as f64 * 0.05,
5147 10.0 + z as f64 * 0.05,
5148 ]);
5149 }
5150 }
5151 }
5152 for z in 0..16 {
5153 for y in 0..16 {
5154 for x in 0..16 {
5155 if xyz.len() == 4520 {
5156 break;
5157 }
5158 xyz.push([
5159 x as f64 * 1.25 + 0.31,
5160 y as f64 * 1.25 + 0.17,
5161 z as f64 * 1.25 + 0.53,
5162 ]);
5163 }
5164 }
5165 }
5166 #[cfg(feature = "parallel")]
5167 assert!(hit_estimate(xyz.len(), &sim, 2.0) >= PARALLEL_PAIRS);
5168 let one = on_threads(1, || {
5169 pairs_within(&xyz, &sim, 2.0, None, None, false).unwrap()
5170 });
5171 let eight = on_threads(8, || {
5172 pairs_within(&xyz, &sim, 2.0, None, None, false).unwrap()
5173 });
5174 assert_eq!(row_keys(&one), row_keys(&eight));
5175 let cluster = eight.iter().filter(|p| p.i < 520 && p.j < 520).count();
5176 assert_eq!(cluster, 520 * 519);
5177 }
5178
5179 #[test]
5180 fn one_thread_matches_the_shift_scan() {
5181 let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5182 let mut xyz = Vec::new();
5183 for iz in 0..9 {
5184 for iy in 0..9 {
5185 for ix in 0..9 {
5186 xyz.push([
5187 (ix as f64 + 0.5) * 2.0,
5188 (iy as f64 + 0.5) * 2.0,
5189 (iz as f64 + 0.5) * 2.0,
5190 ]);
5191 }
5192 }
5193 }
5194 let cutoff = 4.0;
5195 let got = on_threads(1, || {
5196 pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap()
5197 });
5198 let mut keys: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5199 keys.sort();
5200 let mut want = Vec::new();
5201 for i in 0..xyz.len() {
5202 for j in 0..xyz.len() {
5203 for na in -1..=1 {
5204 for nb in -1..=1 {
5205 for nc in -1..=1 {
5206 if i == j && na == 0 && nb == 0 && nc == 0 {
5207 continue;
5208 }
5209 let d2 =
5210 sim.dist2_shifted(xyz[i], xyz[j], sim.lattice_shift(na, nb, nc));
5211 if d2 < cutoff * cutoff {
5212 want.push((i, j, [na, nb, nc]));
5213 }
5214 }
5215 }
5216 }
5217 }
5218 }
5219 want.sort();
5220 assert_eq!(keys, want);
5221 for p in &got {
5222 let d2 = sim.dist2_shifted(
5223 xyz[p.i],
5224 xyz[p.j],
5225 sim.lattice_shift(p.shift[0], p.shift[1], p.shift[2]),
5226 );
5227 assert!((p.dist2 - d2).abs() < 1e-9);
5228 }
5229 }
5230
5231 #[test]
5232 fn columns_hold_the_same_rows() {
5233 let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5234 let mut xyz = Vec::new();
5235 for iz in 0..9 {
5236 for iy in 0..9 {
5237 for ix in 0..9 {
5238 xyz.push([
5239 ix as f64 * 2.0 + 0.3,
5240 iy as f64 * 2.0 + 0.1,
5241 iz as f64 * 2.0 + 0.7,
5242 ]);
5243 }
5244 }
5245 }
5246 let mut cols = PairColumns::default();
5247 for half in [false, true] {
5248 let rows = pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap();
5249 pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut cols).unwrap();
5250 assert_eq!(cols.len(), rows.len());
5251 let mut a: Vec<_> = rows
5252 .iter()
5253 .map(|p| (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()))
5254 .collect();
5255 let mut b: Vec<_> = (0..cols.len())
5256 .map(|t| (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()))
5257 .collect();
5258 a.sort();
5259 b.sort();
5260 assert_eq!(a, b, "half={half}");
5261 }
5262 }
5263
5264 #[test]
5265 fn sparse_bins_write_the_same_rows_on_one_thread_and_eight() {
5266 let cpus = std::thread::available_parallelism()
5272 .map(|n| n.get())
5273 .unwrap_or(1);
5274 let width = cpus.min(8);
5275 if width < 2 {
5276 return;
5277 }
5278 let cells = [
5279 Cell::ortho(40.0, 39.0, 41.0).unwrap(),
5280 Cell::from_vectors(
5281 [40.0, 0.0, 0.0],
5282 [6.0, 39.0, 0.0],
5283 [-4.0, 3.0, 40.5],
5284 [0.3, 0.0, -0.2],
5285 )
5286 .unwrap(),
5287 ];
5288 let mut state = 0x6a09_e667_f3bc_c908u64;
5289 let mut unit = || {
5290 state ^= state << 13;
5291 state ^= state >> 7;
5292 state ^= state << 17;
5293 (state >> 11) as f64 / (1u64 << 53) as f64
5294 };
5295 for sim in &cells {
5296 let xyz: Vec<[f64; 3]> = (0..3000)
5297 .map(|_| sim.cartesian([unit(), unit(), unit()]))
5298 .collect();
5299 let hits = hit_estimate(xyz.len(), sim, 4.0);
5300 if on_threads(width, || walk_threads(hits)) <= 1 {
5301 return;
5302 }
5303 for half in [false, true] {
5304 let (one, one_cols) = on_threads(1, || {
5305 let rows = pairs_within(&xyz, sim, 4.0, None, None, half).unwrap();
5306 let mut cols = PairColumns::default();
5307 pairs_within_columns(&xyz, sim, 4.0, None, None, half, &mut cols).unwrap();
5308 (rows, cols)
5309 });
5310 let eight = on_threads(width, || {
5311 pairs_within(&xyz, sim, 4.0, None, None, half).unwrap()
5312 });
5313 assert!(one.len() > 10_000, "half={half}");
5314 assert!(one == eight, "half={half}: rows differ in content or order");
5315 assert_eq!(one_cols.len(), one.len());
5316 for (t, p) in one.iter().enumerate() {
5317 assert_eq!(
5318 (
5319 one_cols.i[t],
5320 one_cols.j[t],
5321 one_cols.shift[t],
5322 one_cols.dist2[t].to_bits()
5323 ),
5324 (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()),
5325 "half={half} row {t}"
5326 );
5327 }
5328 }
5329 }
5330 }
5331
5332 #[test]
5333 fn half_rows_keep_their_side_on_periodic_images() {
5334 let cells = [
5340 Cell::ortho(6.0, 6.5, 7.0).unwrap(),
5341 Cell::from_vectors(
5342 [6.5, 0.0, 0.0],
5343 [1.5, 6.0, 0.0],
5344 [-1.0, 0.8, 7.0],
5345 [0.1, 0.0, 0.0],
5346 )
5347 .unwrap(),
5348 ];
5349 let mut state = 0x3c6e_f372_fe94_f82bu64;
5350 let mut unit = || {
5351 state ^= state << 13;
5352 state ^= state >> 7;
5353 state ^= state << 17;
5354 (state >> 11) as f64 / (1u64 << 53) as f64
5355 };
5356 let key = |p: &Pair| (p.i, p.j, p.shift, p.dist2.to_bits());
5357 for sim in &cells {
5358 let xyz: Vec<[f64; 3]> = (0..250)
5359 .map(|_| sim.cartesian([unit(), unit(), unit()]))
5360 .collect();
5361 let one = on_threads(1, || {
5362 pairs_within(&xyz, sim, 7.5, None, None, true).unwrap()
5363 });
5364 let eight = on_threads(8, || {
5365 pairs_within(&xyz, sim, 7.5, None, None, true).unwrap()
5366 });
5367 let full = on_threads(1, || {
5368 pairs_within(&xyz, sim, 7.5, None, None, false).unwrap()
5369 });
5370 assert!(
5371 one.iter().any(|p| p.i == p.j),
5372 "no periodic self-image rows"
5373 );
5374 assert!(one == eight, "one thread and eight differ");
5375 let mut want: Vec<_> = full
5376 .iter()
5377 .filter(|p| keep_half(p.i, p.j, p.shift))
5378 .map(key)
5379 .collect();
5380 let mut got: Vec<_> = one.iter().map(key).collect();
5381 want.sort();
5382 got.sort();
5383 assert_eq!(got, want);
5384 let mut cols = PairColumns::default();
5385 on_threads(1, || {
5386 pairs_within_columns(&xyz, sim, 7.5, None, None, true, &mut cols).unwrap()
5387 });
5388 assert_eq!(cols.len(), one.len());
5389 for (t, p) in one.iter().enumerate() {
5390 assert_eq!(
5391 (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()),
5392 (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()),
5393 "column row {t}"
5394 );
5395 }
5396 }
5397 }
5398
5399 static AHEAD_LOCK: std::sync::Mutex<()> = std::sync::Mutex::new(());
5402
5403 #[test]
5404 fn split_tile_fill_writes_the_one_thread_rows() {
5405 let _held = AHEAD_LOCK.lock().unwrap_or_else(|e| e.into_inner());
5406 use std::sync::atomic::Ordering::Relaxed;
5412 let mut state = 0xa54f_f53a_5f1d_36f1u64;
5413 let mut unit = || {
5414 state ^= state << 13;
5415 state ^= state >> 7;
5416 state ^= state << 17;
5417 (state >> 11) as f64 / (1u64 << 53) as f64
5418 };
5419 let cells = [
5420 Cell::ortho(18.0, 17.0, 19.0).unwrap(),
5421 Cell::from_vectors(
5422 [18.0, 0.0, 0.0],
5423 [3.0, 17.5, 0.0],
5424 [-2.0, 1.5, 18.5],
5425 [0.2, -0.1, 0.0],
5426 )
5427 .unwrap(),
5428 Cell::ortho(40.0, 39.0, 41.0).unwrap(),
5429 ];
5430 let split = cfg!(all(
5433 feature = "parallel",
5434 target_arch = "x86_64",
5435 linkcell_avx512
5436 )) && Path::Avx512.usable();
5437 for (c, sim) in cells.iter().enumerate() {
5438 let n = if c == 2 { 3000 } else { 4000 };
5439 let xyz: Vec<[f64; 3]> = (0..n)
5440 .map(|_| sim.cartesian([unit(), unit(), unit()]))
5441 .collect();
5442 let mask: Vec<bool> = (0..n).map(|k| k % 7 != 3).collect();
5443 for m in [None, Some(mask.as_slice())] {
5444 let one = on_threads(1, || pairs_within(&xyz, sim, 4.0, m, None, false).unwrap());
5445 let fills = FUSED_FILLS.load(Relaxed);
5446 AHEAD_TEST.store(2, Relaxed);
5447 let eight = on_threads(8, || pairs_within(&xyz, sim, 4.0, m, None, false).unwrap());
5448 AHEAD_TEST.store(0, Relaxed);
5449 assert!(
5450 !split || FUSED_FILLS.load(Relaxed) > fills,
5451 "cell {c}: the split fill did not run"
5452 );
5453 assert!(one.len() > 10_000);
5454 assert!(one == eight, "cell {c} mask={}", m.is_some());
5455 }
5456 }
5457 }
5458
5459 #[test]
5460 fn prefetching_writers_write_the_same_rows_in_order() {
5461 let _held = AHEAD_LOCK.lock().unwrap_or_else(|e| e.into_inner());
5462 use std::sync::atomic::Ordering::Relaxed;
5467 let mut state = 0xbb67_ae85_84ca_a73bu64;
5468 let mut unit = || {
5469 state ^= state << 13;
5470 state ^= state >> 7;
5471 state ^= state << 17;
5472 (state >> 11) as f64 / (1u64 << 53) as f64
5473 };
5474 let dense = Cell::ortho(18.0, 17.0, 19.0).unwrap();
5475 let sparse = Cell::ortho(40.0, 39.0, 41.0).unwrap();
5476 let sets: Vec<(Cell, Vec<[f64; 3]>)> = vec![
5477 (
5478 dense,
5479 (0..4000)
5480 .map(|_| dense.cartesian([unit(), unit(), unit()]))
5481 .collect(),
5482 ),
5483 (
5484 sparse,
5485 (0..3000)
5486 .map(|_| sparse.cartesian([unit(), unit(), unit()]))
5487 .collect(),
5488 ),
5489 ];
5490 let run = |sim: &Cell, xyz: &[[f64; 3]], threads: usize, half: bool| {
5491 on_threads(threads, || {
5492 let rows = pairs_within(xyz, sim, 4.0, None, None, half).unwrap();
5493 let mut cols = PairColumns::default();
5494 pairs_within_columns(xyz, sim, 4.0, None, None, half, &mut cols).unwrap();
5495 (rows, cols)
5496 })
5497 };
5498 for (sim, xyz) in &sets {
5499 for threads in [1, 8] {
5500 for half in [false, true] {
5501 AHEAD_TEST.store(1, Relaxed);
5502 let off = run(sim, xyz, threads, half);
5503 AHEAD_TEST.store(2, Relaxed);
5504 let on = run(sim, xyz, threads, half);
5505 AHEAD_TEST.store(0, Relaxed);
5506 assert!(off.0.len() > 10_000);
5507 assert!(off.0 == on.0, "rows: threads={threads} half={half}");
5508 assert!(off.1 == on.1, "columns: threads={threads} half={half}");
5509 #[cfg(feature = "capi")]
5511 {
5512 let c_rows = |mode: u8| {
5513 AHEAD_TEST.store(mode, Relaxed);
5514 on_threads(threads, || {
5515 let found = search(xyz, sim, 4.0, None, None, half).unwrap();
5516 let n = found.rows();
5517 let mut out: Vec<(i32, i32, [i32; 3], u64)> = Vec::with_capacity(n);
5518 unsafe {
5520 found.write_rows(out.as_mut_ptr(), |i, j, s, d| {
5521 (i, j, s, d.to_bits())
5522 });
5523 out.set_len(n);
5524 }
5525 out
5526 })
5527 };
5528 let (off, on) = (c_rows(1), c_rows(2));
5529 AHEAD_TEST.store(0, Relaxed);
5530 assert!(off == on, "C rows: threads={threads} half={half}");
5531 }
5532 }
5533 }
5534 }
5535 }
5536
5537 #[test]
5538 fn far_image_is_not_rewrapped() {
5539 let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5540 let xyz = [[0.1, 0.0, 0.0], [0.2, 0.0, 0.0]];
5541 let pairs = pairs_within(&xyz, &sim, 3.0, None, Some(10.0), false).unwrap();
5542 assert_eq!(pairs.len(), 2);
5543 assert!(pairs.iter().all(|p| p.shift == [0, 0, 0]));
5544 assert!(pairs.iter().all(|p| (p.dist2 - 0.01).abs() < 1e-12));
5545 }
5546
5547 #[test]
5548 fn highway_mic_matches_wrap_pair_distance() {
5549 let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5550 let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5551 let pairs = pairs_within(&xyz, &sim, 1.0, None, None, true).unwrap();
5552 let mut mic = [0.0];
5553 crate::dist2_ortho_diffs(
5554 &[xyz[1][0] - xyz[0][0]],
5555 &[xyz[1][1] - xyz[0][1]],
5556 &[xyz[1][2] - xyz[0][2]],
5557 10.0,
5558 10.0,
5559 10.0,
5560 &mut mic,
5561 )
5562 .unwrap();
5563 assert_eq!(pairs.len(), 1);
5564 assert_eq!(pairs[0].shift, [-1, 0, 0]);
5565 assert!((pairs[0].dist2 - mic[0]).abs() < 1e-12);
5566 assert!((mic[0] - 0.64).abs() < 1e-12);
5567 }
5568
5569 #[test]
5570 fn wrap_pair_keeps_shift() {
5571 let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5572 let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5573 let pairs = pairs_within(&xyz, &sim, 1.0, None, None, false).unwrap();
5574 assert_eq!(pairs.len(), 2);
5575 let a = pairs.iter().find(|p| p.i == 0 && p.j == 1).unwrap();
5576 assert_eq!(a.shift, [-1, 0, 0]);
5577 assert!((a.dist2 - 0.64).abs() < 1e-12);
5578 }
5579
5580 #[test]
5581 fn half_list_is_canonical() {
5582 let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5583 let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5584 let pairs = pairs_within(&xyz, &sim, 1.0, None, None, true).unwrap();
5585 assert_eq!(pairs.len(), 1);
5586 assert_eq!(pairs[0].i, 0);
5587 assert_eq!(pairs[0].j, 1);
5588 }
5589
5590 #[test]
5591 fn sheared_cutoff_matches_shift_scan() {
5592 let sim = Cell::from_vectors(
5593 [4.0, 0.0, 0.0],
5594 [1.5, 3.0, 0.0],
5595 [0.2, -0.4, 3.5],
5596 [0.0, 0.0, 0.0],
5597 )
5598 .unwrap();
5599 let xyz = [
5600 sim.cartesian([0.05, 0.10, 0.20]),
5601 sim.cartesian([0.90, 0.15, 0.80]),
5602 sim.cartesian([0.40, 0.70, 0.30]),
5603 sim.cartesian([0.12, 0.85, 0.05]),
5604 ];
5605 let cutoff = 2.5;
5606 let got = pairs_within(&xyz, &sim, cutoff, None, Some(1.0), false).unwrap();
5607 let mut want = Vec::new();
5608 let cut2 = cutoff * cutoff;
5609 for i in 0..xyz.len() {
5610 for j in 0..xyz.len() {
5611 for na in -2..=2 {
5612 for nb in -2..=2 {
5613 for nc in -2..=2 {
5614 if i == j && na == 0 && nb == 0 && nc == 0 {
5615 continue;
5616 }
5617 let shift = sim.lattice_shift(na, nb, nc);
5618 let pi = sim.cartesian(sim.fractional(xyz[i]));
5619 let pj = sim.cartesian(sim.fractional(xyz[j]));
5620 let d2 = sim.dist2_shifted(pi, pj, shift);
5621 if d2 < cut2 {
5622 want.push((i, j, [na, nb, nc]));
5623 }
5624 }
5625 }
5626 }
5627 }
5628 }
5629 let mut got_key: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5630 got_key.sort();
5631 want.sort();
5632 assert_eq!(got_key, want);
5633 }
5634
5635 #[test]
5636 fn wide_cube_matches_shift_scan() {
5637 let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5638 let mut xyz = Vec::new();
5639 for iz in 0..8 {
5640 for iy in 0..8 {
5641 for ix in 0..8 {
5642 xyz.push([
5643 (ix as f64 + 0.5) * 18.0 / 8.0,
5644 (iy as f64 + 0.5) * 18.0 / 8.0,
5645 (iz as f64 + 0.5) * 18.0 / 8.0,
5646 ]);
5647 }
5648 }
5649 }
5650 let cutoff = 4.0;
5651 let cut2 = cutoff * cutoff;
5652 for half in [false, true] {
5653 let got = pairs_within(&xyz, &sim, cutoff, None, None, half).unwrap();
5654 let mut want = Vec::new();
5655 for i in 0..xyz.len() {
5656 for j in 0..xyz.len() {
5657 for na in -1..=1 {
5658 for nb in -1..=1 {
5659 for nc in -1..=1 {
5660 if i == j && na == 0 && nb == 0 && nc == 0 {
5661 continue;
5662 }
5663 let shift = [na, nb, nc];
5664 let d2 = sim.dist2_shifted(
5665 xyz[i],
5666 xyz[j],
5667 sim.lattice_shift(na, nb, nc),
5668 );
5669 if d2 < cut2 && (!half || keep_half(i, j, shift)) {
5670 want.push((i, j, shift));
5671 }
5672 }
5673 }
5674 }
5675 }
5676 }
5677 let mut got_key: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5678 got_key.sort();
5679 want.sort();
5680 assert_eq!(got_key, want);
5681 }
5682 }
5683
5684 #[test]
5685 fn dense_cube_matches_shift_scan() {
5686 let sim = Cell::ortho(6.0, 6.0, 6.0).unwrap();
5687 let mut xyz = Vec::new();
5688 for iz in 0..5 {
5689 for iy in 0..5 {
5690 for ix in 0..5 {
5691 xyz.push([
5692 (ix as f64 + 0.5) * 1.2,
5693 (iy as f64 + 0.5) * 1.2,
5694 (iz as f64 + 0.5) * 1.2,
5695 ]);
5696 }
5697 }
5698 }
5699 let cutoff = 2.0;
5700 let got = pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap();
5701 let mut keys: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5702 keys.sort();
5703 let cut2 = cutoff * cutoff;
5704 let mut want = Vec::new();
5705 for i in 0..xyz.len() {
5706 for j in 0..xyz.len() {
5707 for na in -1..=1 {
5708 for nb in -1..=1 {
5709 for nc in -1..=1 {
5710 if i == j && na == 0 && nb == 0 && nc == 0 {
5711 continue;
5712 }
5713 let shift = [na, nb, nc];
5714 let pi = sim.cartesian(sim.fractional(xyz[i]));
5715 let pj = sim.cartesian(sim.fractional(xyz[j]));
5716 let d2 = sim.dist2_shifted(pi, pj, sim.lattice_shift(na, nb, nc));
5717 if d2 < cut2 {
5718 want.push((i, j, shift));
5719 }
5720 }
5721 }
5722 }
5723 }
5724 }
5725 want.sort();
5726 assert_eq!(keys, want);
5727 }
5728
5729 #[test]
5730 fn bad_cutoff() {
5731 let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5732 let xyz = [[0.0, 0.0, 0.0]];
5733 assert_eq!(
5734 pairs_within(&xyz, &sim, 0.0, None, None, false).unwrap_err(),
5735 Error::BadCutoff
5736 );
5737 }
5738
5739 fn thread_counts() -> Vec<usize> {
5740 let mut counts = vec![1usize];
5741 #[cfg(feature = "parallel")]
5742 counts.extend([2usize, 3, 8]);
5743 counts.sort_unstable();
5744 counts.dedup();
5745 counts
5746 }
5747
5748 fn pair_rows(
5749 threads: usize,
5750 path: Path,
5751 xyz: &[[f64; 3]],
5752 cell: &Cell,
5753 cutoff: f64,
5754 ) -> Vec<(i32, i32, [i32; 3], u64)> {
5755 on_threads(threads, || {
5756 let _guard = crate::simd::force(path);
5757 let rows = pairs_within(xyz, cell, cutoff, None, None, false).unwrap();
5758 let mut cols = PairColumns::default();
5759 pairs_within_columns(xyz, cell, cutoff, None, None, false, &mut cols).unwrap();
5760 let from_rows: Vec<_> = rows
5761 .iter()
5762 .map(|p| (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()))
5763 .collect();
5764 let from_cols: Vec<_> = (0..cols.len())
5765 .map(|t| (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()))
5766 .collect();
5767 assert_eq!(from_rows, from_cols);
5768 from_rows
5769 })
5770 }
5771
5772 #[test]
5774 fn rank_invariant_pairs_on_jittered_triclinic() {
5775 let cell = Cell::from_vectors(
5776 [36.0, 0.0, 0.0],
5777 [3.5, 34.0, 0.0],
5778 [-2.5, 2.0, 33.0],
5779 [0.3, -0.2, 0.15],
5780 )
5781 .unwrap();
5782 let n = 12usize;
5783 let mut state = 0x1234_5678_9abc_def0u64;
5784 let mut next = || {
5785 state ^= state << 13;
5786 state ^= state >> 7;
5787 state ^= state << 17;
5788 state
5789 };
5790 let mut xyz = Vec::new();
5791 for iz in 0..n {
5792 for iy in 0..n {
5793 for ix in 0..n {
5794 let j = |v: u64| ((v >> 11) as f64 / (1u64 << 53) as f64 - 0.5) * 0.15;
5795 xyz.push(cell.cartesian([
5796 (ix as f64 + 0.5) / n as f64 + j(next()),
5797 (iy as f64 + 0.5) / n as f64 + j(next()),
5798 (iz as f64 + 0.5) / n as f64 + j(next()),
5799 ]));
5800 }
5801 }
5802 }
5803 xyz[0][0] = -0.0;
5804 xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5805 xyz[2][2] = 1.0e-320;
5806 let reference = pair_rows(1, Path::Scalar, &xyz, &cell, 5.0);
5807 assert!(reference.len() > 1000, "only {} pairs", reference.len());
5808 for threads in thread_counts() {
5809 for path in crate::simd::paths_to_compare() {
5810 let got = pair_rows(threads, path, &xyz, &cell, 5.0);
5811 assert_eq!(
5812 got,
5813 reference,
5814 "threads={threads} path={path:?} len {} vs {}",
5815 got.len(),
5816 reference.len()
5817 );
5818 }
5819 }
5820 }
5821
5822 #[test]
5823 fn simd_paths_exercised() {
5824 let names: Vec<_> = crate::simd::paths_to_compare()
5825 .iter()
5826 .map(|p| p.name())
5827 .collect();
5828 println!("exercised={}", names.join(","));
5829 println!("native={}", crate::simd::native().name());
5830 if let Ok(text) = std::fs::read_to_string("/proc/cpuinfo") {
5831 if let Some(flags) = text.lines().find(|line| line.starts_with("flags")) {
5832 println!("{flags}");
5833 }
5834 if let Some(model) = text.lines().find(|line| line.starts_with("model name")) {
5835 println!("{model}");
5836 }
5837 }
5838 assert!(names.contains(&"scalar"));
5839 }
5840
5841 fn sha256(data: &[u8]) -> [u8; 32] {
5842 const K: [u32; 64] = [
5843 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
5844 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
5845 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
5846 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
5847 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
5848 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
5849 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
5850 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
5851 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
5852 0xc67178f2,
5853 ];
5854 let mut h = [
5855 0x6a09e667u32,
5856 0xbb67ae85,
5857 0x3c6ef372,
5858 0xa54ff53a,
5859 0x510e527f,
5860 0x9b05688c,
5861 0x1f83d9ab,
5862 0x5be0cd19,
5863 ];
5864 let bit_len = (data.len() as u64).wrapping_mul(8);
5865 let mut msg = data.to_vec();
5866 msg.push(0x80);
5867 while msg.len() % 64 != 56 {
5868 msg.push(0);
5869 }
5870 msg.extend_from_slice(&bit_len.to_be_bytes());
5871 for chunk in msg.chunks_exact(64) {
5872 let mut w = [0u32; 64];
5873 for i in 0..16 {
5874 w[i] = u32::from_be_bytes(chunk[i * 4..i * 4 + 4].try_into().unwrap());
5875 }
5876 for i in 16..64 {
5877 let s0 = w[i - 15].rotate_right(7) ^ w[i - 15].rotate_right(18) ^ (w[i - 15] >> 3);
5878 let s1 = w[i - 2].rotate_right(17) ^ w[i - 2].rotate_right(19) ^ (w[i - 2] >> 10);
5879 w[i] = w[i - 16]
5880 .wrapping_add(s0)
5881 .wrapping_add(w[i - 7])
5882 .wrapping_add(s1);
5883 }
5884 let (mut a, mut b, mut c, mut d, mut e, mut f, mut g, mut hh) =
5885 (h[0], h[1], h[2], h[3], h[4], h[5], h[6], h[7]);
5886 for i in 0..64 {
5887 let s1 = e.rotate_right(6) ^ e.rotate_right(11) ^ e.rotate_right(25);
5888 let ch = (e & f) ^ (!e & g);
5889 let t1 = hh
5890 .wrapping_add(s1)
5891 .wrapping_add(ch)
5892 .wrapping_add(K[i])
5893 .wrapping_add(w[i]);
5894 let s0 = a.rotate_right(2) ^ a.rotate_right(13) ^ a.rotate_right(22);
5895 let maj = (a & b) ^ (a & c) ^ (b & c);
5896 let t2 = s0.wrapping_add(maj);
5897 hh = g;
5898 g = f;
5899 f = e;
5900 e = d.wrapping_add(t1);
5901 d = c;
5902 c = b;
5903 b = a;
5904 a = t1.wrapping_add(t2);
5905 }
5906 h[0] = h[0].wrapping_add(a);
5907 h[1] = h[1].wrapping_add(b);
5908 h[2] = h[2].wrapping_add(c);
5909 h[3] = h[3].wrapping_add(d);
5910 h[4] = h[4].wrapping_add(e);
5911 h[5] = h[5].wrapping_add(f);
5912 h[6] = h[6].wrapping_add(g);
5913 h[7] = h[7].wrapping_add(hh);
5914 }
5915 let mut out = [0u8; 32];
5916 for (i, word) in h.iter().enumerate() {
5917 out[i * 4..i * 4 + 4].copy_from_slice(&word.to_be_bytes());
5918 }
5919 out
5920 }
5921
5922 fn hex32(bytes: &[u8; 32]) -> String {
5923 const HEX: &[u8; 16] = b"0123456789abcdef";
5924 let mut s = String::with_capacity(64);
5925 for b in bytes {
5926 s.push(HEX[(b >> 4) as usize] as char);
5927 s.push(HEX[(b & 0xf) as usize] as char);
5928 }
5929 s
5930 }
5931
5932 fn golden_dist2_bytes() -> Vec<u8> {
5936 let n = 5usize;
5937 let a = 2.5f64;
5938 let boxl = n as f64 * a;
5939 let cell = Cell::ortho(boxl, boxl, boxl).unwrap();
5940 let mut xyz = Vec::new();
5941 for iz in 0..n {
5942 for iy in 0..n {
5943 for ix in 0..n {
5944 xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
5945 }
5946 }
5947 }
5948 xyz[0][0] = -0.0;
5949 xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5950 xyz[2][2] = 1.0e-320;
5951 let rows = pair_rows(1, Path::Scalar, &xyz, &cell, 4.0);
5952 let mut bytes = Vec::with_capacity(rows.len() * 8);
5953 for (_, _, _, bits) in rows {
5954 bytes.extend_from_slice(&bits.to_le_bytes());
5955 }
5956 bytes
5957 }
5958
5959 #[test]
5960 fn golden_isa_hash_matches_scalar_dist2() {
5961 let empty = sha256(b"");
5962 assert_eq!(
5963 hex32(&empty),
5964 "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
5965 );
5966 let bytes = golden_dist2_bytes();
5967 let got = hex32(&sha256(&bytes));
5968 for path in crate::simd::paths_to_compare() {
5969 let n = 5usize;
5970 let a = 2.5f64;
5971 let cell = Cell::ortho(n as f64 * a, n as f64 * a, n as f64 * a).unwrap();
5972 let mut xyz = Vec::new();
5973 for iz in 0..n {
5974 for iy in 0..n {
5975 for ix in 0..n {
5976 xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
5977 }
5978 }
5979 }
5980 xyz[0][0] = -0.0;
5981 xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5982 xyz[2][2] = 1.0e-320;
5983 let rows = pair_rows(1, path, &xyz, &cell, 4.0);
5984 let mut raw = Vec::new();
5985 for (_, _, _, bits) in rows {
5986 raw.extend_from_slice(&bits.to_le_bytes());
5987 }
5988 assert_eq!(hex32(&sha256(&raw)), got, "{path:?}");
5989 }
5990 let file = include_str!("../tests/golden/isa-hashes.toml");
5991 let want = file
5992 .lines()
5993 .find_map(|line| {
5994 line.strip_prefix("sha256 = \"")
5995 .map(|rest| rest.trim_end_matches('"'))
5996 })
5997 .expect("sha256 entry");
5998 assert_eq!(got, want, "update tests/golden/isa-hashes.toml");
5999 }
6000}