1use std::cell::RefCell;
9use std::os::raw::c_void;
10use std::time::Instant;
11
12use super::{
13 box_diameter, select_one_block, walk_cells, BlockScan, Candidates, Geom, KHeap, Mesh, RowsOut,
14 TEAM,
15};
16use crate::bins::{self, Recycled};
17use crate::cell::Cell;
18use crate::Error;
19
20type Phase = extern "C" fn(*mut c_void, i32, i32, i64, i64);
21
22extern "C" {
23 fn lc_omp_max_threads() -> i32;
24 fn lc_knn_one_region(
25 ctx: *mut c_void,
26 pin: i32,
27 n_points: i64,
28 n_bins: i64,
29 n_blocks: i64,
30 bin: Phase,
31 count: Phase,
32 scan_base: Phase,
33 scan: Phase,
34 fill: Phase,
35 select: Phase,
36 team: *mut i32,
37 width: i32,
38 );
39}
40
41struct ThreadScratch {
42 cand: Candidates,
43 heap: KHeap,
44 k: usize,
45}
46
47impl ThreadScratch {
48 fn new(k: usize) -> Self {
49 Self {
50 cand: Candidates::default(),
51 heap: KHeap::new(k),
52 k,
53 }
54 }
55
56 fn ensure(&mut self, k: usize) {
57 if self.k != k {
58 self.heap = KHeap::new(k);
59 self.k = k;
60 }
61 }
62}
63
64struct ScratchPool {
65 hist: Vec<usize>,
66 base: Vec<usize>,
67 chunk_base: Vec<usize>,
68 scratches: Vec<ThreadScratch>,
69}
70
71impl ScratchPool {
72 fn prepare(&mut self, threads: usize, ncell: usize, k: usize) {
73 let rows = threads.saturating_mul(ncell);
74 if self.hist.len() != rows {
75 self.hist.resize(rows, 0);
76 }
77 if self.base.len() != rows {
78 self.base.resize(rows, 0);
79 }
80 if self.chunk_base.len() != threads {
81 self.chunk_base.resize(threads, 0);
82 }
83 if self.scratches.len() < threads {
84 self.scratches
85 .resize_with(threads, || ThreadScratch::new(k));
86 }
87 for scratch in &mut self.scratches[..threads] {
88 scratch.ensure(k);
89 }
90 }
91}
92
93thread_local! {
94 static SCRATCH: RefCell<ScratchPool> = const {
95 RefCell::new(ScratchPool {
96 hist: Vec::new(),
97 base: Vec::new(),
98 chunk_base: Vec::new(),
99 scratches: Vec::new(),
100 })
101 };
102}
103
104struct OmpCtx {
105 xyz: *const [f64; 3],
106 n: usize,
107 cell: *const Cell,
108 ncell: usize,
109 frac: *mut [f64; 3],
110 folded: *mut [f64; 3],
111 key: *mut u32,
112 offsets: *mut usize,
113 occupants: *mut usize,
114 slot_frac: *mut [f64; 3],
115 slot_folded: *mut [f64; 3],
116 counts: *mut usize,
117 hist: *mut usize,
118 base: *mut usize,
119 chunk_base: *mut usize,
120 mesh: *const Mesh,
121 geom: Geom,
122 scratches: *mut ThreadScratch,
123 k: usize,
124 max_reach: i32,
125 mode: u8,
126 side: i32,
128 blocks: [i32; 3],
129 path: crate::simd::Path,
130 time_scan: bool,
131 pop: bool,
132 #[cfg(feature = "timing")]
133 coarse: bool,
134 #[cfg(feature = "timing")]
135 t0: Instant,
136 nn: *mut i32,
137 d2: *mut f64,
138}
139
140fn share(n: usize, slot: i32, nt: i32) -> (usize, usize) {
143 let n = n as i64;
144 let begin = (n * i64::from(slot)) / i64::from(nt);
145 let end = (n * i64::from(slot + 1)) / i64::from(nt);
146 (begin as usize, end as usize)
147}
148
149fn timed(ctx: &OmpCtx, slot: i32, body: impl FnOnce()) {
150 if !ctx.pop {
151 body();
152 return;
153 }
154 let started = Instant::now();
155 body();
156 crate::pop::add_useful(slot as usize, started.elapsed().as_nanos() as u64);
157}
158
159extern "C" fn phase_bin(raw: *mut c_void, slot: i32, nt: i32, begin: i64, end: i64) {
160 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
161 let begin = begin as usize;
162 let end = end as usize;
163 debug_assert_eq!((begin, end), share(ctx.n, slot, nt));
164 timed(ctx, slot, || {
165 let ncell = ctx.ncell;
166 let hist =
170 unsafe { std::slice::from_raw_parts_mut(ctx.hist.add(slot as usize * ncell), ncell) };
171 hist.fill(0);
172 let len = end - begin;
173 let xyz = unsafe { std::slice::from_raw_parts(ctx.xyz.add(begin), len) };
174 let frac = unsafe { std::slice::from_raw_parts_mut(ctx.frac.add(begin), len) };
175 let folded = unsafe { std::slice::from_raw_parts_mut(ctx.folded.add(begin), len) };
176 let key = unsafe { std::slice::from_raw_parts_mut(ctx.key.add(begin), len) };
177 let cell = unsafe { &*ctx.cell };
178 bins::fold_chunk(
179 cell,
180 xyz,
181 ctx.geom.nbin,
182 (frac, folded, key),
183 hist,
184 ctx.path,
185 );
186 });
187}
188
189extern "C" fn phase_count(raw: *mut c_void, slot: i32, nt: i32, begin: i64, end: i64) {
190 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
191 let begin = begin as usize;
192 let end = end as usize;
193 debug_assert_eq!((begin, end), share(ctx.ncell, slot, nt));
194 timed(ctx, slot, || {
195 let ncell = ctx.ncell;
196 let counts = unsafe { std::slice::from_raw_parts_mut(ctx.counts.add(begin), end - begin) };
199 for (offset, bin) in (begin..end).enumerate() {
200 let mut sum = 0usize;
201 for other in 0..nt as usize {
202 sum += unsafe { *ctx.hist.add(other * ncell + bin) };
203 }
204 counts[offset] = sum;
205 }
206 });
207}
208
209extern "C" fn phase_scan_base(raw: *mut c_void, slot: i32, nt: i32, _begin: i64, _end: i64) {
210 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
211 timed(ctx, slot, || {
212 let counts = unsafe { std::slice::from_raw_parts(ctx.counts, ctx.ncell) };
214 let chunk = unsafe { std::slice::from_raw_parts_mut(ctx.chunk_base, nt as usize) };
215 let mut acc = 0usize;
216 for t in 0..nt {
217 let (lo, hi) = share(ctx.ncell, t, nt);
218 let mut sum = 0usize;
219 for count in &counts[lo..hi] {
220 sum += *count;
221 }
222 chunk[t as usize] = acc;
223 acc += sum;
224 }
225 unsafe { *ctx.offsets.add(ctx.ncell) = acc };
226 });
227}
228
229extern "C" fn phase_scan(raw: *mut c_void, slot: i32, nt: i32, begin: i64, end: i64) {
230 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
231 let begin = begin as usize;
232 let end = end as usize;
233 debug_assert_eq!((begin, end), share(ctx.ncell, slot, nt));
234 timed(ctx, slot, || {
235 let ncell = ctx.ncell;
236 let counts = unsafe { std::slice::from_raw_parts(ctx.counts, ncell) };
237 let mut acc = unsafe { *ctx.chunk_base.add(slot as usize) };
238 for (bin, &count) in counts.iter().enumerate().skip(begin).take(end - begin) {
239 unsafe { *ctx.offsets.add(bin) = acc };
240 let mut next_slot = acc;
241 for other in 0..nt as usize {
242 unsafe { *ctx.base.add(other * ncell + bin) = next_slot };
245 next_slot += unsafe { *ctx.hist.add(other * ncell + bin) };
246 }
247 acc += count;
248 }
249 });
250}
251
252extern "C" fn phase_fill(raw: *mut c_void, slot: i32, nt: i32, begin: i64, end: i64) {
253 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
254 let begin = begin as usize;
255 let end = end as usize;
256 debug_assert_eq!((begin, end), share(ctx.n, slot, nt));
257 let _ = nt;
258 timed(ctx, slot, || {
259 let ncell = ctx.ncell;
260 let key = unsafe { std::slice::from_raw_parts(ctx.key, ctx.n) };
265 let frac = unsafe { std::slice::from_raw_parts(ctx.frac, ctx.n) };
266 let folded = unsafe { std::slice::from_raw_parts(ctx.folded, ctx.n) };
267 let next_slots =
268 unsafe { std::slice::from_raw_parts_mut(ctx.base.add(slot as usize * ncell), ncell) };
269 for i in begin..end {
270 let bin = key[i] as usize;
271 let dest = next_slots[bin];
272 next_slots[bin] = dest + 1;
273 unsafe {
274 ctx.occupants.add(dest).write(i);
275 ctx.slot_frac.add(dest).write(frac[i]);
276 ctx.slot_folded.add(dest).write(folded[i]);
277 }
278 }
279 });
280}
281
282extern "C" fn phase_select(raw: *mut c_void, slot: i32, nt: i32, begin: i64, end: i64) {
283 let ctx = unsafe { &*raw.cast::<OmpCtx>() };
284 let begin = begin as usize;
285 let end = end as usize;
286 let _ = nt;
287 #[cfg(feature = "timing")]
288 if ctx.coarse && begin == 0 {
289 crate::simd::add_mesh_ns(ctx.t0.elapsed().as_nanos());
290 }
291 timed(ctx, slot, || {
292 let mesh = unsafe { &*ctx.mesh };
296 let nn = RowsOut(ctx.nn);
297 let dd = if ctx.d2.is_null() {
298 None
299 } else {
300 Some(RowsOut(ctx.d2))
301 };
302 if ctx.side < 0 {
303 match ctx.mode {
304 0 => walk_cells::<0>(mesh, &ctx.geom, ctx.k, ctx.max_reach, (nn, dd), begin, end),
305 1 => walk_cells::<1>(mesh, &ctx.geom, ctx.k, ctx.max_reach, (nn, dd), begin, end),
306 _ => walk_cells::<2>(mesh, &ctx.geom, ctx.k, ctx.max_reach, (nn, dd), begin, end),
307 }
308 return;
309 }
310 let scan = BlockScan {
311 mesh,
312 geom: &ctx.geom,
313 k: ctx.k,
314 max_reach: ctx.max_reach,
315 side: ctx.side,
316 blocks: ctx.blocks,
317 path: ctx.path,
318 time_scan: ctx.time_scan,
319 nn,
320 dd,
321 };
322 let scratch = unsafe { &mut *ctx.scratches.add(slot as usize) };
323 for blk in begin..end {
324 match ctx.mode {
325 0 => select_one_block::<0>(&scan, &mut scratch.cand, &mut scratch.heap, blk),
326 1 => select_one_block::<1>(&scan, &mut scratch.cand, &mut scratch.heap, blk),
327 _ => select_one_block::<2>(&scan, &mut scratch.cand, &mut scratch.heap, blk),
328 }
329 }
330 });
331}
332
333fn assemble(parts: Recycled, nbin: [i32; 3], widths: [f64; 3]) -> Mesh {
334 Mesh {
335 nx: nbin[0],
336 ny: nbin[1],
337 nz: nbin[2],
338 widths,
339 frac: parts.frac,
340 folded: parts.folded,
341 slot_frac: parts.slot_frac,
342 slot_folded: parts.slot_folded,
343 key: parts.key,
344 offsets: parts.offsets,
345 occupants: parts.occupants,
346 counts: parts.counts,
347 next_slot: parts.next_slot,
348 hist: parts.hist,
349 }
350}
351
352fn debug_mesh(mesh: &Mesh, n: usize) {
353 if !cfg!(debug_assertions) {
354 return;
355 }
356 let ncell = mesh.offsets.len() - 1;
357 assert_eq!(mesh.offsets[ncell], n, "bin fill dropped a point");
358 let mut seen = vec![0u8; n];
359 for bin in 0..ncell {
360 let (lo, hi) = (mesh.offsets[bin], mesh.offsets[bin + 1]);
361 assert!(lo <= hi && hi <= n);
362 for pair in mesh.occupants[lo..hi].windows(2) {
363 assert!(pair[0] < pair[1], "bin {bin} is not in index order");
364 }
365 for &i in &mesh.occupants[lo..hi] {
366 assert!(i < n && seen[i] == 0, "occupant {i}");
367 seen[i] = 1;
368 }
369 }
370 assert!(seen.iter().all(|&flag| flag == 1));
371}
372
373pub(super) fn run(
374 xyz: &[[f64; 3]],
375 simbox: &Cell,
376 k: usize,
377 edge: f64,
378 out_nn: &mut [i32],
379 mut out_d2: Option<&mut [f64]>,
380) -> Result<(), Error> {
381 let (nbin, widths, ncell) = bins::grid(simbox, edge)?;
382 let n = xyz.len();
383 let n_points = i64::try_from(n).map_err(|_| Error::Overflow)?;
384 let n_bins = i64::try_from(ncell).map_err(|_| Error::Overflow)?;
385 let width = if crate::on_caller() { 1 } else { 0 };
388 let threads = if width == 1 {
389 1
390 } else {
391 unsafe { lc_omp_max_threads() }.max(1) as usize
392 };
393 let mut parts = bins::take_recycled();
394 if parts.frac.len() != n {
395 parts.frac.resize(n, [0.0; 3]);
396 parts.folded.resize(n, [0.0; 3]);
397 parts.key.resize(n, 0);
398 }
399 if parts.offsets.len() != ncell + 1 {
400 parts.offsets.resize(ncell + 1, 0);
401 }
402 parts.occupants.resize(n, 0);
403 parts.slot_frac.resize(n, [0.0; 3]);
404 parts.slot_folded.resize(n, [0.0; 3]);
405 if parts.counts.len() != ncell {
406 parts.counts.resize(ncell, 0);
407 }
408 let mut mesh = assemble(parts, nbin, widths);
409 let side = super::block_side(mesh.occupants.len(), nbin);
410 let (n_select, blocks, side_i) = if let Some(side) = side {
411 let blocks = [
412 (nbin[0] + side - 1) / side,
413 (nbin[1] + side - 1) / side,
414 (nbin[2] + side - 1) / side,
415 ];
416 let nblock = (blocks[0] as usize)
417 .saturating_mul(blocks[1] as usize)
418 .saturating_mul(blocks[2] as usize);
419 (nblock, blocks, side)
420 } else {
421 (ncell, [0; 3], -1)
422 };
423 let n_blocks = i64::try_from(n_select).map_err(|_| Error::Overflow)?;
424 let cell_min = (widths[0] / f64::from(nbin[0]))
425 .min(widths[1] / f64::from(nbin[1]))
426 .min(widths[2] / f64::from(nbin[2]));
427 let need = (box_diameter(simbox) / cell_min).ceil();
428 let image = nbin[0].max(nbin[1]).max(nbin[2]) / 2 + 2;
429 let max_reach = if need.is_finite() && need < 1.0e7 {
430 (need as i32).saturating_add(3).max(image)
431 } else {
432 image
433 };
434 let geom = Geom {
435 cols: [simbox.a(), simbox.b(), simbox.c()],
436 lengths: simbox.widths(),
437 nbin,
438 widths,
439 };
440 let mode = if simbox.is_ortho() {
441 0
442 } else if simbox.is_restricted() {
443 1
444 } else {
445 2
446 };
447 let path = crate::simd::select();
448 #[cfg(feature = "timing")]
449 let time_scan = crate::simd::scan_timing_enabled();
450 #[cfg(not(feature = "timing"))]
451 let time_scan = false;
452 #[cfg(feature = "timing")]
453 let coarse = crate::simd::coarse_timing_enabled();
454 let pop = crate::pop::enabled();
455 let pin = i32::from(super::PIN_LEAST_LOADED.load(std::sync::atomic::Ordering::Relaxed));
456 let d2 = out_d2
457 .as_mut()
458 .map(|row| row.as_mut_ptr())
459 .unwrap_or(std::ptr::null_mut());
460
461 SCRATCH.with(|slot| {
462 let pool = &mut *slot.borrow_mut();
463 pool.prepare(threads, ncell, k);
464 let mesh_ptr = &mut mesh as *mut Mesh;
468 let frac = unsafe { (*mesh_ptr).frac.as_mut_ptr() };
469 let folded = unsafe { (*mesh_ptr).folded.as_mut_ptr() };
470 let key = unsafe { (*mesh_ptr).key.as_mut_ptr() };
471 let offsets = unsafe { (*mesh_ptr).offsets.as_mut_ptr() };
472 let occupants = unsafe { (*mesh_ptr).occupants.as_mut_ptr() };
473 let slot_frac = unsafe { (*mesh_ptr).slot_frac.as_mut_ptr() };
474 let slot_folded = unsafe { (*mesh_ptr).slot_folded.as_mut_ptr() };
475 let counts = unsafe { (*mesh_ptr).counts.as_mut_ptr() };
476 let mut ctx = OmpCtx {
477 xyz: xyz.as_ptr(),
478 n,
479 cell: simbox,
480 ncell,
481 frac,
482 folded,
483 key,
484 offsets,
485 occupants,
486 slot_frac,
487 slot_folded,
488 counts,
489 hist: pool.hist.as_mut_ptr(),
490 base: pool.base.as_mut_ptr(),
491 chunk_base: pool.chunk_base.as_mut_ptr(),
492 mesh: mesh_ptr,
493 geom,
494 scratches: pool.scratches.as_mut_ptr(),
495 k,
496 max_reach,
497 mode,
498 side: side_i,
499 blocks,
500 path,
501 time_scan,
502 pop,
503 #[cfg(feature = "timing")]
504 coarse,
505 #[cfg(feature = "timing")]
506 t0: Instant::now(),
507 nn: out_nn.as_mut_ptr(),
508 d2,
509 };
510 let mut team = 0i32;
511 unsafe {
512 lc_knn_one_region(
513 (&mut ctx as *mut OmpCtx).cast(),
514 pin,
515 n_points,
516 n_bins,
517 n_blocks,
518 phase_bin,
519 phase_count,
520 phase_scan_base,
521 phase_scan,
522 phase_fill,
523 phase_select,
524 &mut team,
525 width,
526 );
527 }
528 TEAM.store(team.max(1) as usize, std::sync::atomic::Ordering::Relaxed);
529 if pop {
530 crate::pop::set_threads(team.max(1) as usize);
531 }
532 });
533 debug_mesh(&mesh, n);
534 Ok(())
535}