flannrust — A Faster nanoflann in Rust with Python Bindings

If you work with point clouds, you do a lot of nearest-neighbor search — normal estimation, Chamfer distances, correspondence search, downsampling. A fast kd-tree matters, and the go-to option has been C++. nanoflann is the one many people reach for: small, fast, header-only, battle-tested for over a decade. But there was no Rust equivalent — so I ported it.

flannrust is a Rust port of nanoflann that returns bit-identical results to the original, matches or beats C++ on most workloads tested, and ships Python bindings faster than SciPy's cKDTree. Every line of Rust was written by an AI agent (Claude Code) under my direction — I wrote the specs, set the standards, reviewed the evidence, and refused to accept any number I couldn't trace back to a run.

Benchmark results: Rust vs C++ kd-tree performance

Everything below was measured on my machine: AMD Ryzen 7 9800X3D, WSL2, both sides compiled with maximum optimization and native CPU tuning. Every workload runs 100 times after warmup, interleaved Rust-then-C++, and the published ratio is the ratio of medians. The full methodology with every command and raw output lives in the repository.

The six workloads below cover the main ways kd-trees get used in practice:

• Build 1M points (parallel) — constructing the tree from a million 3D points using all CPU cores. This is what you pay up front before any queries, and it matters when you rebuild frequently (e.g. dynamic scenes, SLAM).
• Radius search (~1000 hits) — find all points within a distance threshold of a query point. Used in normal estimation, density filtering, and any operation that needs a local neighborhood of variable size.
• KNN dim 8, f64 — find the 10 nearest neighbors in 8-dimensional space with double precision. Tests how well the search scales beyond the typical 3D case — common in feature matching and descriptor spaces. flannrust's hand-written AVX2 distance kernels give it a clear edge here.
• Dynamic KNN after churn — query the tree after inserting and removing points without a full rebuild. Simulates incremental updates like tracking moving objects or streaming point clouds.
• KNN dim 3, k=10 — the bread-and-butter workload: 10 nearest neighbors in 3D. This is what most point cloud processing pipelines spend their time on.
• Dynamic add 20k points — insert 20,000 points into an existing tree. Tests the cost of incremental growth without rebuilding from scratch.

The parallel build win (Rust at 63% of C++ time) comes from a genuinely better design — each worker gets its own node arena and they merge by offsetting indices, so no thread ever contends. Radius search is another solid win (19% faster). The dim-8 win comes from hand-written AVX2 SIMD distance kernels that close the gap LLVM's auto-vectorizer wouldn't. The bottom three rows (dynamic KNN after churn, dim-3, and dynamic add) are within a few percent of each other — both implementations hit the same limits at low dimensions.

Low-dimensional performance. Earlier versions of flannrust were 1.2–1.6× slower than C++ at dimensions 2–3 — the most common point-cloud workload. We traced this to three codegen issues (LLVM if-converting a branch into a serializing cmov, a misguided binary-search insert, and a missing inline hint) and fixed all three. flannrust now lands within a few percent of nanoflann C++ across all tested dim/k combinations, including the compile-time fixed3 specialization, and wins outright on most. The full benchmark suite is in the repository.

How does build time scale with dataset size?

flannrust's parallel build is faster at every point cloud size we tested, but the advantage isn't constant. At small sizes (under 5k points), the gap is enormous — C++ spends more time launching threads than building the tree, while flannrust reuses a warm thread pool. At medium sizes (10k–200k), the speedup settles around 2×. At large sizes (1M+), it narrows from 1.8× to about 1.5× at 5M as both libraries become memory-bandwidth limited. Here's the full sweep from 500 to 5 million points:

The flat C++ line at small sizes (the ~0.5ms floor) is thread creation cost — it dominates the actual tree construction at those sizes. Sequential (single-threaded) builds were also measured and produce nearly identical times for both libraries at every N, confirming that the speed difference comes entirely from the parallel design.

Python bindings: faster than SciPy's cKDTree

flannrust ships Python bindings (pip install via maturin) with a cKDTree-style API. The comparison below is Python-to-Python: all libraries called through their Python interface, same data, same queries.

Leveling the playing field

pynanoflann ships as a GCC-compiled wheel that silently fuses multiply-add operations — a compiler optimization that trades the last bit of floating-point precision for roughly 10% more speed on distance-heavy workloads. flannrust's default metric="l2" preserves bit-exact parity with the C++ reference, which means it deliberately leaves that optimization on the table.

For a fair comparison, the chart below uses metric="l2_fma", which does the same thing pynanoflann gets for free. Think of it as choosing between "identical to C++ at the last decimal" and "matching pynanoflann's compiler settings." The difference between L2 and L2Fma is within 4 ULP — the smallest representable gap in floating-point — invisible for all practical uses. The default metric="l2" remains available for anyone who needs exact reproducibility.

The flannrust baseline (1.0 line) is the flannrust Python wheel with metric="l2_fma".

A few notes on reading this chart. The "build 1M" row compares what each library actually ships: flannrust parallelizes tree construction, the others don't. For a same-rules comparison, see the single-threaded "build 100k" row above it.

The dim-8 f64 row is the closest race: flannrust and pynanoflann are within 3% of each other. At the pure Rust-vs-C++ level, flannrust is 20% faster on this workload thanks to hand-written AVX2 distance kernels. The remaining Python-level gap is binding overhead (per-call query copies, GIL acquire/release). Every workload shown is a flannrust win or statistical tie.

Bit-exact cross-validation against nanoflann C++

Speed means nothing if the port doesn't produce identical results. The project had one non-negotiable rule: the port must match the original, bit for bit.

The original nanoflann 1.12.1 header sits vendored in the repository and gets compiled, through a thin C wrapper, into the same test binaries as the Rust code. Every cross-validation test builds a tree with flannrust and a second tree with the real C++ nanoflann on the same data, runs the same queries against both, and compares. If any of it drifts by a single bit, CI goes red.

• Indices: exact match, no tolerance
• Distances: compared at ULP granularity (unit in the last place — the smallest difference two floats can have)
• Ties: k-th neighbor ties compared as sets
• Float types: f32 and f64
• Dimensions: 2 to 32
• Metrics: five distance metrics (L1, L2, L2Simple, SO2, SO3)
• Datasets: uniform, clustered, all-identical points, exponentially spaced coordinates
• Leaf sizes: 1 to 64
• Queries: 60 seeded queries per configuration

Bit-exact is a surprisingly high bar. Floating-point addition isn't associative at the last bit — (a+b)+c can differ from a+(b+c) — so the port had to match nanoflann's exact accumulation order in every distance computation. The parallel builder also had to be deterministic: it partitions the data before handing work to threads, so the parallel and sequential trees come out identical. If any of that drifts, CI catches it.

The bottom line: across every configuration in the matrix above, flannrust returns the same indices, the same distances, and the same tie-breaking behavior as nanoflann C++. The speed results in this post mean something because the two libraries are provably computing the same thing.

Why is it faster? The design choices that matter

The port follows nanoflann's algorithm exactly — same splits, same traversal order, same tie-breaking. The speed differences come from how the data is laid out in memory and how threads coordinate, not from algorithmic tricks.

• Smaller nodes, less memory traffic. Each node in flannrust is 20 bytes (f32) vs nanoflann's ~48 bytes — same fields, different representation. nanoflann links nodes with 8-byte pointers and uses size_t (8-byte) indices on 64-bit systems, plus 16-byte alignment padding. flannrust stores nodes in a flat array and uses u32 indices (4 bytes), which is enough for any practical tree. The nodes hold the same split information — the saving comes entirely from the pointer-to-index mapping, which is standard practice in Rust. During a search, the CPU walks contiguous memory rather than chasing pointers, which means fewer cache misses per step.

• Lock-free parallel tree building. When building a kd-tree in parallel, nanoflann spawns a new thread for each subtree and has them allocate nodes from a shared pool protected by a mutex. flannrust takes a different approach: it partitions the data first, gives each worker thread its own private arena to build into, then the parent thread merges the results by offsetting the indices. No thread ever waits on another. This is why flannrust's parallel build is 1.5–2× faster — the algorithm is identical, the difference is entirely in how threads share (or don't share) resources.

• Parallel dynamic slot rebuilds. nanoflann's dynamic kd-tree rebuilds internal slots sequentially after insertions and removals. flannrust rebuilds them in parallel — each slot gets its own mutable reference via rayon::scope, so no synchronization is needed. This is a deliberate deviation from the C++ design that also closed the dynamic-add gap: the previous C++ win on add_points is now a statistical tie.

• Persistent thread pool. nanoflann creates and destroys threads on every build call. flannrust reuses rayon's thread pool, which stays warm across calls. For small point clouds this matters more than the actual tree construction — at 500 points, flannrust finishes building in 12 microseconds while nanoflann is still launching threads.

• Hand-written SIMD distance kernels. LLVM does not auto-vectorize the L2 distance loop — verified with perf stat showing zero zmm register usage even at -C target-cpu=native. flannrust adds AVX2 and AVX-512 kernels for the default L2 metric that use per-chunk horizontal reduction to stay bit-exact with the scalar path: the SIMD result matches (d0²+d1²)+(d2²+d3²) to the last bit. The AVX2 kernels give a 20% Rust win at dim 8; on CPUs with AVX-512 support, 512-bit kernels kick in at dim ≥ 32 for even larger gains. The L2Fma variant relaxes bit-exactness for more throughput via fused multiply-add.

Porting a C++ library to Rust with an AI agent

I don't write Rust, so the workflow had to be built around verification rather than code review. The key steps:

1. Spec first. I wrote detailed specifications for every component — what "bit-exact" means, what the test matrix covers, what counts as a valid benchmark. The agent worked from these, not from vague instructions.
2. The C++ original as ground truth. nanoflann 1.12.1 is vendored in the repository and compiled into the same test binaries as the Rust code. Every cross-validation test builds two trees — one Rust, one C++ — on the same data and compares the results. This is how I could verify correctness without reading every line of Rust.
3. Benchmarks with repetitions. Every number in this post comes from 100 repetitions, with interleaved runs, warmup, and published noise floors. Early in the project, five of seven performance conclusions turned out to be wrong once we added proper statistics. Single-run benchmarks are noise generators.
4. Iterate on evidence. When results looked off, I'd share context ("the machine was under load", "nanoflann accumulates distances in this specific order") and the agent would remeasure, correct, and document what changed.

This kind of project — a port of a well-specified library with a testable reference implementation — is a good fit for AI-assisted development. The trust chain runs through the vendored C++ original and the test harness, not through anyone's Rust expertise.

DHH made a similar point in his Rails World 2026 keynote — shipping Rust on the backend without writing it yourself. flannrust is the same idea applied to a numerical library, where bit-exact cross-validation against the C++ original provides a verification chain that code review alone never could.

A note on rigor. I did my best to benchmark this fairly — 100 repetitions per workload, interleaved runs, idle-host measurements, published noise floors. The full benchmark suite is in the repository for anyone who wants the complete picture. But this is ultimately a side project born from curiosity and made possible by AI agents doing the heavy lifting. I'm a 3D vision researcher, not a Rust developer or a FLANN expert. There are almost certainly things I've missed, edge cases I haven't tested, and Rust patterns that someone with real experience would do differently. If you spot something off — a benchmark that's unfair, a design choice that's leaving performance on the table, or a claim that doesn't hold — I genuinely want to hear about it. Open an issue or reach out.

The code is at github.com/sitzikbs/flannrust. Install the Rust crate from crates.io or the Python wheel from PyPI (pip install flannrust). The repository includes the full benchmark suite and the raw output for every number reported in this post.

If you work with point clouds and want a fast kd-tree with Python bindings, give flannrust a try and let me know how it holds up on your workloads.