Skip to main content

linkcell/
knn_fused.rs

1//! One thread team for an unmasked k-nearest query.
2//!
3//! Bin, count, scan, fill, and select are phases of one standing team in
4//! `src/knn_region.c`.
5//! Each slot keeps a private histogram, a private next-slot row, and a private
6//! candidate list. Slots meet only at the barriers between phases.
7
8use 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    /// Negative when the shell walk runs per cell instead of per block.
127    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
140/// Static share, as `schedule(static)` divides. The same division is in
141/// `src/knn_region.c`.
142fn 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        // Safety: slot `slot` owns histogram row `slot`, and `begin..end`
167        // is that slot's disjoint slice of the point arrays. One team
168        // thread runs each slot.
169        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        // Safety: this slot writes `counts[begin..end]` only. Histograms are
197        // read-only after the bin barrier.
198        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        // Safety: slot 0 alone runs this. `counts` is complete.
213        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                // Safety: this slot owns every thread's next slot at `bin`,
243                // and other slots own other bins.
244                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        // Safety: key, frac, and folded are read-only after the scan barrier.
261        // This slot's next-slot row is private. Each next slot was the
262        // exclusive start of this slot's points in that bin, so the
263        // destinations do not alias another slot.
264        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        // Safety: the mesh is complete and read-only. Slot `slot` owns
293        // `scratches[slot]`. Each source is in one cell, and each cell is
294        // in one block, so output rows do not alias.
295        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    // A one-thread search runs the region on the caller whatever width
386    // the caller's OpenMP team has.
387    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        // Field pointers come from one raw mesh pointer. Phases before
465        // select write disjoint ranges through them. Select then reads
466        // the mesh, after those borrows have ended at the barriers.
467        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}