Skip to main content

linkcell/
lib.rs

1//! Periodic linked-cell k-nearest neighbour search.
2//!
3//! vesin builds cutoff pair lists. nanoflann builds Euclidean KD-trees
4//! without a minimum-image convention. This crate is the missing piece:
5//! Allen and Tildesley's linked cells, a k-heap per source, and an
6//! index box that grows one axis at a time until the k-th neighbour
7//! cannot lie past an unvisited face. The pair itself is Rapaport's
8//! cell shift, not a per-pair nearest integer. [`pairs_within`] is the
9//! cutoff pair list with integer cell shifts (vesin/tonari `ijS`);
10//! [`knearest`] unique-indexes.
11//!
12//! # Algorithm
13//!
14//! 1. **Fold** every position into the primary cell
15//!    ([`Cell::fractional`], then [`Cell::cartesian`]).
16//! 2. **Bin** the folded points on a fractional mesh. The bin count
17//!    along each axis uses the perpendicular face width, so a sheared
18//!    dump is not treated as orthogonal.
19//! 3. **Grow an index box** of linked cells. The first visit is the
20//!    3×3×3 around the home bin. After that, only an axis whose
21//!    unvisited plane is still inside the k-th neighbour grows.
22//!    Occupants are stored in cell order. A neighbour cell whose slab
23//!    cannot beat the worst heap entry is skipped. The cap is the
24//!    space diagonal over the minimum cell height, so a shift outside
25//!    `{-1,0,1}` is still visited when it is the Euclidean image.
26//!
27//! The walk basis depends on the cell. An orthorhombic box, including
28//! a rectangular film, is used as stored. A restricted triclinic box
29//! (LAMMPS dump bounds, a CON angle, a hexagonal prism) is
30//! tilt-reduced in place and the shift is triangular. A general
31//! orientation is Minkowski-reduced. [`pairs_within`] keeps the
32//! caller's basis, because the reported shift is an integer
33//! combination of that H.
34//!
35//! Pair distances in the walk are not a per-pair minimum-image wrap.
36//! After the fold, a neighbour stencil `(jx, jy, jz)` contributes
37//! [`Cell::lattice_shift`] and [`Cell::dist2_shifted`]: a Cartesian
38//! subtract plus one lattice vector (the vesin / LAMMPS ghost trick).
39//! Orthorhombic boxes set the [`Cell::is_ortho`] flag and skip the two
40//! 3x3 matvecs: three independent wraps, and the shift is a scaled
41//! diagonal. The Highway batch ([`dist2_ortho_diffs`]) is that wrap
42//! for a raw difference. [`knearest_brute`] uses it on an orthorhombic
43//! box. [`pairs_within`] keeps the stencil image and does not wrap
44//! the shifted difference again.
45//!
46//! # Why a unique-cell stamp is wrong
47//!
48//! A stamp that visits each linked cell once, with a **single** shift
49//! for every occupant, is not a minimum-image convention. Occupants of
50//! one cell can need **different** images of the same source (a wide
51//! bin, or a source near a face). The walk keys on the integer stencil
52//! `(jx, jy, jz)`, including wraps: the same `rem_euclid` bin may
53//! appear with more than one [`Cell::lattice_shift`].
54//!
55//! # Output
56//!
57//! [`knearest`] returns one [`Neighbors`] row per input point, nearest
58//! first. [`knearest_into`] writes a packed `n * k` index buffer
59//! (`-1` in unused slots), the same layout as `lc_knearest`.
60//!
61//! # Features
62//!
63//! `parallel` is on by default. An unmasked k-nearest query of at least
64//! 8192 points runs on one linkcell thread team when this build has it: bin,
65//! count, scan, fill, and select, with a private histogram and scratch
66//! on each thread. Masked and smaller queries use rayon.
67//! `--no-default-features` drops rayon and serializes the walk (re-enable
68//! `capi` if the C ABI is still required). The per-source k-heap
69//! (`KHeap`) stays on the stack for `k <= 16`; larger `k` spills to the
70//! heap.
71//!
72//! The mesh fold, the k-nearest SoA scan, and cutoff pairs use AVX-512
73//! (eight lanes), AVX2 (four lanes), or NEON (two lanes) when the CPU
74//! has that path. AVX-512 also requires AVX-512VL, POPCNT, and FMA.
75//! AVX2 is selected only when FMA is present too. Stored sums are
76//! separate multiplies and adds, in the scalar order, so every stored
77//! value matches the scalar path bit for bit. Pair screening may use
78//! FMA inside its margin test. The value it stores is the direct sum
79//! of squares. The fold floor is minimage `floor_fast`, truncation on
80//! every architecture. `LINKCELL_SIMD` forces `scalar`, `avx2`, `avx512`, or
81//! `neon`. [`simd_path`] reports the path in use. Neighbour rows, pair
82//! rows, and the fold are bitwise identical across thread counts. The
83//! `timing` feature exports `SimdTiming` for benchmark counters.
84//!
85//! # Examples
86//!
87//! Periodic image, not the raw Cartesian vector:
88//!
89//! ```
90//! use linkcell::{knearest, Cell};
91//!
92//! # fn main() -> Result<(), linkcell::Error> {
93//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
94//! let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
95//! let rows = knearest(&xyz, &sim, 1, None, None)?;
96//! assert_eq!(rows[0].indices, vec![1]);
97//! assert!((rows[0].dist2[0] - 0.64).abs() < 1e-12);
98//! # Ok(())
99//! # }
100//! ```
101//!
102//! Two occupants of one linked cell (the whole box is a single bin)
103//! need different images of the source. A unique-cell stamp with one
104//! shift cannot serve both.
105//!
106//! ```
107//! use linkcell::{knearest, Cell};
108//!
109//! # fn main() -> Result<(), linkcell::Error> {
110//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
111//! let xyz = [[0.1, 0.0, 0.0], [1.0, 0.0, 0.0], [9.8, 0.0, 0.0]];
112//! let rows = knearest(&xyz, &sim, 2, None, Some(10.0))?;
113//! assert_eq!(rows[0].indices, vec![2, 1]);
114//! assert!((rows[0].dist2[0] - 0.09).abs() < 1e-12);
115//! assert!((rows[0].dist2[1] - 0.81).abs() < 1e-12);
116//! # Ok(())
117//! # }
118//! ```
119//!
120//! Packed `n * k` indices, unused slots `-1`:
121//!
122//! ```
123//! use linkcell::{knearest_into, Cell};
124//!
125//! # fn main() -> Result<(), linkcell::Error> {
126//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
127//! let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
128//! let mut out = [0; 4];
129//! knearest_into(&xyz, &sim, 2, None, None, &mut out)?;
130//! assert_eq!(out, [1, -1, 0, -1]);
131//! # Ok(())
132//! # }
133//! ```
134//!
135//! The C ABI (`lc_*`) is the hourglass waist: packed `n * k` indices,
136//! matching squared distances, and `lc_pairs_within` for a cutoff
137//! list with the caller's shift. C++ lives in `include/linkcell.hpp`
138//! as a RAII header over that ABI.
139
140#![deny(missing_docs)]
141
142mod bins;
143mod cell;
144mod error;
145mod knearest;
146mod open_cell;
147mod pairs;
148mod partition;
149mod place;
150mod pop;
151mod replica;
152mod simd;
153mod skin;
154mod skin_simd;
155mod team;
156#[cfg(feature = "capi")]
157mod vesin_abi;
158#[cfg(feature = "capi")]
159pub use vesin_abi::{NeighborCalc, VesinOptions};
160
161pub use cell::{
162    dist2_many, dist2_ortho_diffs, dist2_pairs, reduce_pairs, reduce_pairs_packed, wrap_many, Cell,
163};
164pub use error::Error;
165pub use knearest::{
166    knearest, knearest_brute, knearest_csr, knearest_into, knearest_into_d2, knearest_into_many,
167    knearest_team_threads, pin_knearest_to_least_loaded, shutdown_knearest_team, Neighbors,
168};
169pub use open_cell::{cell_for_pbc, pairs_open, pairs_within_pbc, stencil_builds, PbcQuery};
170pub use pairs::{
171    pairs_within, pairs_within_columns, pairs_within_count, pairs_within_into, Pair, PairColumns,
172};
173pub use partition::{
174    cell_graph, cell_grid, curve_split_device, derived_balance, derived_balance_f64, edge_cut,
175    exclusive_prefix, fused_masks, halo, halo_width, hilbert_key, histogram, mark_reached,
176    mesh_cut, morton_cmp, morton_key, owned_cells, partition, partition_graph, prefix_assign,
177    profile_ns, profile_reset, rank_mask, replicate_graph, score, timer_resolution_ns, CellGraph,
178    CellGrid, MeshCut, Method, PartRequest, PartScore, RankMask, DEFAULT_METHOD,
179};
180pub use pop::{
181    efficiencies as pop_efficiencies, engage as pop_engage, prepare as pop_prepare,
182    reset as pop_reset, snapshot as pop_snapshot,
183};
184pub use replica::ReplicaList;
185pub use simd::simd_path;
186#[cfg(feature = "timing")]
187pub use simd::{simd_timing, SimdTiming};
188pub use skin::SkinList;
189
190#[cfg(feature = "parallel")]
191thread_local! {
192    static ON_CALLER: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
193}
194
195/// True while a search asked to run on one thread is on the calling thread.
196#[cfg(feature = "parallel")]
197pub(crate) fn on_caller() -> bool {
198    rayon::current_thread_index().is_none() && ON_CALLER.with(std::cell::Cell::get)
199}
200
201/// Threads the walk may split over. A one-thread search on the caller is
202/// one: asked from outside a pool, rayon builds its global pool at
203/// `RAYON_NUM_THREADS` or the cpu count, and the walk then splits over it.
204#[cfg(feature = "parallel")]
205pub(crate) fn pool_width() -> usize {
206    if on_caller() {
207        1
208    } else {
209        rayon::current_num_threads()
210    }
211}
212
213/// Runs `work` on this thread as a one-thread search.
214#[cfg(all(feature = "parallel", feature = "capi"))]
215pub(crate) fn run_on_caller<R>(work: impl FnOnce() -> R) -> R {
216    struct Restore(bool);
217    impl Drop for Restore {
218        fn drop(&mut self) {
219            ON_CALLER.with(|flag| flag.set(self.0));
220        }
221    }
222    let _restore = Restore(ON_CALLER.with(|flag| flag.replace(true)));
223    work()
224}
225
226#[cfg(feature = "capi")]
227mod capi;
228#[cfg(feature = "tune")]
229mod tune;
230#[cfg(feature = "capi")]
231pub use capi::*;