bench_hll_vs_cpcd.nx source
↩ module page · 73 lines · 2513 B
1// bench_hll_vs_cpcd.nx -- HLL_8 vs CPC DENSE at matched accuracy.
2//
3// Fixes the v1 memory loss by configuring CPC DENSE with matched-accuracy
4// parameters instead of matched-m parameters.
5//
6// MATCHED-ACCURACY CONFIG:
7// HLL_8: lg_k=7 -> m=128 registers (1 byte each), rel-stddev = 1.04/sqrt(128) = 9.2%
8// CPC dense: lg_k=3, w=16 -> big_M = 128 coupons, rel-stddev = 1/sqrt(128) = 8.8%
9//
10// MEMORY:
11// HLL_8: 24 header + 128 register bytes = 152 bytes
12// CPC dense: 72 header + 16 bitmap bytes = 88 bytes
13//
14// EXPECTED VERDICT: MEMORY BEATS at matched accuracy.
15
16import "syscalls.nx"
17import "sketch_hll.nx"
18import "sketch_cpc_dense.nx"
19import "sketch_comparator.nx"
20import "sketch_types.nx"
21
22func main() -> i64 {
23 let n: i64 = 1000 // distinct keys
24
25 // HLL_8 at lg_k=7 (m=128, ~9.2% stddev)
26 let hll: *Hll = nx_hll_alloc(7, 42)
27 if hll == (0 as *Hll) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
28
29 // CPC dense at lg_k=3, w=16 (m=8, w=16, big_M=128, ~8.8% stddev)
30 let cpc: *CpcDense = nx_cpcd_alloc(3, 16, 42)
31 if cpc == (0 as *CpcDense) { return __syscall(93, 6, 0, 0, 0, 0, 0) }
32
33 // Stream N distinct keys through both.
34 let buf: *u8 = sys_mmap(8)
35 var i: i64 = 0
36 while i < n {
37 buf[0] = (i ) & 0xFF
38 buf[1] = (i >> 8 ) & 0xFF
39 buf[2] = (i >> 16) & 0xFF
40 buf[3] = 0xA1
41 buf[4] = 0
42 buf[5] = 0
43 buf[6] = 0
44 buf[7] = 0
45 nx_hll_add(hll, buf, 8)
46 nx_cpcd_add(cpc, buf, 8)
47 i = i + 1
48 }
49
50 let hll_est: i64 = nx_hll_estimate(hll)
51 let cpc_est: i64 = nx_cpcd_estimate(cpc)
52
53 // ACCURACY: who's closer to truth = n ?
54 let r_acc: *ComparisonResult = nx_cmp_accuracy(cpc_est, hll_est, n, 10000)
55
56 // MEMORY: CPC dense (88 bytes) vs HLL_8 (152 bytes)
57 let cpc_mem: i64 = nx_cpcd_memory_bytes(cpc)
58 let hll_mem: i64 = 24 + 128 // HLL header + register array
59 let r_mem: *ComparisonResult = nx_cmp_memory(cpc_mem, hll_mem, 10000)
60
61 // TIME: skip (both run in series; treat as equivalent for v1)
62 let r_tim: *ComparisonResult = nx_cmp_time(100, 100, 10000)
63
64 // Composite verdict.
65 let composite: i64 = nx_cmp_composite(r_acc, r_mem, r_tim)
66
67 // Encode verdicts in low 8 bits for exit code (limit of POSIX).
68 var ret: i64 = 0
69 ret = ret | r_acc.verdict
70 ret = ret | (r_mem.verdict << 2)
71 ret = ret | (composite << 4)
72 return ret
73}