sketch_hll4_vs_hll8_bench.nx
buildroot/runtime/sketch_hll4_vs_hll8_bench.nx
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
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
structs
| none |
consts
| none |
functions
| 30 | func iabs_h4(x: i64) -> i64 called by 1: main |
| 35 | func write_bh4(buf: *u8, value: i64) -> i64 called by 1: main |
| 46 | func main() -> i64 |