sketch_hll4_vs_hll8_bench.nx source
↩ module page · 103 lines · 3234 B
1// sketch_hll4_vs_hll8_bench.nx -- memory-efficiency paired bench.
2//
3// CLAIM TO VALIDATE:
4// HLL_4 (4-bit registers + Heule exception table) achieves the SAME
5// cardinality accuracy as HLL_8 (8-bit registers) at ~50% memory
6// for the typical case where < ~10% of registers hit rho > 14
7// (the value beyond which the 4-bit register saturates and the
8// exception table records the actual rho). Apache DataSketches
9// HLL_4_12 documents the same claim; substrate matches.
10//
11// WORKLOAD:
12// Stream 10000 distinct keys into both at lg_k=10 (m=1024 regs).
13//
14// MEMORY:
15// HLL_8 (lg_k=10): m=1024 bytes regs + header = ~1048 B
16// HLL_4 (lg_k=10): m/2=512 bytes regs + exception table overhead.
17// For 10k stream at lg_k=10, ~few exceptions expected ->
18// ~512 + ~8*16 (initial except cap) = ~640 B. ~38% reduction.
19//
20// HARD-WIN GATE:
21// MEMORY: HLL_4 bytes < HLL_8 bytes by >25%.
22// ACCURACY: both estimates within 15% of truth=10000.
23
24import "syscalls.nx"
25import "sketch_hll.nx"
26import "sketch_hll4.nx"
27import "sketch_comparator.nx"
28import "sketch_types.nx"
29
30func iabs_h4(x: i64) -> i64 {
31 if x < 0 { return -x }
32 return x
33}
34
35func write_bh4(buf: *u8, value: i64) -> i64 {
36 var i: i64 = 0
37 var v: i64 = value
38 while i < 8 {
39 buf[i] = (v & 0xFF) as u8
40 v = v >> 8
41 i = i + 1
42 }
43 return 0
44}
45
46func main() -> i64 {
47 let lg_k: i64 = 10
48 let n: i64 = 10000
49 let seed: i64 = 42
50
51 let h8: *Hll = nx_hll_alloc(lg_k, seed)
52 let h4: *Hll4 = nx_hll4_alloc(lg_k, seed)
53 if h8 == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
54 if h4 == (0 as *Hll4) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
55
56 let key_raw: *u8 = sys_mmap(8)
57 let key: *u8 = key_raw
58
59 var i: i64 = 0
60 while i < n {
61 write_bh4(key, i + 5000000)
62 nx_hll_add(h8, key, 8)
63 nx_hll4_add(h4, key, 8)
64 i = i + 1
65 }
66
67 let h8_est: i64 = nx_hll_estimate(h8)
68 let h4_est: i64 = nx_hll4_estimate(h4)
69
70 // ---- ACCURACY: both within HLL 3-sigma band ----
71 if iabs_h4(h8_est - n) > (n * 15) / 100 {
72 return __syscall(93, 10, 0, 0, 0, 0, 0)
73 }
74 if iabs_h4(h4_est - n) > (n * 15) / 100 {
75 return __syscall(93, 11, 0, 0, 0, 0, 0)
76 }
77
78 // ---- MEMORY axis (no nx_hll_memory_bytes; compute inline) ----
79 let h8_bytes: i64 = h8.m + 32 // m bytes regs + 32 header
80 let h4_bytes: i64 = nx_hll4_memory_bytes(h4)
81 let mem: *ComparisonResult = nx_cmp_memory(h4_bytes, h8_bytes, 10000)
82
83 if mem.verdict != NX_CMP_VERDICT_BEATS {
84 return __syscall(93, 20, 0, 0, 0, 0, 0)
85 }
86 if mem.delta_ppm < 250000 { // require >25% memory reduction
87 return __syscall(93, 21, 0, 0, 0, 0, 0)
88 }
89
90 // ---- Both estimates should be CLOSE to each other (same family) ----
91 let diff: i64 = iabs_h4(h8_est - h4_est)
92 if diff > (n * 10) / 100 { // within 10% of each other
93 return __syscall(93, 30, 0, 0, 0, 0, 0)
94 }
95
96 // ---- Sanity: HLL_4 exception count is bounded (most regs < rho=15) ----
97 let exc: i64 = nx_hll4_exception_count(h4)
98 if exc > n / 10 { // not >10% of N
99 return __syscall(93, 40, 0, 0, 0, 0, 0)
100 }
101
102 return 0
103}