svar2 range probe: fuse the search loop into a Rust kernel

[d-laub]

The sparse range probe (#357) is overwhelmingly numpy-pass-bound: the branchless partition_point loop runs _depth iterations over the whole query block, each one a handful of full-array passes, and the cell_vk gather is the minority of the time.

Measured by splitting the lookup at N = 1e8: the cell_vk gather moves 2.4 GB across 16,384 scattered points in 0.26–0.28 ms and is only 13–16% of full lookup; the cell_id gather is 0.03 ms; full lookup is 1.68–2.03 ms. So the search loop is the other 84–87%, and it is overhead-bound, not memory-bound — it runs over a 16,384-element block that is L2-resident. (Multi-GB memory access was the stable part of that measurement, at a 1.02–1.09× min/max spread; all the variance sat in the search loop.)

A single-pass kernel over (region_ptr, cell_id) would do the whole search per query in registers instead of in _depth full-array numpy passes. Estimated headroom on the probe itself is 3–5×.

Deliberately NOT done in #357, on measurement rather than principle. The gate in tests/benchmarks/profiling/bench_svar2_range_lookup.py binds the probe at ≤ 2% of batch wall and it passes with margin:

• Worst row in the sweep (N=1e8, n_q=8192, globally shuffled), canonical median of five runs: 1.48 ms = 0.86% of the 171 ms single-threaded spliced batch, and 1.68% of the same batch on 8 threads (88 ms).
• Realized chr22 operating point (N=1e7, matching chr22's 18.0e6 entries): ~0.5% of the 171 ms batch — confirming the design spec's own "~0.5% of batch wall" claim — and ~0.95% at 8 threads.

So 3–5× on the probe buys roughly 0.35–0.4% of single-threaded batch wall today. The probe's share rises with thread count, because it is serial Python/numpy while the batch around it scales, which is why the 8-thread figure is carried here alongside the single-threaded one.

It becomes worth doing if the benchmark gate ever fails, if the read path gets fast enough elsewhere that 0.5% matters, or if thread counts climb far enough that the serial share dominates. The script prints a break-even batch wall (worst_ms / GATE) for exactly this purpose: 73.9 ms at the canonical figures — below that batch wall, the probe exceeds 2% and this issue is live.

Shape, if taken: a #[pyfunction] in src/ffi/mod.rs over a kernel in a domain module, registered in src/lib.rs's #[pymodule]. Note there is no dual-backend parity harness any more (_dispatch.py and docs/roadmaps/rust-migration.md were retired in 8f9d3c99), so parity needs a hand-written numpy oracle plus frozen .npz goldens under tests/parity/.

Found while implementing #357. The companion opportunity on the write path is the larger prize — see the genoray find_ranges_chunk issue.

[d-laub]

Revisited during brainstorming of the #357 follow-ups. Recommendation: leave deferred. The thread-scaling argument above — the one reason this looked like it might go live on its own — does not survive arithmetic.

The concern

This issue notes the probe's share of batch wall rises with thread count, because the probe is serial Python/numpy while the batch around it scales: 0.86% of the 171 ms single-threaded batch, 1.68% of the 88 ms 8-thread batch. Extrapolating that trend naively, a 32- or 64-core node looks like it would push the probe past the 2% gate with no code change at all, making this issue live by default on big hardware.

The arithmetic

Fit Amdahl's law to the two batch figures already recorded here (BATCH_MS = 171.0, BATCH_MS_8T = 88.0):

T(n) = S + P/n
T(1) = S + P     = 171
T(8) = S + P/8   =  88

Subtracting: P(1 − 1/8) = 83, so P = 94.86 ms and S = 76.14 ms.

The batch wall therefore asymptotes at 76.14 ms — and the break-even wall this issue names is 73.9 ms (worst_ms / GATE = 1.48 / 0.02). The asymptote sits above break-even, by about 3%.

Worst-row share (1.48 ms, N=1e8, n_q=8192, globally shuffled) against that model:

threads	batch wall	probe share
1	171.0 ms	0.86%
8	88.0 ms	1.68%
16	82.1 ms	1.80%
32	79.1 ms	1.87%
∞	76.1 ms	1.94%

So thread count alone never trips the 2% gate, no matter how wide the machine.

Caveat

This is a two-point fit to a two-parameter model, so it is exactly determined and has no residual — it cannot be validated against the data it came from. It is a strong prior, not a measurement. Two things would falsify it: a batch whose serial fraction is smaller than this fit implies (the model would then under-predict scaling and the gate could be reached), or per-thread effects the model omits entirely (memory bandwidth saturation, NUMA), which push against this issue by making the batch wall worse, not better.

The margin is genuinely thin — 76.1 ms against 73.9 ms. A third batch measurement at a real high thread count would settle it cheaply, and is worth taking opportunistically rather than as its own task.

What actually makes this live

Not thread count. The serial 76.1 ms shrinking — i.e. some other serial part of the read path getting optimized. That is exactly the moment the benchmark would be re-run anyway, so the existing gate in tests/benchmarks/profiling/bench_svar2_range_lookup.py remains the right trigger. No standing work item here.

Estimated cost if built anyway: a #[pyfunction] kernel plus a hand-written numpy oracle and frozen .npz goldens under tests/parity/ (there is no dual-backend parity harness since 8f9d3c99), to buy ~0.35% of single-threaded batch wall today.