Expand description
Periodic linked-cell k-nearest neighbour search.
vesin builds cutoff pair lists. nanoflann builds Euclidean KD-trees
without a minimum-image convention. This crate is the missing piece:
Allen and Tildesley’s linked cells, a k-heap per source, and an
index box that grows one axis at a time until the k-th neighbour
cannot lie past an unvisited face. The pair itself is Rapaport’s
cell shift, not a per-pair nearest integer. pairs_within is the
cutoff pair list with integer cell shifts (vesin/tonari ijS);
knearest unique-indexes.
§Algorithm
- Fold every position into the primary cell
(
Cell::fractional, thenCell::cartesian). - Bin the folded points on a fractional mesh. The bin count along each axis uses the perpendicular face width, so a sheared dump is not treated as orthogonal.
- Grow an index box of linked cells. The first visit is the
3×3×3 around the home bin. After that, only an axis whose
unvisited plane is still inside the k-th neighbour grows.
Occupants are stored in cell order. A neighbour cell whose slab
cannot beat the worst heap entry is skipped. The cap is the
space diagonal over the minimum cell height, so a shift outside
{-1,0,1}is still visited when it is the Euclidean image.
The walk basis depends on the cell. An orthorhombic box, including
a rectangular film, is used as stored. A restricted triclinic box
(LAMMPS dump bounds, a CON angle, a hexagonal prism) is
tilt-reduced in place and the shift is triangular. A general
orientation is Minkowski-reduced. pairs_within keeps the
caller’s basis, because the reported shift is an integer
combination of that H.
Pair distances in the walk are not a per-pair minimum-image wrap.
After the fold, a neighbour stencil (jx, jy, jz) contributes
Cell::lattice_shift and Cell::dist2_shifted: a Cartesian
subtract plus one lattice vector (the vesin / LAMMPS ghost trick).
Orthorhombic boxes set the Cell::is_ortho flag and skip the two
3x3 matvecs: three independent wraps, and the shift is a scaled
diagonal. The Highway batch (dist2_ortho_diffs) is that wrap
for a raw difference. knearest_brute uses it on an orthorhombic
box. pairs_within keeps the stencil image and does not wrap
the shifted difference again.
§Why a unique-cell stamp is wrong
A stamp that visits each linked cell once, with a single shift
for every occupant, is not a minimum-image convention. Occupants of
one cell can need different images of the same source (a wide
bin, or a source near a face). The walk keys on the integer stencil
(jx, jy, jz), including wraps: the same rem_euclid bin may
appear with more than one Cell::lattice_shift.
§Output
knearest returns one Neighbors row per input point, nearest
first. knearest_into writes a packed n * k index buffer
(-1 in unused slots), the same layout as lc_knearest.
§Features
parallel is on by default. An unmasked k-nearest query of at least
8192 points runs on one linkcell thread team when this build has it: bin,
count, scan, fill, and select, with a private histogram and scratch
on each thread. Masked and smaller queries use rayon.
--no-default-features drops rayon and serializes the walk (re-enable
capi if the C ABI is still required). The per-source k-heap
(KHeap) stays on the stack for k <= 16; larger k spills to the
heap.
The mesh fold, the k-nearest SoA scan, and cutoff pairs use AVX-512
(eight lanes), AVX2 (four lanes), or NEON (two lanes) when the CPU
has that path. AVX-512 also requires AVX-512VL, POPCNT, and FMA.
AVX2 is selected only when FMA is present too. Stored sums are
separate multiplies and adds, in the scalar order, so every stored
value matches the scalar path bit for bit. Pair screening may use
FMA inside its margin test. The value it stores is the direct sum
of squares. The fold floor is minimage floor_fast, truncation on
every architecture. LINKCELL_SIMD forces scalar, avx2, avx512, or
neon. simd_path reports the path in use. Neighbour rows, pair
rows, and the fold are bitwise identical across thread counts. The
timing feature exports SimdTiming for benchmark counters.
§Examples
Periodic image, not the raw Cartesian vector:
use linkcell::{knearest, Cell};
let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
let rows = knearest(&xyz, &sim, 1, None, None)?;
assert_eq!(rows[0].indices, vec![1]);
assert!((rows[0].dist2[0] - 0.64).abs() < 1e-12);Two occupants of one linked cell (the whole box is a single bin) need different images of the source. A unique-cell stamp with one shift cannot serve both.
use linkcell::{knearest, Cell};
let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.1, 0.0, 0.0], [1.0, 0.0, 0.0], [9.8, 0.0, 0.0]];
let rows = knearest(&xyz, &sim, 2, None, Some(10.0))?;
assert_eq!(rows[0].indices, vec![2, 1]);
assert!((rows[0].dist2[0] - 0.09).abs() < 1e-12);
assert!((rows[0].dist2[1] - 0.81).abs() < 1e-12);Packed n * k indices, unused slots -1:
use linkcell::{knearest_into, Cell};
let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
let mut out = [0; 4];
knearest_into(&xyz, &sim, 2, None, None, &mut out)?;
assert_eq!(out, [1, -1, 0, -1]);The C ABI (lc_*) is the hourglass waist: packed n * k indices,
matching squared distances, and lc_pairs_within for a cutoff
list with the caller’s shift. C++ lives in include/linkcell.hpp
as a RAII header over that ABI.
Structs§
- Cell
- Periodic parallelepiped: columns of H, origin, and an ortho flag.
- Cell
Graph - Periodic cell adjacency with pair-count edge weights.
- Cell
Grid - Fractional bins and the point count in each bin.
- MeshCut
- Assignment, the grid it was cut on, and the bin of every point.
- Neighbor
Calc - Reused buffers for repeated
lc_vesin_neighborscalls through the C ABI. - Neighbors
- One source’s k nearest neighbours, nearest first.
- Pair
- One atom-image pair inside the cutoff.
- Pair
Columns - Cutoff rows as columns:
i[t],j[t],shift[t],dist2[t]. - Part
Request - One call to
partitionorpartition_graph. - Part
Score - Cut, imbalance, and halo fraction of one assignment.
- PbcQuery
- Options for
pairs_within_pbc. - Rank
Mask - Point mask of one rank after its halo is painted.
- Replica
List - Shared candidate list and one filtered frame per bead.
- Skin
List - Cutoff list with a Verlet skin.
- Vesin
Options - Options block, identical in layout to
VesinOptions. - lc_cell
- Periodic parallelepiped. Lattice vectors are a, b, c (same as vesin rows).
- lc_pair
- One cutoff row: source
i, targetj, shiftS, squared distance. The C++linkcell::ShiftedPairhas this layout.
Enums§
- Error
- Why a search could not run.
- Method
- How
partition_graphcuts the cell graph.
Constants§
- DEFAULT_
METHOD - Default method.
Functions§
- cell_
for_ pbc - Lattice for
periodic. A zero row on an open axis is replaced by a unit axis so the periodic rows still define a cell. A fully open mask does not readrows. - cell_
graph - Cell grid plus pair-count arcs from
pairs_within. - cell_
grid - Point counts on the mesh
pairs_withinwould use. - curve_
split_ device - Curve split on the device, including the copies both ways.
- derived_
balance - Balance allowed by one indivisible cell.
- derived_
balance_ f64 - The derived bound as a real ratio, for drivers that take a float.
- dist2_
many - Squared MIC distances from
pto each packed candidate inqs. - dist2_
ortho_ diffs - Orthorhombic wrap of precomputed differences, one reciprocal per axis.
- dist2_
pairs - Squared MIC distances for packed pair lists
psandqs. - edge_
cut - Undirected edge cut.
- exclusive_
prefix - Exclusive prefix.
out[i + 1] - out[i] = values[i],out[0] = 0. - fused_
masks - Paint each rank’s halo while walking the cells that rank owns.
- halo
- Ghost cells of
domain. - halo_
width - Bin radii that cover a length of
cutoff * depth. - hilbert_
key - Hilbert index on a cube of
2^bitscells per axis (Skilling, 2004). - histogram
- Histogram of flat bin ids.
- knearest
- k-nearest neighbours of every point (or of the masked subset).
- knearest_
brute - Brute-force k-nearest. Tests and small systems only.
- knearest_
csr - The k-nearest graph as CSR
(offsets, columns); see the C entrylc_knearest_csrfor the row order. - knearest_
into - Write k-nearest indices, nearest first, into caller storage.
- knearest_
into_ d2 - Write k-nearest indices and squared distances, nearest first.
- knearest_
into_ many - Frame-major batch:
xyzisn_frames * npoints,out_*aren_frames * n * k. One shared cell.maskis lengthnorNone. - knearest_
team_ threads - Threads that ran the last k-nearest query.
- lc_
cell_ ⚠graph - Periodic cell adjacency. Edge weights are pair counts from
lc_pairs_withinwithhalfset. - lc_
cell_ ⚠grid - Point counts on the linked-cell mesh.
- lc_
for_ slabs - Run
cb(ctx, begin, end)over disjoint spans of0..non the pool selected bylc_set_threads. One thread runs the whole span on the caller. The spans cover0..nexactly once. - lc_halo⚠
- Ghost cells of
domain. A nullout_ghostqueries*out_count. - lc_
halo_ ⚠width - Bin radii for
cutoff * depth.out_widthreceives three counts. - lc_
knearest ⚠ - k-nearest neighbours for
npoints. - lc_
knearest_ ⚠csr - The k-nearest graph of
npoints as CSR. - lc_
knearest_ ⚠d2 - Like
lc_knearest, and write squared distances intoout_d2. - lc_
knearest_ ⚠many - Frame-major batch.
xyzisn_frames * npacked triples.out_nn/out_d2aren_frames * n * k. One shared cell.maskis lengthnorNULL.out_d2may beNULL. - lc_
last_ error - Thread-local last-error string from this thread’s most recent
lc_knearest. - lc_
mesh_ ⚠cut - Domain of each cell and the bin of each point, from one mesh cut.
- lc_
num_ threads - Width selected by
lc_set_threads, or the global pool when unset. - lc_
owned_ ⚠mask - Owned points are 2. Points in a cell painted from the owned walk are 1.
- lc_
pairs_ ⚠open - Cartesian half pair list of an open cluster.
- lc_
pairs_ ⚠within - Cutoff pairs with the vesin / tonari shift
S. - lc_
pairs_ ⚠within_ pbc lc_pairs_within_rowswith a periodicity mask.- lc_
pairs_ ⚠within_ rows lc_pairs_withinwith one array oflc_pairrows.- lc_
partition ⚠ - Domain id of each cell.
- lc_
partition_ ⚠weights - Domain of each cell from caller-supplied weights.
- lc_
set_ continuation - Run
cbat the end of this thread’s nextlc_knearest, still inside its pool. A nullcbclears it. The hook belongs to the calling thread; a search started on another thread does not run it. The search clears nothing by itself: the caller drops the hook when the call returns. - lc_
set_ gpu_ curve_ split - Install the device curve split used by the
devicepartition. The GPU library calls this from a static initializer when it is loaded. A nullfremoves it, and the device partition then reports no device. - lc_
set_ threads - Choose the Rayon width for later searches.
n == 0leaves it unset: the search starts on the calling thread with Rayon’s and OpenMP’s own widths.n == 1runs the whole search on the calling thread and starts no thread.n < 0selects one thread. - lc_
stencil_ builds - How many partner stencils have been built in this process.
- lc_
team_ ⚠run - Run
nstagesstages in one parallel region on the pool selected bylc_set_threads, the caller one of the workers (seeteam). Stagesischunks[s]calls offn_(ctx, s, chunk, worker), in any order and on any worker; every chunk of a stage returns before any chunk of the next starts.workeris fixed for one worker thread during the call and belowlc_team_width, so it can index per-worker scratch. No worker that has not started holds up a stage or the return. - lc_
team_ width - Workers an
lc_team_runstarted now may use: theworkerindex it passes is below this. - lc_
version - Library version string. Process-static, NUL-terminated. Do not free.
- lc_
within_ ⚠reach - Owned points are 2. Ghosts within
reachof an owned atom are 1. - mark_
reached - Mark points owned by
domainor withinreachof one of its atoms. - mesh_
cut - Cut the mesh once and keep the point bins.
- morton_
cmp - Morton order matching
morton_key: at each bit,z, theny, thenx. - morton_
key - Packed Morton key. Coordinates at or above
2^21do not fit. - owned_
cells - Cells of each domain, in cell order.
- pairs_
open - Cartesian half pair list of an open cluster.
- pairs_
within - Pairs with
dist2 < cutoff², one row per atom-image. - pairs_
within_ columns - The same rows as
pairs_within, as four columns. - pairs_
within_ count - How many rows
pairs_withinwould write, without writing them. - pairs_
within_ into - Write
pairs_withinintoout, keeping its allocation. - pairs_
within_ pbc - Cutoff pairs with a periodicity mask.
- partition
- Domain id of each cell. See
PartRequest. - partition_
graph - Partition an existing graph.
deviceneeds the point bins, so it returnsError::NoDevicehere. Build the assignment from points withpartitionwhen the device path is required. - pin_
knearest_ to_ least_ loaded - Place the k-nearest team workers on the least-loaded CPUs.
- pop_
efficiencies - POP3 factors for one run: load balance, communication efficiency, parallel efficiency.
- pop_
engage - Turn POP3 counters on for this process.
- pop_
prepare - Give every worker a slot. Call once before the timed repetitions.
- pop_
reset - Zero the useful-time counters. Slot assignment stays.
- pop_
snapshot - Useful nanoseconds on each worker, in slot order.
- prefix_
assign - Weighted prefix of
order. A zero total weight treats every cell as weight 1. - profile_
ns - Critical-path wall time, in nanoseconds.
- profile_
reset - Zero the phase counters used by the next partition.
- rank_
mask - Halo and point mask for one rank, from that rank’s own cells.
- reduce_
pairs - Drop self images and collapse duplicate
(i, j)rows. - reduce_
pairs_ packed - Same reduction over a packed
n * 2C buffer. - replicate_
graph - Place
copiesdisjoint copies ofgraphside by side along x. - score
- Cut, imbalance, and halo fraction.
- shutdown_
knearest_ team - Join the standing k-nearest team.
- simd_
path - Name of the path the next fold or scan takes:
LINKCELL_SIMDwhen it is set, otherwise the widest path this CPU runs. - stencil_
builds - How many partner stencils have been built since the process started.
- timer_
resolution_ ns - Smallest advance
Instantreported on this process. - wrap_
many - Minimum-image wrap of packed difference vectors.