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)

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

main nx_lc_alloc nx_lc_is_pow2 nx_hll_alloc write_blc nx_lc_add murmur3_32 mm_load_u32_le mm_rotl32 nx_lc_set_bit nx_hll_add murmur3_32 ↻ nx_clz32 nx_bits_clz32 nx_lc_estimate nx_lc_zeros nx_lc_popcount_byte nx_lc_neg_ln_ppm nx_hll_estimate nx_hll_pow2_neg_q32 nx_hll_alpha_m_sq_q64 nx_hll_bias_table_n nx_hll_bias_table_get nx_hll_bias_lgk4 nx_hll_bias_lgk5 nx_hll_bias_lgk6 nx_hll_bias_lgk7 nx_hll_bias_lgk8 nx_hll_bias_lgk9 nx_hll_bias_lgk10 nx_hll_log2_ppm nx_hll_bias_correct nx_hll_bias_table_n ↻ nx_hll_bias_table_get ↻ nx_mulshl_div_i64 nx_i128_alloc nx_i128_mul_i64 nx_i128_mul_u64 nx_i128_neg nx_i128_shl

structs

none

consts

none

functions

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