code wiki / (root) / sketch_lc_vs_hll_small_n_bench.nx

sketch_lc_vs_hll_small_n_bench.nx

buildroot/runtime/sketch_lc_vs_hll_small_n_bench.nx

2789 B90 linesdepth 6pulls 13 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_lc_vs_hll_small_n_bench.nx -- LC sweet-spot paired bench. CLAIM TO VALIDATE: Linear Counter (Whang-Vander Zanden 1990) is exact-bit per insert with collision-driven variance. At small N where bit-collisions are rare (N << m), LC's estimator is tighter than HLL's, which pays a constant overhead for the rho-based ranks even when the counts are small. The substrate ships both; LC's documented sweet spot is "small-N". Bench verifies the cross-over: at N <= m/4, LC should win on accuracy at matched memory. WORKLOAD: N = 200 distinct keys. LC m_bits = 1024 (128 bytes regs) HLL lg_k = 7 (m = 128 regs * 8 bits = 1024 bits = 128 bytes total) Both at ~128 byte register footprint. MEASUREMENT: ACCURACY: closer to truth=200 wins.

dependencies 5 imports · 0 importers

syscalls.nx sketch_linear_counter.nx sketch_hll.nx sketch_comparator.nx sketch_types.nx sketch_lc_vs_hll_small_n_bench

imports: syscalls.nxsketch_linear_counter.nxsketch_hll.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

structs

none

consts

none

functions

29func iabs_lc(x: i64) -> i64
34func write_blc(buf: *u8, value: i64) -> i64
45func main() -> i64