sketch_kll_vs_reservoir_bench.nx
buildroot/runtime/sketch_kll_vs_reservoir_bench.nx
about
sketch_kll_vs_reservoir_bench.nx -- MATCHED-MEMORY honest measurement.
HONESTY UP FRONT:
sketch_kll.nx header asserts "KLL has tighter rank-error at fixed
memory" -- but at MATCHED slot count this is FALSE per declared
envelopes:
KLL k=64 (16 levels × 64 = 1024 slots): declared eps = 0.12
Reservoir cap=1024 (flat): declared eps = 0.0425
Reservoir wins on rank-error magnitude at matched memory by ~3x.
KLL's actual structural advantage is elsewhere:
- DETERMINISTIC mergeable (Reservoir is harder to merge)
- Streaming O(1) amortized update vs Reservoir's O(1/n) prob
- Eviction-free at large N (Reservoir's sample stops growing)
This bench MEASURES the empirical rank error of both at matched
memory, and asserts what the substrate actually does, not what the
docstring claims. If KLL beats Reservoir empirically, KLL's claim
stands. If Reservoir wins, the header gets a correction (queued).
WORKLOAD:
Stream 1..10000, deterministic.
Memory: ~8KB for both (KLL k=64, Reservoir cap=1024).
MEASUREMENT:
Errors at p10/p50/p90 vs truth (1000/5000/9000).
Compare via sketch_comparator accuracy axis.
dependencies 5 imports · 0 importers
imports: syscalls.nxsketch_kll.nxsketch_reservoir.nxsketch_comparator.nxsketch_types.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| none |
functions
| 35 | func iabs_kr(x: i64) -> i64 called by 1: main |
| 40 | func main() -> i64 |