code wiki / (root) / sketch_kll_vs_reservoir_bench.nx

sketch_kll_vs_reservoir_bench.nx

buildroot/runtime/sketch_kll_vs_reservoir_bench.nx

5652 B140 linesdepth 5pulls 7 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

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

syscalls.nx sketch_kll.nx sketch_reservoir.nx sketch_comparator.nx sketch_types.nx sketch_kll_vs_reservoir_bench.

imports: syscalls.nxsketch_kll.nxsketch_reservoir.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

structs

none

consts

none

functions

35func iabs_kr(x: i64) -> i64
40func main() -> i64