# Performance
Benchmark results and how to reproduce them. See the
[README](https://github.com/Filyus/packed_spatial_index#readme) for the API
overview.
Numbers are from one machine and depend on hardware and workload, so treat them as
relative, not absolute. Single-thread rows are measured with the benchmark thread
pinned to one performance core (`BENCH_PIN_CORE`, see [Reproducing](#reproducing));
parallel rows run unpinned so the rayon workers can spread across cores.
## Baselines
The benchmarks below compare against these crate versions:
- [`static_aabb2d_index`](https://crates.io/crates/static_aabb2d_index) `2.1.0` by
Jedidiah McCready — a Rust Flatbush port (build and search).
- [FlatGeobuf](https://flatgeobuf.org/) (`flatgeobuf` `6.0.1`) by Pirmin Kalberer
and Björn Harrtell — a Flatbush-inspired geospatial format (build, search,
persistence).
- [`bvh`](https://crates.io/crates/bvh) `0.12.0` — used in the closest-hit raycast
comparison.
- [`fast_hilbert`](https://crates.io/crates/fast_hilbert) `2.1.0` by Stephan Hügel — a
popular standalone Hilbert curve encoder (encode throughput).
This crate's own design follows the packed Hilbert R-tree of
[flatbush](https://github.com/mourner/flatbush) (Vladimir Agafonkin) and its
Rust port `static_aabb2d_index`.
## Hilbert encoder throughput
The build step sorts items by the Hilbert index of their box centers, so encoder
throughput feeds directly into build time. The `hilbert2d_bench` suite encodes
100,000 random `(u16, u16)` points into an output buffer — independent
iterations the compiler can pipeline and vectorize, which reflects real build
usage. `black_box` wraps only the input and output buffers; wrapping every
element would collapse the measurement into single-call latency and bias it
toward the table-driven path. All Hilbert encoders produce identical indices for
the full `u16` range, so this is a like-for-like speed comparison. Lower is
better.
| `magic_bits` (crate default) | 185 us | 541 Melem/s | 3.5x |
| reference `static_aabb2d_index::hilbert_xy_to_index` | 183 us | 546 Melem/s | 3.5x |
| `lut` (4-bit state machine) | 241 us | 416 Melem/s | 2.7x |
| `loop_rotation` | 998 us | 100 Melem/s | 0.65x |
| `fast_hilbert::xy2h` (order 16) | 644 us | 155 Melem/s | 1.0x |
| `morton` (Z-order baseline, not Hilbert) | 47 us | 2.1 Gelem/s | n/a |
The crate's default `magic_bits` encoder is branchless bit arithmetic that
auto-vectorizes, landing within a few percent of the `static_aabb2d_index`
reference and about 3.5x faster than `fast_hilbert`. `fast_hilbert` is generic
over coordinate width and curve order; that generality costs it throughput on the
fixed `u16` path, though it still beats the naive `loop_rotation`. Note the trade-off
direction flips for single-call latency: in a dependent-accumulation loop the
table-driven `lut` wins because it has no arithmetic dependency chain, while
`magic_bits` is fastest only when iterations are independent (the build case).
The Morton row is a Z-order curve, included only as a locality/speed baseline —
it is not a Hilbert curve and is not used for ordering. Reproduce with
`cargo bench --bench hilbert2d_bench --features bench-internals`.
## 2D competitors
Lower is better. The 2D competitor workload uses 100,000 random AABBs and
1,000 random query boxes; build and search competitors are measured in the
same benchmark suite on the same generated inputs. Persistence rows use the
canonical byte format for 100,000 boxes.
| Full build | 46.82 ms | 6.31 ms | 2.23 ms serial / 1.73 ms parallel | - |
| Search batch | 545.58 us | 440.86 us | 416.19 us | 115.32 us |
| Serialize built tree (fresh buffer) | - | - | 399.11 us | 613.21 us |
| Serialize built tree (reused buffer) | 131.28 us | - | 68.02 us | 160.86 us |
| Load owned tree | 646.49 us | - | 372.24 us | 554.75 us |
| Load zero-copy view | - | - | 34.96 us | n/a |
`SimdIndex2D` searches faster than `Index2D` but **serializes and loads slower**
(roughly 1.5–2.4× in a clean re-measure) — expected, not noise. The on-disk
format is AoS (one canonical format shared by both, so the bytes are
interchangeable). `Index2D` stores AoS too, so `to_bytes` is close to a memcpy
and `from_bytes` close to zero-copy; `SimdIndex2D` stores SoA (separate min/max
columns, what makes its queries fast), so it gathers SoA→AoS to serialize and
scatters AoS→SoA to load. The `reused buffer` row isolates this best:
`Index2D` 68.02 us (≈memcpy) vs `SimdIndex2D` 160.86 us (the transpose). So
`SimdIndex2D` pays at serialize/load to win at query time — prefer it when you
query far more than you persist, and load read-mostly bytes through the zero-copy
`Index2DView` (34.96 us) rather than rebuilding an owned SoA index.
Scalar `Index2D` search versus `static_aabb2d_index` is dataset-sensitive: the
margin between them ranges from a few percent to 1.8× across two runs with the
same item and query counts but different generated inputs — and on the `0xF6B`
inputs the two were the other way round under `2.0.0` of the baseline crate (see
below). Treat the ordering as a property of the data and the baseline version,
not as a standing result:
| `flatgeobuf2d_bench`, seed `0xF6B` (`search_with`) | 440.86 us | 416.19 us | 115.32 us |
| `index2d_bench`, seed `0xB0B` (`search_into_stack` / `search_simd`) | 604.86 us | 335.80 us | 221.17 us |
The `SimdIndex2D` columns are not the same entry point: `search_with` picks a
kernel for the query, while `search_simd` is the explicit wide-4 path, so read
each row against itself rather than down the column.
### `static_aabb2d_index` 2.0.0 vs 2.1.0
`2.1.0` replaced the comparison sort in its build with an in-place MSD radix sort
that stops descending once a range falls inside a single tree node, and it skips
sorting entirely when every Hilbert key is equal. Medians on this crate's
benchmark inputs (uniform random AABBs, `node_size = 16`): the build and `0xB0B`
search rows are over three interleaved runs per version with both binaries pinned
to the same four cores; the `0xF6B` search row is a single pinned run of each
binary, back to back.
| Build 1,000 | 16.67 ms | 10.86 ms | -35% |
| Build 100,000 | 5.99 ms | 6.29 ms | +5% |
| Build 1,000,000 | 73.06 ms | 76.20 ms | +4% |
| Search batch, `index2d_bench` seed `0xB0B` | 619.71 us | 605.08 us | -2% |
| Search batch, `flatgeobuf2d_bench` seed `0xF6B` | 319.35 us | 439.54 us | **+38%** |
So the new sort wins clearly at small `n`, where the node-boundary cutoff removes
most of the work, and loses a few percent at 100k and above, where the MSD
partition passes cost more than the old comparison sort on well-spread keys.
Search moves with the dataset rather than uniformly. The `2.1.0` changelog notes
that internal item ordering may differ, and on the `0xF6B` inputs that ordering
costs the baseline 38% on the query batch, while on `0xB0B` it is unchanged
within noise. The other three search rows of that suite move by 3% or less
between the two runs, and downwards (FlatGeobuf 551.80 → 534.07 us, `Index2D`
425.04 → 421.30 us, `SimdIndex2D` 117.30 → 117.43 us), so this is the baseline
crate changing, not the machine.
Duplicate-heavy build inputs
(`build_degenerate` in `index2d_bench`, 100,000 boxes) move in both directions
too: 64 distinct keys goes 4.92 ms → 3.76 ms, all-identical boxes 5.83 ms →
6.55 ms. None of it changes the standing of this crate's build, which stays
2.4–3.4× faster serial across all four of those shapes.
## 2D vs 3D
Lower latency is better. The `3D speed` column is `2D latency / 3D latency`, so
values above `1.00x` mean 3D is faster. The build workload uses 100,000 boxes
with `node_size = 16`; search and KNN use 1,000 query boxes or points.
| Hilbert encode | production 2D LUT vs 3D nibble LUT | 753.19 us | 1.0053 ms | 0.75x |
| Build | planar XY | 2.2526 ms | 3.8785 ms | 0.58x |
| Build | uniform XYZ | 2.3997 ms | 4.0482 ms | 0.59x |
| Search batch | planar XY | 550.49 us | 672.92 us | 0.82x |
| Search batch | uniform XYZ | 544.18 us | 404.77 us | 1.34x |
| Top-1 | planar XY | 1.0084 ms | 1.2634 ms | 0.80x |
| Top-10 | planar XY | 1.9223 ms | 2.6466 ms | 0.73x |
| Top-1 | uniform XYZ | 1.0070 ms | 1.7472 ms | 0.58x |
| Top-10 | uniform XYZ | 1.9427 ms | 4.1653 ms | 0.47x |
| Serialize built tree (fresh buffer) | 399.11 us | 558.86 us | 0.71x |
| Serialize built tree (reused buffer) | 68.02 us | 96.21 us | 0.71x |
| Load owned tree | 372.24 us | 520.90 us | 0.71x |
| Load zero-copy view | 34.96 us | 36.26 us | 0.96x |
| Serialize built tree (fresh buffer) | 613.21 us | 894.42 us | 0.69x |
| Serialize built tree (reused buffer) | 160.86 us | 263.74 us | 0.61x |
| Load owned tree | 554.75 us | 939.51 us | 0.59x |
## 3D SIMD
The speed column is scalar/serial latency divided by SIMD/parallel latency, so
values above `1.00x` mean the SIMD or parallel path is faster.
| Search batch | uniform XYZ | `Index3D` 406.86 us | `SimdIndex3D` 169.39 us | 2.40x |
| Search batch | flat Z | `Index3D` 1.99 ms | `SimdIndex3D` 846.36 us | 2.35x |
| Build `finish_simd` | uniform XYZ, 200k boxes | serial 10.03 ms | parallel 6.98 ms | 1.44x |
## Large-window range search
When a query fully contains a tree node, the covered-range fast path collects the
whole subtree by copying its contiguous leaf-index range instead of running
per-item overlap tests. This keeps the SIMD indexes from regressing against the
scalar indexes as the window grows: full-extent windows reach parity (both paths
just copy the contiguous index range) and everything smaller stays ahead. On
AVX-512 a masked compress-store collects the matching leaf indices in one
instruction, widening the SIMD lead on dense mid-to-large windows (e.g. the 3D
flat-Z batch above, and the `large` / `thin slab` rows here). Workload: 100,000
boxes over a 10,000-wide space, 1,000 query boxes per window class. Lower is
better.
| small (10–200) | 357.94 us | 127.84 us |
| large (2,000–5,000) | 6.52 ms | 3.97 ms |
| wide sliver | 2.48 ms | 0.87 ms |
| full extent | 11.19 ms | 11.79 ms |
| small (50–300) | 402.71 us | 168.32 us |
| large (2,000–5,000) | 10.38 ms | 4.12 ms |
| thin slab | 3.51 ms | 1.27 ms |
| full extent | 11.65 ms | 11.62 ms |
## Closest-hit raycast vs the `bvh` crate
Closest-hit raycast over the packed index against the
[`bvh`](https://crates.io/crates/bvh) crate (100k boxes, 1,000 rays of length
4,000). For closest hit, "BVH" is a fair hand-rolled ordered traversal over its
SAH tree; for all hits, its broad-phase `traverse_iterator`.
| build (uniform) | **4 ms** | 31 ms |
| closest hit, uniform | **0.72 ms** | 1.6 ms |
| closest hit, clustered | 58 µs | **27 µs** |
| all hits, uniform | **0.5 ms** | 1.5 ms |
| all hits, clustered | 53 µs | **41 µs** |
The packed Hilbert tree builds ~7x faster. All-hits has no early-exit, so the
SIMD slab test wins on uniform scenes but is edged out on heavily clustered ones;
for closest hit a SAH BVH builds a structurally better tree and wins on clustered
scenes. Reproduce with `cargo bench --bench raycast3d_bench --features simd`.
## Ray-triangle closest hit (mesh payload)
A triangle payload plus the index over each triangle's bounding box is a
streamable mesh BVH: `raycast` returns candidate boxes, then
`Ray3D::closest_triangle` runs the exact Moller-Trumbore test only on those. The
records are fixed-width, so the payload drops its offset table (smaller file, one
fewer streamed read) and a view borrows them as a zero-copy typed slice. The
`f32` records (`Triangle3DF32`, 36 bytes) are half the size of `f64`
(`Triangle3D`, 72 bytes) and test 8 at a time through `wide::f32x8`; the `f64`
path is scalar. Workload: 4,096 rays against 4,096 candidate triangles (the
narrow-phase test). Lower is better.
| `f64` `Triangle3D` (scalar) | 121.6 ms | 7.2 ns |
| `f32` `Triangle3DF32` (SIMD) | 47.8 ms | 2.8 ns |
The `f32` SIMD kernel runs ~2.5x faster than scalar `f64` here. Most of that is
the kernel: in pure scalar (no `simd` feature) `f32` is only modestly ahead of
`f64`, since both autovectorize and the win is mainly the 8-wide test. f32's
other benefit is size — half the payload bytes on disk and over the wire.
Reproduce with `cargo bench --bench raytriangle3d_bench --features simd`.
## f32 storage vs f64
The `coord_precision` suite compares compact f32 storage with f64 storage.
Lower is better. Range rows run `search(Box2D)` for 1,000 random query boxes.
Small query boxes cover 0.1% of the coordinate extent per axis; large query
boxes cover 5%. KNN rows use 200 query points with top-8 results.
Quick selector:
- `SimdIndex2D`: 32-byte f64 boxes. Use for exact range queries with many hits
and fastest exact KNN.
- `SimdIndex2DF32::search`: 16-byte rounded f32 boxes, SIMD-batched. In the
AVX-512 runs above it is also the **fastest** range path — ~1.2–1.45× over the
f64 `SimdIndex2D` (half the box bytes plus 16 boxes per SIMD chunk to f64's 8),
so it wins on speed *and* memory, not just memory — at the cost of a few
near-boundary false positives from the outward-rounded boxes. Returns the same
hits as the scalar `Index2DF32` (both round the query inward onto the f32 grid).
Use it when those extra hits are OK, or as a compact first-pass filter.
- `SimdIndex2DF32::*_exact`: 16-byte f32 index plus source f64 boxes. Use when
exact range queries return few hits and compact storage matters. Exact KNN is
available, but f64 is faster in these runs.
- `Index2DF32` / `Index3DF32`: the same 16/24-byte f32 boxes, scalar (no `simd`).
Identical range hits to `SimdIndex2DF32` (a conservative superset from the
outward-rounded boxes) plus `search_exact`; pick it for the half memory
without the SIMD dependency, or to stream a compact file with
`StreamIndex2DF32` / `StreamIndex3DF32` (half the box bytes over the wire).
Scalar f32 trades speed for memory: a 1M-box spot check ran range queries
about 30% slower than `Index3D` and `search_exact` about 45% slower. The query
is rounded once onto the f32 grid so each node compares f32-vs-f32 with no
per-node widen (and bit-identical hits to the f64 test); the residual gap is
the few extra conservative candidates from the outward-rounded boxes, and a
build about 1.7x slower from that rounding. Reach for it when you want half the
memory without a SIMD dependency, not for raw query speed (use
`SimdIndex2DF32` for that).
| small query boxes | 10k | 89 us | 72 us | 78 us |
| small query boxes | 100k | 123 us | 92 us | 102 us |
| small query boxes | 1M | 163 us | 128 us | 146 us |
| large query boxes | 10k | 131 us | 110 us | 298 us |
| large query boxes | 100k | 561 us | 456 us | 1.84 ms |
| large query boxes | 1M | 5.14 ms | 3.52 ms | 17.35 ms |
The `f64 exact` and `f32 rounded` columns use the compress-store collection on
AVX-512, which roughly halves the large-window rows versus the scalar collection;
`f32 exact` runs the per-item refinement callback (no compress) and is unchanged.
| 10k items | 218 us | 233 us | 374 us |
| 100k items | 337 us | 349 us | 493 us |
## Summary
- `Index2D` is the general-purpose path;
- `SimdIndex2D` and `SimdIndex3D` are best for heavier query batches where SIMD
work amortizes well;
- scalar `Index2D` search versus `static_aabb2d_index` depends on the generated
data and query distribution, while `Index2D` build is faster in these runs;
- `Index3D` build and KNN are still slower than `Index2D`, but uniform 3D search
can be faster when Z meaningfully prunes the tree;
- f32 storage halves box memory; exact callbacks trade source-box lookup for
exact results;
- SIMD persistence uses the same canonical bytes as scalar persistence; it pays
an SoA gather/scatter cost but avoids a second file format;
- `any` is often much faster than collecting full result sets when all you need
is existence;
- AVX-512 is not always the fastest path in parallel workloads because CPU
frequency behavior matters.
## Benchmark layout
Performance-related code lives under `benches`:
- `benches/*.rs` are Criterion benchmark suites run with `cargo bench`.
- `benches/tools` is a local developer package for quick comparisons of encoder
variants, sort strategies, node sizes, parallel builds, and SoA layouts.
The local tools use the hidden `bench-internals` feature and are excluded from
the published crate.
```bash
cargo run --release --manifest-path benches/tools/Cargo.toml --bin sortkey_quality_2d
cargo run --release --manifest-path benches/tools/Cargo.toml --bin node_size_3d
```
Benchmark coverage:
- `hilbert2d_bench` compares the crate's Hilbert encoders against the
`static_aabb2d_index` reference and the `fast_hilbert` crate;
- `flatgeobuf2d_bench` compares against FlatGeobuf's packed Hilbert R-tree;
- `index2d_bench` compares build/search paths against `static_aabb2d_index`;
- `index3d_bench` covers 3D build/search/KNN, SIMD search/build, dimension
comparisons, node sizes, and a hidden Morton baseline;
- `persistence_knn2d_bench` / `persistence_knn3d_bench` cover scalar/SIMD
persistence, loaded views, and KNN;
- `raycast3d_bench` compares closest-hit raycast against the `bvh` crate;
- `raytriangle3d_bench` compares `closest_triangle` over `f64` vs compact `f32`
triangle records.
## Build flags
The default `x86-64` target compiles SIMD at SSE2 width (128-bit). To get AVX2 /
AVX-512 codegen, build with one of:
```bash
RUSTFLAGS="-C target-cpu=native" # best for a binary you run on the build machine
RUSTFLAGS="-C target-cpu=x86-64-v3" # portable AVX2 baseline (all v3 CPUs)
```
`native` enables every feature of the building CPU but produces a **non-portable**
binary (an older CPU can fault on a missing instruction); use the `x86-64-v3`
microarchitecture level for binaries you distribute.
The explicit SIMD search / visit / raycast kernels are selected at runtime
(`is_x86_feature_detected!`) and dispatch **AVX-512 → AVX2 → SSE2**: AVX-512 uses
`VPCOMPRESSQ` result collection (~1.6–1.9× over scalar), the AVX2 tier uses a
[left-pack](internals/simd.md) emulation (~1.3–1.6× over the SSE2 fallback on
AVX2-only CPUs), and SSE2 is the floor. So these kernels do **not** need
`target-cpu` to pick the right width. The flag's remaining benefit is widening
the **scalar** autovectorized loops (~1.1–1.3×). (The WASM demo passes
`-Ctarget-feature=+simd128` for the same reason.)
Independently of width, range search and all-hits raycast **prefetch the next
tree node** while the current one is tested — a free latency hint worth ~3–5% on
range and ~5–12% on heavy raycast traversal. See
[internals/prefetch.md](internals/prefetch.md).
## Reproducing
```bash
cargo bench --bench hilbert2d_bench --features bench-internals
cargo bench --bench index2d_bench --no-default-features --features parallel,simd,bench-internals
cargo bench --bench index3d_bench --no-default-features --features parallel,simd,bench-internals
cargo bench --bench persistence_knn2d_bench --no-default-features --features simd,bench-internals
cargo bench --bench persistence_knn3d_bench --no-default-features --features simd,bench-internals
cargo bench --bench flatgeobuf2d_bench --no-default-features --features parallel,simd,bench-internals
cargo bench --bench coord_precision --no-default-features --features f32-storage,simd
cargo bench --bench raycast3d_bench --features simd
cargo bench --bench raytriangle3d_bench --features simd
```
For low-noise numbers, set `BENCH_PIN_CORE=<n>` to pin the measuring thread to one
logical core — a fast performance core (on a hybrid CPU, avoid the efficiency
cores; check your CPU's topology for which logical IDs are performance cores). It
is read at startup and is a no-op when unset:
```bash
BENCH_PIN_CORE=8 cargo bench --bench index2d_bench --features parallel,simd,bench-internals
```
On Linux the self-pin is a no-op; pin from the OS instead, e.g.
`taskset -c 8 cargo bench …`.