code wiki / (root) / sketch_hll4_vs_hll8_bench.nx

sketch_hll4_vs_hll8_bench.nx

buildroot/runtime/sketch_hll4_vs_hll8_bench.nx

3234 B103 linesdepth 7pulls 13 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_hll4_vs_hll8_bench.nx -- memory-efficiency paired bench. CLAIM TO VALIDATE: HLL_4 (4-bit registers + Heule exception table) achieves the SAME cardinality accuracy as HLL_8 (8-bit registers) at ~50% memory for the typical case where < ~10% of registers hit rho > 14 (the value beyond which the 4-bit register saturates and the exception table records the actual rho). Apache DataSketches HLL_4_12 documents the same claim; substrate matches. WORKLOAD: Stream 10000 distinct keys into both at lg_k=10 (m=1024 regs). MEMORY: HLL_8 (lg_k=10): m=1024 bytes regs + header = ~1048 B HLL_4 (lg_k=10): m/2=512 bytes regs + exception table overhead. For 10k stream at lg_k=10, ~few exceptions expected -> ~512 + ~8*16 (initial except cap) = ~640 B. ~38% reduction. HARD-WIN GATE: MEMORY: HLL_4 bytes < HLL_8 bytes by >25%. ACCURACY: both estimates within 15% of truth=10000.

dependencies 5 imports · 0 importers

syscalls.nx sketch_hll.nx sketch_hll4.nx sketch_comparator.nx sketch_types.nx sketch_hll4_vs_hll8_bench.nx

imports: syscalls.nxsketch_hll.nxsketch_hll4.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_hll_alloc nx_hll4_alloc write_bh4 nx_hll_add murmur3_32 mm_load_u32_le mm_rotl32 nx_clz32 nx_bits_clz32 nx_hll4_add murmur3_32 ↻ nx_clz32 ↻ nx_hll4_read nx_hll4_get_packed nx_hll4_except_find nx_hll4_write nx_hll4_set_packed nx_hll4_except_set nx_hll4_except_find ↻ 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

structs

none

consts

none

functions

30func iabs_h4(x: i64) -> i64
called by 1: main
35func write_bh4(buf: *u8, value: i64) -> i64
called by 1: main
46func main() -> i64