nordisk/znippy

.nornir/stree.md

# Static search tree (`stree`) — benchmarks & the Ragnar gap
<!-- nornir:class: reasoning -->

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](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:

| method | ns/query |
|---|---|
| `std` binary search | ~1150 |
| Eytzinger binary search | ~200 |
| S-tree SIMD `find` (single) | ~115 |
| + batching (128) | ~45 |
| + prefetching | ~30 |
| + interleave / left-max | ~22–27 |
| 6 threads | ~7 |

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:

| dataset | binsearch | serial | batch16 | best batch | speedup |
|---|---|---|---|---|---|
| 8 MB (in-cache) | 123 | 122 | 41 | 40 | 3.0× |
| 128 MB | 646 | 300 | 65 | 65 | 10.0× |
| 1 GB (RAM) | 1067 | 507 | 96 | 96 | 11.2× |

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

| dataset | binsearch | serial | batch16 | best batch | speedup |
|---|---|---|---|---|---|
| 8 MB (in-cache) | 111 | 56 | 23 | **19** | 5.8× |
| 128 MB | 646 | 181 | 45 | 44 | 14.8× |
| 1 GB (RAM) | 1057 | 315 | 72 | **66** | **16.0×** |

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:

| dataset | default | native |
|---|---|---|
| 8 MB | 40 → 47 | 15 → 20 |
| 128 MB | 68 → 82 | 45 → 52 |
| 1 GB | 104 → 120 | 74 → 76 |

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

```bash
# 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
```