nordisk/znippy-zoomies

ragnar-report — stree optimisation toward the 40× ratio

RECONSTRUCTED 2026-08-10 evening after a box reboot wiped the tmpfs scratchpad. Raw logs (baseline/h3/lab/final *-3runs.log, thp_probe) are gone; every number below was recorded in this report or the git commits before the reboot and is quoted from those. Machine t14s, 16 cores, avx2/avx512{f,bw,vl,dq}. Committed artifacts survive: znippy-zoomies a568fa8 → ed9f44f → f4f7080 → 0.1.23 (published), znippy ba77d83, skade-katalog 0.1.17 (published).

FINAL RESULT: 40× reached and passed. Final arms (3 consistent runs): stree32_512mb 56.6–59.3× (18.7 ns), stree_1gb 50.9–55.1× (24.2 ns), stree32_64mb ~40×, stree_128mb ~35×, git_oid_8m 4.6–5.4×. Conservative cross-check with the morning's quiet binsearch denominators (that final sweep's denominators ran ~25% load-inflated): stree32_512mb ≈ 50×, stree_1gb ≈ 42× — past 40 either way. What made it reachable was never one trick: three silent defects (misaligned nodes, EINVAL'd madvise, sandbox THP-disable) sat stacked under the correct algorithm.

0. Provenance of the 40×

• Article: "Static search trees: 40x faster than binary search" — Ragnar Groot Koerkamp, Dec 2024, https://curiouscoding.nl/posts/static-search-tree/
• Code: https://github.com/RagnarGrootKoerkamp/static-search-tree (MIT)
• The 40× is u32/B=16/batch-128 with prefetch+interleave+hugepages at the 4 GB point (binsearch ~1150 ns → ~27 ns). The ratio is size-dependent; expecting 40× at 8e6 keys over-reads the article.

1. H1 — entry points (settled by reading)

• Bench stree_*/stree32_*: batch_stream::<16/32/128> — real MLP path.
• Bench + production oid path: GitOidIndex::lookup_batch → STree64Mmap::lookup_batch_pipeline::<8> — P=8 (BATCH_P, oid_index.rs:312). The "8 matched the sweet spot" comment conflated the call batch size sweep (1/100/1000/10000 → 100) with the const-generic in-flight P, which was never swept.
• lookup_batch_pipeline is two-phase (route → sort_unstable → serial leaf scan + verify): built for the cold 144 GB OSM mmap, pure overhead on an in-RAM section, and the leaf misses sit outside the pipeline.
• lookup_batch_ptr / lookup_batch_interleave: called by nobody.
• Production delivers oids in bulk: emit_set passes the whole store's oids in ONE lookup_batch call; bench passes 50k–200k. "40+ ids per call" holds.

2. Baseline (morning, quiet box, best of 3)

Headline: raw tree already 16–25×; the oid path's 2.8× deficit lived in the wrapper (P=8 + sort + unpipelined leaf/verify), not in fanout.

Anomalies explained: (1e5 serial≥batch) wrapper tax ≈ pipeline win in L3; (1e6 serial≈binsearch) binsearch's top ~13 probe levels are cache-resident, equal miss counts. Both reproduce in Ragnar's own serial-vs-batch plots.

3. Hypothesis verdicts (all measured except H5)

Also measured NULL and reverted, with mechanism: verify-side software prefetch (110.0 → 108.5 on git_oid_8m — the verify loop's independent iterations were already overlapped by the OoO window). fused2 (two-chunk softpipe): null, chunk barrier already covered by leaf prefetches.

4. What shipped

znippy-zoomies a568fa8: STree64Mmap::lookup_batch_fused::<P> (single-phase: route with next-level prefetch → leaf-line prefetch → immediate scan; no routed Vec, no sort, no scatter); NodeBuf (64-B-aligned nodes, new_with_stride_phase for A/B); stree512.rs (H2 refutation); examples/stree_lab.rs (LAB_N/LAB_Q/LAB_REPS/LAB_SEED).

znippy ba77d83: BATCH_P 8→64 + pipeline→fused in oid_index.rs. Measured: git_oid_8m batch 184.6 → 110.0 ns, 2.81× → 4.57× (lab predicted 105–110/~4.7). store.rs batch-of-one guard loosened to tolerate the now-tie (was built on the sort phase's 1.02× penalty; 604 vs 620 ns, winner flips run-to-run).

znippy-zoomies ed9f44f: NodeBuf for in-RAM STree64 + NodeBuf32 for STree32/STree32Mmap — at 134M keys ram_stream_p128 61.5 → 24.4 ns (~36× then; the whole in-RAM 2× gap was allocation phase). Hugepage saga (below). fused2 verdict recorded.

znippy-zoomies f4f7080 — Hi32 tree: STreeHi32Mmap routes on a monotone 32-bit truncation (hi(q)=(q^sign)>>32): internal node = 16×u32 = 64 B one line, fanout 17, i64 leaf column. Predecessor-safe (undercount ⇒ never overshoot; leaf scans forward while id<q; test forces equal-hi32 runs). Same-run pairs: 8M fused_p64 31.7 → hi32 23.2 (−27%); 134M 46.1→38.3 and 37.3→28.8 (−17…−23%). The "third variant" answered YES — via truncation, not AVX-512.

Published: znippy-zoomies 0.1.23; skade-katalog 0.1.17 (dep floor 0.1.23; its static_index/batch_stream gets aligned nodes with zero code change; 53 tests green).

5. The hugepage lever was dead behind THREE independent bugs

AnonHugePages: 0 kB under 4.9 GB of madvised trees. Each bug alone fatal:

1. madvise needs page-aligned addresses; glibc large allocs are mmap base+0x10 → every call since the first commit failed EINVAL, silently. Fix: advise_hugepage_raw rounds inward to page boundaries.
2. Hint after first touch: vec![] faults all 4 K pages, then the hint waits on khugepaged (never on bench timescales). Fix: NodeBuf* do with_capacity → advise → fill.
3. PR_SET_THP_DISABLE inherited from the agent sandbox (THP_enabled: 0 vs PID 1's 1) — makes 1+2 moot under any agent shell, meaning ALL agent-driven bench history on this box ran THP-less. Fix: stree::thp_enable_for_process() — called by binaries only (nornir-bench main does; library never flips process state).

After all three: AnonHugePages 4 743 168 kB of 4 877 GB Rss, smaps-verified. THP's isolated timing share on the batched walk looks ≈ nil (MLP already hides TLB walks; the fused numbers didn't move); its effect on the latency-bound serial/binsearch arms is an open measurement — every post-fix sweep was polluted by co-load (RustRover + other sessions).

6. Final arms (all fixes; 3 consistent runs; denominators ~25% load-inflated)

7. Open items / where the next session starts

• Arrow-path analysis (oid→ordinal vs Arrow payload split, redb txn-per-batch, extents split, three-layout A/B): a subagent was mid-measurement when the box rebooted; its journal died with /tmp. Needs re-running — the decisive number is the re-measured 72–91% split, which gates section-v4 (interleave oid+row+ord to collapse verify's 3 cold lines to 1) vs payload-fetch pipelining vs nothing. NB the verify-prefetch NULL above: independent .map() loads are already OoO-overlapped; do not build a pipelined payload fetch without measuring the split first.
• THP timing delta on serial arms: needs a genuinely quiet box.
• Hi32 quiet-box absolutes (expected ~17–19 ns → ~50× for i64).
• Wiring Hi32 into the oid path buys only ~4 ns (verify-dominated); not done.
• Pre-existing reds, not from this work: znippy resolve:: ×3 (thin-pack base resolution, red at pristine HEAD), zoomies vann::search_batch ×1.
• gunnar itself: untouched; end-to-end (clone/fetch/pack-serve) impact of the 1.6–5× lookup wins unmeasured.