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)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_kll_alloc nx_reservoir_alloc nx_kll_add nx_kll_level_addr nx_kll_compact nx_kll_sort_level nx_kll_level_addr ↻ nx_kll_level_addr ↻ nx_kll_rng_next nx_kll_compact ↻ nx_reservoir_add nx_reservoir_rng_below nx_reservoir_rng_next nx_kll_quantile nx_kll_total_weight nx_kll_level_addr ↻ nx_reservoir_quantile nx_reservoir_sort iabs_kr nx_kll_memory_bytes nx_reservoir_memory_bytes nx_cmp_memory

structs

none

consts

none

functions

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