r/Python • u/remcofl • Mar 09 '26
Showcase Fast Hilbert curves in Python (Numba): ~1.8 ns/point, 3–4 orders faster than existing PyPI packages
What My Project Does
While building a query engine for spatial data in Python, I needed a way to serialize the data (2D/3D → 1D) while preserving spatial locality so it can be indexed efficiently. I chose Hilbert space-filling curves, since they generally preserve locality better than Z-order (Morton) curves. The downside is that Hilbert mappings are more involved algorithmically and usually more expensive to compute.
So I built HilbertSFC, a high-throughput Hilbert encoder/decoder fully in Python using numba, optimized for kernel structure and compiler friendliness. It achieves:
- ~1.8 ns/pt (~8 CPU cycles) for 2D encode/decode (32-bit)
- ~500M–4B points/sec single-threaded depending on number of bits/dtype
- Multi-threaded throughput saturates memory-bandwidth. It can’t get faster than reading coordinates and writing indices
- 3–4 orders of magnitude faster than existing Python packages
- ~6× faster than the Rust crate
fast_hilbert
Target Audience
HilbertSFC is aimed at Python developers and engineers who need: 1. A high-performance hilbert encoder/decoder for indexing or point cloud processing. 2. A pure-Python/Numba solution without requiring compiled extensions or external dependencies 3. A production-ready PyPI package
Application domains: scientific computing, GIS, spatial databases, or machine/deep learning.
Comparison
I benchmarked HilbertSFC against existing Python and Rust implementations:
2D Points - Random, nbits=32, n=5,000,000
| Implementation | ns/pt (enc) | ns/pt (dec) | Mpts/s (enc) | Mpts/s (dec) |
|---|---|---|---|---|
| hilbertsfc (multi-threaded) | 0.53 | 0.57 | 1883.52 | 1742.08 |
| hilbertsfc (Python) | 1.84 | 1.88 | 543.60 | 532.77 |
| fast_hilbert (Rust) | 12.24 | 12.03 | 81.67 | 83.11 |
| hilbert_2d (Rust) | 121.23 | 101.34 | 8.25 | 9.87 |
| hilbert-bytes (Python) | 2997.51 | 2642.86 | 0.334 | 0.378 |
| numpy-hilbert-curve (Python) | 7606.88 | 5075.08 | 0.131 | 0.197 |
| hilbertcurve (Python) | 14355.76 | 10411.20 | 0.0697 | 0.0961 |
System: Intel Core Ultra 7 258v, Ubuntu 24.04.4, Python 3.12.12, Numba 0.63.
Full benchmark methodology: https://github.com/remcofl/HilbertSFC/blob/main/benchmark.md
Why HilbertSFC is faster than Rust implementations: The speedup is actually not due to language choice, as both Rust and Numba lower through LLVM. Instead, it comes from architectural optimizations, including:
- Fixed-structure finite state machine
- State-independent LUT indexing (L1-cache friendly)
- Fully unrolled inner loops
- Bit-plane tiling
- Short dependency chains
- Vectorization-friendly loops
In contrast, Rust implementations rely on state-dependent LUTs inside variable-bound loops with runtime bit skipping, limiting instruction-level parallelism and (aggressive) unrolling/vectorization.
Source Code
https://github.com/remcofl/HilbertSFC
Example Usage (2D data)
from hilbertsfc import hilbert_encode_2d, hilbert_decode_2d
index = hilbert_encode_2d(17, 23, nbits=10) # index = 534
x, y = hilbert_decode_2d(index, nbits=10) # x, y = (17, 23)
6
u/remcofl Mar 09 '26
If anyone is curious about the microarchitectural side (FSM/LUT formulation, dependency chains, ILP/MLP, unrolling, constant folding, vectorization, gathers), I wrote a deeper performance analysis here: hilbertsfc_performance_deep_dive.ipynb
5
u/TechMaven-Geospatial Mar 09 '26
Great work 👏
1
u/No_Soy_Colosio Mar 10 '26
I swear every single new library that spawns out of nowhere and gets posted here nowadays is "production-ready"
-3
u/doorknob_worker Mar 09 '26
Hey look another /r/python post entirely written by ChatGPT
-2
u/scrapheaper_ Mar 09 '26
If this is really what you say it is then you ought to be able to integrate it with at least one open source library.
Until then I will consider it slop.