# Performance

Three questions: how meshsearch compares to the alternatives, how to choose the
cell side, and what to expect on data unlike the data measured here.

The numbers are from an Apple M1 Pro (10 cores, 16 GiB, macOS 14.5) with
Python 3.14.7, numpy 2.5.3, scipy 1.18.1, scikit-learn 1.9.1, and meshsearch
built with AppleClang at `-O3`. Absolute times are machine-specific; the ratios
between libraries travel better than the microseconds do. Treat a difference
under about 10 per cent as a tie.

## Against cKDTree and BallTree

Three queries are measured, named here as the Python bindings spell them and
identical to their C++ counterparts:

| in the tables | the call | what it asks |
|---|---|---|
| **nearest** | `grid.nearest_object(x, y, z)` | the one nearest object |
| **k = 10** | `grid.nearest_objects(10, x, y, z)` | the ten nearest, nearest first |
| **radius** | `grid.close_objects(x, y, z, rmax)` | every object within `rmax` |

`rmax` is twice the mean separation of the data, which holds the answer at
about 33 neighbours at every size, so one query does the same amount of work as
the data grows. cKDTree and BallTree answer the same three questions, through
`query`, `query` with `k=10`, and `query_ball_point` / `query_radius`, and
return the same neighbours.

The points are uniform in the unit cube, and the queries are 1000 uniform query
points. Query times are **microseconds for one query point**. The per-call rows
call the library once per point; the batched rows hand all 1000 points over in
a single call. Memory is the resident set the structure occupies.

meshsearch is tabulated at two cell sides, because it has one and the trees do
not. One mean separation gives about one object per cell; four gives about 64.

**Cell side of one mean separation**

| points | | meshsearch | cKDTree | BallTree |
|---|---|---|---|---|
| **1e5** | construction (s) | 0.016 | 0.029 | 0.030 |
| | memory (MiB) | 29 | 26 | 88 |
| | nearest, per call | 1.09 | 8.48 | 35.67 |
| | nearest, batched | 0.33 | 0.83 | 3.75 |
| | k = 10, per call | 5.35 | 11.40 | 39.69 |
| | k = 10, batched | 4.13 | 2.03 | 7.77 |
| | radius, per call | 5.36 | 5.97 | 49.11 |
| | radius, batched | 4.16 | 4.00 | 3.83 |
| **1e6** | construction (s) | 0.199 | 0.387 | 0.394 |
| | memory (MiB) | 299 | 53 | 96 |
| | nearest, per call | 1.33 | 9.45 | 53.37 |
| | nearest, batched | 0.42 | 1.31 | 21.67 |
| | k = 10, per call | 13.33 | 12.74 | 63.88 |
| | k = 10, batched | 11.64 | 3.58 | 34.22 |
| | radius, per call | 12.32 | 8.92 | 850.24 |
| | radius, batched | 10.86 | 7.06 | 10.91 |
| **1e7** | construction (s) | 2.808 | 5.822 | 6.326 |
| | memory (MiB) | 1,495 | 400 | 177 |
| | nearest, per call | 1.79 | 8.66 | 81.26 |
| | nearest, batched | 0.58 | 1.42 | 51.85 |
| | k = 10, per call | 21.86 | 12.56 | 103.54 |
| | k = 10, batched | 16.03 | 3.86 | 73.02 |
| | radius, per call | 17.17 | 10.78 | 9,005.79 |
| | radius, batched | 14.40 | 8.79 | 23.17 |

**Cell side of four mean separations**

| points | | meshsearch | cKDTree | BallTree |
|---|---|---|---|---|
| **1e5** | construction (s) | 0.011 | 0.029 | 0.027 |
| | memory (MiB) | 10 | 28 | 87 |
| | nearest, per call | 2.61 | 8.79 | 34.97 |
| | nearest, batched | 1.91 | 0.91 | 4.04 |
| | k = 10, per call | 12.39 | 10.58 | 39.49 |
| | k = 10, batched | 11.21 | 2.27 | 8.37 |
| | radius, per call | 3.85 | 6.09 | 48.27 |
| | radius, batched | 3.09 | 4.56 | 3.94 |
| **1e6** | construction (s) | 0.134 | 0.365 | 0.366 |
| | memory (MiB) | 123 | 54 | 97 |
| | nearest, per call | 4.63 | 8.69 | 46.85 |
| | nearest, batched | 3.39 | 1.17 | 17.75 |
| | k = 10, per call | 18.60 | 11.61 | 57.03 |
| | k = 10, batched | 17.12 | 3.28 | 26.91 |
| | radius, per call | 6.13 | 8.15 | 811.82 |
| | radius, batched | 4.48 | 6.24 | 9.55 |
| **1e7** | construction (s) | 1.644 | 6.107 | 6.610 |
| | memory (MiB) | 672 | 400 | 177 |
| | nearest, per call | 8.42 | 9.60 | 85.37 |
| | nearest, batched | 7.78 | 1.43 | 53.83 |
| | k = 10, per call | 34.34 | 13.73 | 104.41 |
| | k = 10, batched | 32.37 | 4.54 | 76.44 |
| | radius, per call | 9.71 | 11.08 | 10,016.19 |
| | radius, batched | 8.76 | 9.22 | 26.97 |

### What the numbers say

**Construction is faster everywhere** — about 2x against cKDTree at one mean
separation, 2.6x to 3.7x at four.

**Memory is the weakest column at a fine cell side and the strongest at a
coarse one.** At one mean separation meshsearch holds 1.5 GiB at 1e7 against
cKDTree's 400 MiB; at four mean separations, 672 MiB, and at 1e5 it is a third
of cKDTree's.

**Nearest neighbour, one mean separation: meshsearch wins in both calling
styles.** Per call it is 5x to 8x faster than cKDTree; batched, 0.33, 0.42 and
0.58 microseconds against 0.83, 1.31 and 1.42, so 2.4x to 3.1x faster. At four
mean separations this reverses, 2.1x to 5.4x slower batched, because each cell
holds 64 candidates to test.

**Radius, four mean separations: batched meshsearch is the fastest thing
measured.** 3.09, 4.48 and 8.76 microseconds against batched cKDTree's 4.56,
6.24 and 9.22, so 1.05x to 1.48x faster at all three sizes. At one mean
separation it is 1.0x to 1.6x slower than batched cKDTree.

**k = 10 is the query to take elsewhere.** Against batched cKDTree, meshsearch
is 2.0x to 4.2x slower at one mean separation and 4.9x to 7.1x at four. The gap
is algorithmic, so no cell side and no calling style closes it: if this query
dominates, use a tree.

**BallTree loses every row.** Never call it once per point: its per-call radius
query is 9 milliseconds at 1e7 against 23 microseconds batched.

### Per call or batched

A call from Python costs about 1 microsecond before any work happens, against
7 to 8 for scipy. That is what decides how much batching can win: a query
taking 1 microsecond gets most of its time back, one taking 15 gets under 10
per cent. In these tables batching gains 3.1x to 3.3x on nearest neighbour at
one mean separation and 1.1x to 1.4x on everything else. If a query is already
slow, batching is not what will fix it.

The batched forms exist in the Python bindings only. A C++ caller has no
boundary to cross and writes a loop.

## Choosing the cell side

The cell side is the one tuning parameter, and it is not a single trade-off:
the best choice for one query kind is not the best for another. Query times in
microseconds, with `rmax` again at twice the mean separation.

**1e6 points**

| cell side | cells | objects per cell | build (s) | memory (MiB) | nearest | k = 10 | radius |
|---|---|---|---|---|---|---|---|
| 1 mps | 1,000,000 | 1 | 0.189 | 302 | 1.21 | 11.70 | 10.88 |
| 2 mps | 125,000 | 8 | 0.135 | 103 | 1.92 | 9.01 | 8.04 |
| 3 mps | 39,304 | 25 | 0.129 | 82 | 3.05 | 14.39 | 4.41 |
| 4 mps | 15,625 | 64 | 0.130 | 92 | 4.38 | 19.67 | 6.43 |

**1e7 points**

| cell side | cells | objects per cell | build (s) | memory (MiB) | nearest | k = 10 | radius |
|---|---|---|---|---|---|---|---|
| 1 mps | 10,077,696 | 1 | 2.931 | 1,622 | 1.80 | 16.71 | 14.63 |
| 2 mps | 1,259,712 | 8 | 1.487 | 876 | 3.24 | 15.75 | 14.21 |
| 3 mps | 373,248 | 27 | 1.422 | 741 | 6.72 | 26.94 | 8.29 |
| 4 mps | 157,464 | 64 | 1.459 | 701 | 9.88 | 33.20 | 9.74 |

**Nearest neighbour is the one query that only gets worse as the cell grows,**
by a factor of 3.6 at 1e6 and 5.5 at 1e7 from one mean separation to four. Its
cost follows the objects per cell.

**k-nearest is flat in the middle and worse at the ends,** best at two mean
separations at 1e6 and near-flat from one to two at 1e7, then following the
objects per cell like nearest neighbour.

**A radius query is fastest on a coarse grid, with its best value in the
middle:** 4.41 microseconds at three mean separations against 10.88 at one, and
8.29 against 14.63 at 1e7. What decides its cost is `rmax / cellsize` rather
than either alone — **keep that ratio at or below 1** and the scan stays within
the nearest cells; above it the scan widens sharply.

**Memory falls by about half, not by the drop in cell count.** From one mean
separation to four at 1e7 it goes 1,622 to 701 MiB while the cells fall 64-fold,
because what remains is a floor that does not depend on the cell side: the
grid's copy of the coordinates and its index tables. Past about three mean
separations there is no further saving to have.

### Starting point

- **Mixed use:** two to three mean separations. Nothing is at its worst there —
  at 1e7 it costs 3.24 to 6.72 microseconds on nearest neighbour, 15.75 to
  26.94 on k = 10 and 8.29 to 14.21 on radius.
- **Mostly nearest-neighbour work:** one mean separation, paid for in memory,
  1,622 MiB at 1e7 against 741 at three.
- **Mostly shell or radius queries:** three to four, keeping `rmax / cellsize`
  at or below 1.
- **Memory-bound:** go coarser, but expect little further gain past three mean
  separations.

Worth more than any of the above: run the sweep on your own data, which takes a
few minutes.

```
python benchmarks/benchmark_cellsize.py --sweep
```

## What to expect on other data

**Clustered or masked catalogues will behave differently, and the cell-side
guidance may not survive.** Every number here is uniform random points in a
cube, which is the case a uniform grid suits best. A clustered catalogue, or a
survey footprint with holes, fills some cells heavily and leaves others empty:
queries in the dense regions test far more candidates than the objects-per-cell
average suggests, while the empty cells still cost memory and still get walked.
A tree adapts its subdivision to local density and a uniform mesh does not, so
expect the comparison to move against meshsearch, and expect the best cell side
to differ from the one suggested above. Sweep it.

**Read the fine-grid memory figures as an order of magnitude.** At one mean
separation the grid holds millions of small per-cell vectors, and the resident
set depends on how the allocator grows them; it varies by hundreds of MiB for
the same data. Size a machine from the coarse-grid rows, which are stable, and
treat one mean separation at 1e7 as "one to two gigabytes" rather than a number.

**Nothing here measures threads.** Const members may be called concurrently on
one grid, and non-const members may not, but no figure above says what that
scales like.

**Nothing here measures a mixed or evolving workload.** Each table is one query
kind on a grid built once and left alone. `addObject` and `removeObject` are not
measured, nor is a grid queried after many of them. A grid that has churned
heavily is not the grid measured here: the storage a removed object held is
kept, and objects added later sit at the end of the coordinates rather than
beside the others in their cell, which is where a freshly built grid gets some
of its speed.

**Nothing here measures anisotropic boxes or non-uniform units.** The cell is
cubic and the same on all three axes. Data much longer in one dimension, or
coordinates whose axes are not comparable, gets a cell side that is a compromise
on every axis at once.