nordisk/znippy

Static search tree (stree) — benchmarks & the Ragnar gap

The id→position index under the OSM node store (node_store_arrow.rs → STree64Mmap) is a static search tree, derived from Ragnar Groot Koerkamp's static-search-tree (https://github.com/RagnarGrootKoerkamp/static-search-tree, MIT). Source: znippy-zoomies/src/stree.rs, re-exported into osm-katana as crate::stree64.

This chapter records how it is benchmarked (nornir bencher, not criterion), how it compares to Ragnar's published numbers, and the fixes that closed most of the gap.

Acknowledgement. The whole data structure — the cache-line S(+)-tree, the branchless SIMD compare, the prefetched batch traversal — is Ragnar Groot Koerkamp's (MIT, © 2025). Our work here is only measurement and a couple of i64-specific tunings on top of his design and his excellent writeup. Thank you, Ragnar. https://curiouscoding.nl/posts/static-search-tree/

Benched through nornir bencher — no criterion

Per benching.md, znippy has one bench suite and it does not use cargo's bench harness / criterion. The stree benches are Bencher impls in xtask/examples/nornir-bench.rs, registered with register_bench!:

znippy.stree_8mb     result=stree_8mb     log2n=20   (~8 MB, fits L2/L3)
znippy.stree_128mb   result=stree_128mb   log2n=24   (~128 MB, ~L3 on the 3975WX)
znippy.stree_1gb     result=stree_1gb     log2n=27   (~1 GB, RAM-bound; heavy)

stree_1gb is gated behind NORNIR_BENCH_SKIP_HEAVY like the 500 MB stream benches. Each emits reciprocal-throughput metrics in ns/query (the _ns suffix renders "lower is better" — see nornir::bench::unit_of):

binsearch_ns (std slice::binary_search baseline on the same sorted slice), serial_ns (find_exact, one at a time), batch16_ns / batch32_ns / batch128_ns (batch_stream::<P>, software-pipelined + prefetched), plus build_ms, keys, data_mb, and speedup_x (binsearch ÷ best batch — our own "40×" number).

Does the bencher need a criterion connection? No. nornir bencher is a deliberate fork away from criterion (single-shot real-workload numbers, historized by git SHA into Iceberg, gated for >10% regression). The stree benches plug straight into that — no [[bench]], no criterion, no #[bench]. The size sweep (cache → RAM) is the methodology; the warehouse is the history.

Ragnar's published numbers

"Static search trees: 40× faster than binary search" (https://curiouscoding.nl/posts/static-search-tree/), 1 GB of uniform-random u32 (~250 M keys), single thread:

The headline 40× = 1150 → ~27 ns/query single-threaded. The "~9 ns" figure is the multi-threaded best case (~7 ns on 6 threads, RAM-bandwidth limited). Two things he stresses that matter below: hugepages dominate the RAM-bound regime, and throughput saturates around P≈16 in-flight queries (≈12 CPU line-fill buffers) — larger P does not help.

Our numbers (Threadripper PRO 3975WX, 32c, 128 MB L3)

Sparse sorted i64 keys (OSM-node-id shaped), 1 M random present queries (hit workload = full-depth traversal). ns/query, best-of-N.

Default build (cargo build --release, no target flags), after the fixes below:

RUSTFLAGS="-C target-cpu=native" (how the local planet pipeline is built), after the fixes:

Our binary_search baseline (~1050 ns @ 1 GB) matches Ragnar's ~1150 ns, so the harness is sound. In-cache (8 MB) we now hit 19 ns/query — squarely in his range. At 1 GB native we reach 66 ns (16×); the residual vs his ~27 ns is architectural, not a bug (see Remaining levers).

The gap we found, and the fixes

The original code measured ~110 ns @ 1 GB and ~55 ns @ 8 MB batched — ~2–4× off Ragnar even in cache. Diagnosed with a size sweep + a target-cpu=native A/B:

1. AVX2 was never inlined in the default build. count_lt ran is_x86_feature_detected!("avx2") per node and called a separate #[target_feature] function that cannot inline into a non-feature caller — so every node compare (≈9 levels × P) paid a branch + a non-inlined call. Fix: the hot traversals are now generic over the counter (Cnt: Fn), and each public entry dispatches the AVX2 feature check once per query/batch into a #[target_feature(enable="avx2")] wrapper, so count_lt_avx2 inlines straight into the loop. Scalar path retained as the non-AVX2 fallback. This is the bulk of the in-cache win (8 MB batch 55→40 ns default; →19 ns native).

2. The tree never asked for hugepages. With transparent_hugepage=madvise (the common default), a plain Vec tree uses 4 KB pages, so every one of the ≈9 dependent loads per query is also a dTLB miss at 1 GB. Fix: advise_hugepage() (madvise(MADV_HUGEPAGE)) on the tree's backing store in both STree64::new and STree64Mmap::new_with_stride. Best-effort, same style as the existing advise_willneed. This is the RAM-bound win (1 GB batch 108→96 ns default, serial 537→507; native serial 537→315).

Both fixes preserve the public API and all 32 correctness tests (cargo test -p znippy-zoomies stree::), which check every batch variant against serial find_exact.

Remaining levers (not yet taken — need sign-off)

We are at 66 ns vs his ~27 ns at 1 GB native. The residual is inherent to our key type / layout, not a defect:

• i64 / B=8 → ~9 tree levels vs his u32 / B=16 → ~7 levels: ~1.3× more dependent cache-line loads per query, baked into using 64-bit OSM ids in a one-cache-line node. (The tree is built in RAM at load time from the on-disk sorted records — B is not persisted, so it's a free perf knob, not a format decision.)
• Build the planet binary with target-cpu=native. osm-katana runs locally on a known machine; native is a free ~1.5–2× over the default build (table above) with zero code change. Not committed as a global .cargo flag because CI is ubuntu-latest and bench history compares same-machine numbers — set it for the local planet build / release bench instead.
• Interleaved + left-max layout (his last ~30→22 ns step): lookup_batch_interleave exists but isn't the production default; node_store_arrow.rs uses lookup_batch_pipeline::<16>. P≈16 is correct (matches his saturation point; our P=32/128 regress, as his do).
• Multi-threading the batch lookup is the path to his ~7 ns — the planet node-resolution pass is already chunked and could fan out.

Tried & rejected: B=16 two-cache-line node

We prototyped Ragnar's larger-node idea at i64 width — const B = 16 (128 B node, two cache lines, branching factor 17, count_lt_avx2 doing 4 AVX2 compares per node). All 32 correctness tests passed, so it's viable; it's just slower for our workload. Best-batch ns/query, B=8 → B=16:

B=16 helps the serial single-query path (1 GB serial 580→457 ns default — fewer levels, fewer dependent misses), but regresses the batched path at every size — and production (node_store_arrow.rs) uses batched lookup_batch_pipeline::<16>. Why: P-way batching already hides the miss latency that fewer levels would save, so all that remains is B=16's doubled per-node cost (2 line loads + 4 compares + a longer leaf scan). Reverted to B=8. The count_lt_avx2 loop is left B-agnostic (B/4 compares), so the constant is a one-line flip if a serial-heavy workload ever wants it. Negative result, but a clean one — and exactly the trade-off Ragnar discusses for node size.

Reproduce

# Full suite (stree_1gb runs):
cargo run -p xtask --release --example nornir-bench
# Skip the 1 GB stree + other heavy workloads:
NORNIR_BENCH_SKIP_HEAVY=1 NORNIR_BENCH_SKIP_PLANET=1 \
  cargo run -p xtask --release --example nornir-bench
# Native (planet-build-equivalent) numbers:
RUSTFLAGS="-C target-cpu=native" cargo run -p xtask --release --example nornir-bench