KDTree Benchmarks¶
The KDTree benchmark compares fastspatial.KDTree with
scipy.spatial.KDTree using exact Euclidean k-nearest-neighbor queries.
Run The Benchmark¶
Build the extension in release mode before measuring:
uv sync --group benchmark
uv run maturin develop --release
uv run --group benchmark python benchmarks/kdtree_vs_scipy.py
To refresh this page with the latest benchmark table, hardware report, and
Plotly wall-time chart, add --update-docs:
For a smaller focused run:
uv run --group benchmark python benchmarks/kdtree_vs_scipy.py \
--points 10000 \
--dims 16 \
--queries 2000 \
--repeats 9
--update-docs replaces only the generated section below, between the marker
comments, and writes the chart asset into docs/kdtree/assets/.
Default Matrix¶
The default benchmark covers:
| Parameter | Values |
|---|---|
| Point counts | 10_000, 100_000 |
| Dimensions | 2, 3, 4, 5, 7, 8, 9, 12, 16 |
| Queries | 2_000 |
k |
8 |
| Leaf size | 16 |
The output includes build time, Single KNN time, Batched KNN time, environment metadata, and weakest-case speedup summaries.
Current Result¶
Generated on 2026-05-12T20:12:32-04:00 by benchmarks/kdtree_vs_scipy.py.
Benchmark arguments: points=10000,100000, dims=2,8,16, queries=2000, k=8, leafsize=16, repeats=7, seed=42.
Speedup is SciPy median time / fastspatial median time. For example, 1.22x (18% less time) means fastspatial took about 82% of SciPy's wall time for that measurement.
Wall Time Plot¶
The plot uses median wall times from the largest measured 2D and 8D cases. The y-axis is logarithmic so build and query workloads remain readable together.
Hardware and Runtime¶
| Item | Value |
|---|---|
| Python | 3.12.13 |
| NumPy | 2.4.4 |
| SciPy | 1.17.1 |
| fastspatial build profile | release |
| OS | CachyOS |
| Machine | x86_64 |
| CPU | AMD Ryzen 7 3700X 8-Core Processor |
| Logical cores | 16 |
| Physical cores | 8 |
| Memory | 31.3 GiB |
Results¶
| Case | Build ms fastspatial / SciPy | Build speedup | Single KNN ms fastspatial / SciPy | Single KNN speedup | Batched KNN ms fastspatial / SciPy | Batched KNN speedup |
|---|---|---|---|---|---|---|
| 10,000 points / 2D | 1.022 / 2.409 | 2.36x (58% less time) | 4.245 / 51.46 | 12.12x (92% less time) | 0.680 / 2.375 | 3.49x (71% less time) |
| 10,000 points / 8D | 2.051 / 2.491 | 1.21x (18% less time) | 76.55 / 112.2 | 1.47x (32% less time) | 11.28 / 53.58 | 4.75x (79% less time) |
| 10,000 points / 16D | 2.121 / 2.863 | 1.35x (26% less time) | 288.9 / 384.3 | 1.33x (25% less time) | 45.64 / 351.7 | 7.71x (87% less time) |
| 100,000 points / 2D | 12.83 / 24.12 | 1.88x (47% less time) | 4.738 / 50.48 | 10.65x (91% less time) | 0.846 / 3.313 | 3.92x (74% less time) |
| 100,000 points / 8D | 18.80 / 27.73 | 1.48x (32% less time) | 143.0 / 180.6 | 1.26x (21% less time) | 22.85 / 123.7 | 5.41x (82% less time) |
| 100,000 points / 16D | 25.63 / 35.39 | 1.38x (28% less time) | 1,967 / 3,517 | 1.79x (44% less time) | 282.3 / 3,633 | 12.87x (92% less time) |
Weakest Cases¶
| Metric | Weakest case | Result |
|---|---|---|
| Build | 10,000 points / 8D | 1.21x (18% less time) |
| Single KNN | 100,000 points / 8D | 1.26x (21% less time) |
| Batched KNN | 10,000 points / 2D | 3.49x (71% less time) |
Slower Than SciPy¶
- No measured case was slower than SciPy.