Skip to main content

Crate linkcell

Crate linkcell 

Source
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

  1. Fold every position into the primary cell (Cell::fractional, then Cell::cartesian).
  2. 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.
  3. 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.
CellGraph
Periodic cell adjacency with pair-count edge weights.
CellGrid
Fractional bins and the point count in each bin.
MeshCut
Assignment, the grid it was cut on, and the bin of every point.
NeighborCalc
Reused buffers for repeated lc_vesin_neighbors calls through the C ABI.
Neighbors
One source’s k nearest neighbours, nearest first.
Pair
One atom-image pair inside the cutoff.
PairColumns
Cutoff rows as columns: i[t], j[t], shift[t], dist2[t].
PartRequest
One call to partition or partition_graph.
PartScore
Cut, imbalance, and halo fraction of one assignment.
PbcQuery
Options for pairs_within_pbc.
RankMask
Point mask of one rank after its halo is painted.
ReplicaList
Shared candidate list and one filtered frame per bead.
SkinList
Cutoff list with a Verlet skin.
VesinOptions
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, target j, shift S, squared distance. The C++ linkcell::ShiftedPair has this layout.

Enums§

Error
Why a search could not run.
Method
How partition_graph cuts 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 read rows.
cell_graph
Cell grid plus pair-count arcs from pairs_within.
cell_grid
Point counts on the mesh pairs_within would 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 p to each packed candidate in qs.
dist2_ortho_diffs
Orthorhombic wrap of precomputed differences, one reciprocal per axis.
dist2_pairs
Squared MIC distances for packed pair lists ps and qs.
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^bits cells 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 entry lc_knearest_csr for 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: xyz is n_frames * n points, out_* are n_frames * n * k. One shared cell. mask is length n or None.
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_within with half set.
lc_cell_grid⚠
Point counts on the linked-cell mesh.
lc_for_slabs
Run cb(ctx, begin, end) over disjoint spans of 0..n on the pool selected by lc_set_threads. One thread runs the whole span on the caller. The spans cover 0..n exactly once.
lc_halo⚠
Ghost cells of domain. A null out_ghost queries *out_count.
lc_halo_width⚠
Bin radii for cutoff * depth. out_width receives three counts.
lc_knearest⚠
k-nearest neighbours for n points.
lc_knearest_csr⚠
The k-nearest graph of n points as CSR.
lc_knearest_d2⚠
Like lc_knearest, and write squared distances into out_d2.
lc_knearest_many⚠
Frame-major batch. xyz is n_frames * n packed triples. out_nn / out_d2 are n_frames * n * k. One shared cell. mask is length n or NULL. out_d2 may be NULL.
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_rows with a periodicity mask.
lc_pairs_within_rows⚠
lc_pairs_within with one array of lc_pair rows.
lc_partition⚠
Domain id of each cell.
lc_partition_weights⚠
Domain of each cell from caller-supplied weights.
lc_set_continuation
Run cb at the end of this thread’s next lc_knearest, still inside its pool. A null cb clears 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 device partition. The GPU library calls this from a static initializer when it is loaded. A null f removes it, and the device partition then reports no device.
lc_set_threads
Choose the Rayon width for later searches. n == 0 leaves it unset: the search starts on the calling thread with Rayon’s and OpenMP’s own widths. n == 1 runs the whole search on the calling thread and starts no thread. n < 0 selects one thread.
lc_stencil_builds
How many partner stencils have been built in this process.
lc_team_run⚠
Run nstages stages in one parallel region on the pool selected by lc_set_threads, the caller one of the workers (see team). Stage s is chunks[s] calls of fn_(ctx, s, chunk, worker), in any order and on any worker; every chunk of a stage returns before any chunk of the next starts. worker is fixed for one worker thread during the call and below lc_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_run started now may use: the worker index 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 reach of an owned atom are 1.
mark_reached
Mark points owned by domain or within reach of 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, then y, then x.
morton_key
Packed Morton key. Coordinates at or above 2^21 do 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_within would write, without writing them.
pairs_within_into
Write pairs_within into out, 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. device needs the point bins, so it returns Error::NoDevice here. Build the assignment from points with partition when 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 * 2 C buffer.
replicate_graph
Place copies disjoint copies of graph side 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_SIMD when 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 Instant reported on this process.
wrap_many
Minimum-image wrap of packed difference vectors.