<!-- https://docs.dseams.info/user/howto/neighbour-lists.md -->

# Cutoff neighbour lists {#cutoff-neighbour-lists}

Build the cutoff list, choose the thread count, and read the pinned
session that compared it with vesin, freud, matscipy, mdapy, and OVITO.
The calls are on the [API map](../../reference/api.md).
The drivers are on [Benchmarks](benchmarks.md).

## Box {#box}

`nneigh::orthoFullCsr` reads `PointCloud.box`.

A length of 3 is orthorhombic. `box[0..2]` are `Lx, Ly, Lz`.
The minimum image on each axis is `dr - L * floor(dr / L + 0.5)`.

A length of at least 6 is a restricted triclinic LAMMPS dump.
`box[0..2]` are the bound spans `xhi_bound - xlo_bound` and so on.
`box[3..5]` are the tilt factors `xy, xz, yz` in the same length unit.
`boxLow` is the bound origin.
Any other length makes the call return false.
`gen::makeFracBox` recovers the edge lengths

- `lx = xspan - max(0, xy, xz, xy+xz) + min(0, xy, xz, xy+xz)`
- `ly = yspan - max(0, yz) + min(0, yz)`
- `lz = zspan`

and the perpendicular widths `wx, wy, wz`.
The cartesian image of a fractional shift `(sx, sy, sz)` is

- `x = lx * sx + xy * sy + xz * sz`
- `y = ly * sy + yz * sz`
- `z = lz * sz`

Cells are sized from those perpendicular widths.
When every axis has reach 1 and at least two cells, both boxes walk
the 27 image shifts filled once for that call.
A reach above 1 uses the fractional minimum image.
The pair is kept when the squared length is strictly below the cutoff
squared.

`nneigh::setBoxFromLammpsEdges` stores edge lengths plus tilt as that
dump box. A zero tilt stays three spans, so the orthorhombic loop is
unchanged. `seams read` prints the three bound spans. When the box has
six entries it appends `xy`, `xz`, and `yz`, each followed by its value.
There is no tilt flag.

## CSR {#csr}

`offsets` has length `nop + 1`.
`cols[offsets[i] .. offsets[i + 1]]` is sorted by cloud index and has
no self entry.
A null subset is every atom.
`half` keeps the pair only on the lower cloud index.
The pair set does not depend on the thread count.
The call returns false when the box is not usable.
Outside a parallel region the scratch stays allocated and is refilled
on the next call. Inside one, the call uses a local scratch.

`idRowsFromCsr` and `indexRowsFromCsr` put the atom itself first and
then the CSR partners, as atom ids or as cloud indices.
`halfIdRowsFromCsr` keeps the pair on the lower index.
`neighListO`, `halfNeighList`, and `getNewNeighbourListByIndex` build
this CSR and then those rows.

`CutoffSkin` builds candidates at `cutoff + skin`.
`update` calls `moved`. That is true when the atom count, the box, the
origin, or any minimum-image displacement exceeds `skin / 2`, and also
when the subset pointer or the half flag changes.
Otherwise `lastReused` is true.
`filter` then copies the wide CSR down to pairs still inside `cutoff`.
`moved` and `filter` are private. `offsets` and `cols` are the filtered
list.

`chill::classifyBondsCsr` labels the bonds of that CSR.
`chill::chillPlusFromCsr` keeps the four nearest of each row, accumulates
the real spherical harmonics at `l = 3`, and returns the cubic count.
`symm::diamondFromCsr` accepts the CSR and does not read it. The shell
kernel builds its own 3.5 Å bonds. A clean cubic shell is 1, a clean
hexagonal shell is 0, stacking-disordered ice is 2, and any other shell
is -1.
`chill::steinhardtQlCutoff` builds the CSR for one atom type and returns
`q_l`. The Lechner-Dellago average is filled only when `average` is true.
Degrees other than 3, 4, 6, 8, and 12 return zeros. `l = 12` runs on the
host.

## Threads {#threads}

`orthoFullCsr` sets `omp_set_dynamic(0)` and sizes its scratch for
`omp_get_max_threads`.
The thread count is `OMP_NUM_THREADS`.
`orthoFullCsr`, `CutoffSkin`, and the row converters take no thread
argument.
Outside a parallel region, an orthorhombic list whose subset has fewer
than 2048 atoms sets the team to one thread for that call and then
restores the previous count. A triclinic list leaves
`OMP_NUM_THREADS` as it was.
The parallel region starts at 256 atoms.
A call that is already inside an OpenMP region uses one thread.
The skin filter and the row converters use a parallel for from 256
atoms. The row converters skip that team when already inside one.
`nneigh::preferSerialCutoff(true)` keeps `neighListO` on the one-thread
builder.
The pinned session also sets `OMP_PROC_BIND=close`, `OMP_PLACES=cores`,
`OMP_DYNAMIC=FALSE`, and `OMP_WAIT_POLICY=PASSIVE`, and pins the process
with `taskset` to cores `0 .. T-1`.

## Orthorhombic session {#orthorhombic-session}

Ice Ic, lattice constant 6.35 Å, cutoff 3.5 Å.
Each conventional cell holds 8 molecules, so the three frames are
10648, 110592, and 884736 molecules.
The full list has four neighbours per molecule, `4N` directed pairs.
Rows are sorted by cloud index.
The same checksum is produced at 1, 2, 4, and 8 threads.

The host is a KVM guest, kernel 6.12.113+, one socket, Intel Xeon
family 6 model 207 stepping 2, 8 cores, one thread per core, 2.4 GHz.
Caches are L1d 384 KiB, L1i 256 KiB, L2 16 MiB, L3 320 MiB, with 47 GiB
of RAM. The compiler is GCC 15.2.0, release `-O3`.
The guest does not expose hardware performance counters.
vesin is 0.6.2, freud is 3.6.1, matscipy is 1.3.1 with ASE 3.29.0.
Every code returned `4N` pairs. A later sitting, six calls and the
language API, is in [Literature head-to-head](literature-h2h.md). There the
one-thread vesin pool is 51.194 ms and an explicit eight-thread pool
is 22.269 ms, both full lists of 442368 pairs.

| molecules | threads | d-SEAMS CSR | d-SEAMS rows | vesin | freud | matscipy |
| --- | --- | --- | --- | --- | --- | --- |
| 10648 | 1 | 3.709 | 4.160 | 5.674 | 9.508 | 8.458 |
| 10648 | 8 | 0.968 | 1.241 | 2.375 | 9.575 | 9.215 |
| 110592 | 1 | 25.080 | 29.510 | 52.801 | 104.725 | 76.528 |
| 110592 | 8 | 4.554 | 6.077 | 18.159 | 37.994 | 79.412 |
| 884736 | 1 | 244.517 | 291.817 | 1073.681 | 1067.929 | 585.680 |
| 884736 | 8 | 35.618 | 49.400 | 176.231 | 1068.058 | 590.335 |

The d-SEAMS columns in this table, and the triclinic and orthorhombic
columns of the shared-stencil table, were measured in one session on
8 cores. Eight timed calls after one warmup. The process is pinned to
cores 0 .. T-1, with OMP_NUM_THREADS=T, OMP_DYNAMIC=FALSE,
OMP_PROC_BIND=close, OMP_PLACES=cores, and OMP_WAIT_POLICY=PASSIVE.
`bench_cutoff_list` times this orthorhombic CSR and, separately, the
`neighListO` atom-ID rows. `bench_v2` `tilt` and `ortho` time the
shared-stencil CSR. The median is the 5th of the 8 sorted samples. The
interquartile range (IQR) is the linear 75th percentile minus the
linear 25th, with rank (n-1)p. No host name is part of the record. The
vesin, freud, and matscipy columns are the earlier comparison, not
this session.

Orthorhombic CSR median (IQR) in milliseconds, 1 thread then 8:
10648 is 3.709 (0.280) and 0.968 (0.040);
110592 is 25.080 (0.222) and 4.554 (0.322);
884736 is 244.517 (4.625) and 35.618 (1.582).
The row medians (IQR) are 4.160 (0.179) and 1.241 (0.104);
29.510 (0.500) and 6.077 (0.959);
291.817 (12.147) and 49.400 (2.016).

```bash
meson setup build-release --buildtype=release -Dwith_tests=true \
  -Dwith_cli=true -Dwith_mpi=disabled -Dwith_openmp_offload=disabled
ninja -C build-release tests/bench_cutoff_list
NEIGH_BENCH=$PWD/build-release/tests/bench_cutoff_list \
  python3 scripts/bench_neighbours_threads.py
```

`bench_cutoff_list` arguments are the molecule count, the thread count,
and the number of timed repeats. It builds the CSR once before those
repeats. The Python callers in the script discard two builds before
the timed repeats. The comparison environment is vesin 0.6.2,
freud-analysis, matscipy, and ASE. NEIGH_PYTHON selects that
interpreter. Do not install the PyPI package named freud.

## Triclinic session, before the shared stencil {#triclinic-session-before-the-shared-stencil}

The same ice, with `xy = 0.25 L`, `xz = 0.05 L`, `yz = 0.12 L`.
Eight timed calls after one warmup. The median is again the 5th sample.
This shear does not change which molecules are neighbours: the checksum
matches the orthorhombic list.
The numbers below are the list before both boxes shared one stencil.
mdapy is 2.0.0 and OVITO is 3.17.2.
OVITO is timed with a new pipeline on every sample, because a pipeline
caches its output. `LD_LIBRARY_PATH` points at the system libGL
directories for that process only, and is unset for d-SEAMS.

| molecules | threads | d-SEAMS | vesin | freud |
| --- | --- | --- | --- | --- |
| 110592 | 1 | 43.250 | 52.412 | 138.003 |
| 110592 | 8 | 10.873 | 22.582 | 137.605 |
| 884736 | 1 | 643.776 | 1161.736 | 1291.377 |
| 884736 | 8 | 97.572 | 194.677 | 1228.686 |

Each analysis sample builds the CSR and then runs on those rows.
freud has no CHILL+, ring census, or polyhedral template match.

| analysis | molecules | threads | d-SEAMS | mdapy | OVITO |
| --- | --- | --- | --- | --- | --- |
| CHILL+ | 110592 | 1 | 66.261 | 69.247 | 623.611 |
| CHILL+ | 110592 | 8 | 16.797 | 87.292 | 89.249 |
| CHILL+ | 884736 | 1 | 645.498 | 836.341 | 4896.235 |
| CHILL+ | 884736 | 8 | 171.240 | 976.795 | 671.322 |
| rings | 110592 | 1 | 127.569 | 2444.762 | 530.515 |
| rings | 110592 | 8 | 45.258 | 2408.506 | 263.796 |
| rings | 884736 | 1 | 1143.636 | 18713.615 | 5447.092 |
| rings | 884736 | 8 | 387.861 | 18813.651 | 2974.254 |

## Shared stencil {#shared-stencil}

At 110592 molecules the perpendicular widths give 42 by 43 by 43 cells,
against 43 cubed for the cube. Both reaches are 1, so both lists use the
27-cell stencil. The walks test 4,297,540 and 4,204,334 candidate pairs.
The 43.250 ms triclinic row above rebuilt the cell matrix for every
candidate. The shared stencil fills the 27 cartesian images once, and
both boxes call that loop. The d-SEAMS columns are the same 8-core
session as the orthorhombic table: eight samples, median the 5th, IQR
defined there. vesin and freud are the earlier comparison.

| molecules | threads | triclinic | orthorhombic | vesin | freud |
| --- | --- | --- | --- | --- | --- |
| 110592 | 1 | 31.594 | 26.408 | 51.994 | 122.628 |
| 110592 | 8 | 6.879 | 5.136 | 24.911 | 127.350 |
| 884736 | 1 | 448.170 | 305.342 | 1141.327 | 1191.634 |
| 884736 | 8 | 69.177 | 51.959 | 203.597 | 1153.981 |

Shared-stencil CSR median (IQR), triclinic then orthorhombic:
110592 at 1 thread is 31.594 (0.576) and 26.408 (0.392);
at 8 threads, 6.879 (1.388) and 5.136 (0.206);
884736 at 1 thread is 448.170 (27.448) and 305.342 (0.788);
at 8 threads, 69.177 (3.783) and 51.959 (18.696).

CHILL+ on this CSR, the shell label, and the short-hop ring search:

| analysis | molecules | threads | d-SEAMS | mdapy | OVITO |
| --- | --- | --- | --- | --- | --- |
| CHILL+ | 110592 | 1 | 40.862 | 65.618 | 628.011 |
| CHILL+ | 110592 | 8 | 11.297 | 13.545 | 99.530 |
| CHILL+ | 884736 | 1 | 508.358 | 758.383 | 4942.828 |
| CHILL+ | 884736 | 8 | 92.831 | 794.323 | 659.641 |
| diamond | 110592 | 1 | 79.765 | 147.656 | 148.962 |
| diamond | 110592 | 8 | 19.395 | 188.508 | 37.889 |
| diamond | 884736 | 1 | 720.704 | 1190.894 | 1186.497 |
| diamond | 884736 | 8 | 100.959 | 1295.796 | 290.571 |
| rings | 110592 | 1 | 86.970 | 2330.859 | 560.793 |
| rings | 110592 | 8 | 32.497 | 2342.910 | 282.745 |
| rings | 884736 | 1 | 831.572 | 17972.932 | 4855.287 |
| rings | 884736 | 8 | 273.613 | 18066.436 | 2601.361 |

Every molecule of this ice is cubic, so the CHILL+ cubic count is `N`.
The symmetry driver prints the atom count as its sink and the number of
labels other than -1 as its crystal count. Both are `N` on this ice.
The ring counts match mdapy: 221184 at 110592 molecules and
1769472 at 884736. The OVITO ring sink is the particle count, because
FindRings does not write a structure code. PTM has no cubic-ice
template, so its structure code is 0 on this crystal.

```bash
NEIGH_BENCH=$PWD/build-release/tests/bench_v2 \
  python3 scripts/bench_neighbours_v2.py
```

The script times `tilt`, `chill`, `rings`, and `symmetry`.
It does not time the unsheared cell. Those rows are
`bench_v2 ortho N T 8` under the same pin: N is the molecule count
and T is the thread count. Any mode other than `tilt` builds that
cell. The usage line names `tilt`, `chill`, `rings`, and `symmetry`.
Unset, NEIGH_BENCH points at `bbdir-release/tests/bench_v2`.
The Python samples call the function once, take an untimed result,
then time the repeats.
