sketch_hll_lgk12_vs_lgk8_bench.nx source
↩ module page · 112 lines · 3841 B
1// sketch_hll_lgk12_vs_lgk8_bench.nx -- validates bits-up cap raise.
2//
3// SUBSTRATE FACT TO VALIDATE:
4// NX_HLL_LGK_MAX raised from 10 to 12 this session. Adds alpha_m_sq_q64
5// entries for lg_k=11, 12 + Heule thresholds. Higher lg_k gives
6// exponentially more registers (m = 2^lg_k) and tighter rel-stddev
7// (1.04 / sqrt(m)).
8//
9// lg_k=8: m=256, rel stddev = 1.04/16 = 6.5%
10// lg_k=12: m=4096, rel stddev = 1.04/64 = 1.6% (4x tighter)
11//
12// WORKLOAD:
13// 100,000 distinct keys streamed into both sketches.
14// Truth = 100,000.
15//
16// MEASUREMENT:
17// ACCURACY axis: closer to truth wins.
18// At matched-seed input, lg_k=12 should beat lg_k=8.
19//
20// HARD-WIN GATE:
21// ACCURACY BEATS by >2x improvement.
22
23import "syscalls.nx"
24import "sketch_hll.nx"
25import "sketch_comparator.nx"
26import "sketch_types.nx"
27
28func iabs_hl(x: i64) -> i64 {
29 if x < 0 { return -x }
30 return x
31}
32
33func write_bh(buf: *u8, value: i64) -> i64 {
34 var i: i64 = 0
35 var v: i64 = value
36 while i < 8 {
37 buf[i] = (v & 0xFF) as u8
38 v = v >> 8
39 i = i + 1
40 }
41 return 0
42}
43
44func main() -> i64 {
45 let small: *Hll = nx_hll_alloc(8, 42)
46 let big: *Hll = nx_hll_alloc(12, 42)
47 if small == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
48 // CRITICAL: this is the cap-raise validation -- alloc at lg_k=12
49 // must succeed.
50 if big == (0 as *Hll) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
51
52 if small.lg_k != 8 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
53 if big.lg_k != 12 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
54 if small.m != 256 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
55 if big.m != 4096 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
56
57 let key_raw: *u8 = sys_mmap(8)
58 let key: *u8 = key_raw
59
60 let n_keys: i64 = 100000
61 var i: i64 = 1
62 while i <= n_keys {
63 write_bh(key, i + 1000000)
64 nx_hll_add(small, key, 8)
65 nx_hll_add(big, key, 8)
66 i = i + 1
67 }
68
69 let small_est: i64 = nx_hll_estimate(small)
70 let big_est: i64 = nx_hll_estimate(big)
71
72 // ---- Both must be in reasonable range ----
73 if iabs_hl(small_est - n_keys) > (n_keys * 30) / 100 {
74 return __syscall(93, 10, 0, 0, 0, 0, 0)
75 }
76 if iabs_hl(big_est - n_keys) > (n_keys * 10) / 100 {
77 return __syscall(93, 11, 0, 0, 0, 0, 0)
78 }
79
80 // ---- ACCURACY: big BEATS small ----
81 let acc: *ComparisonResult = nx_cmp_accuracy(big_est, small_est, n_keys, 10000)
82 if acc.verdict != NX_CMP_VERDICT_BEATS {
83 return __syscall(93, 20, 0, 0, 0, 0, 0)
84 }
85 // Expected improvement: lg_k=12 has 4x tighter rel-stddev than lg_k=8.
86 // On a 100k stream, lg_k=8 err ~ 6500, lg_k=12 err ~ 1600.
87 // delta_ppm = (small_err - big_err) * 1e6 / 100000 ~ (6500-1600)*10 = 49000
88 if acc.delta_ppm < 10000 { // require >=1% improvement (well below the expected ~5%)
89 return __syscall(93, 21, 0, 0, 0, 0, 0)
90 }
91
92 // ---- Sanity: declared envelopes via nx_hll_query ----
93 let q_small: *ApproxI64 = nx_hll_query(small)
94 let q_big: *ApproxI64 = nx_hll_query(big)
95 // lg_k=8 -> stddev_rel_ppb = 65_000_000 (per existing table)
96 if q_small.param_a != 65000000 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
97 // lg_k=12 -> stddev_rel_ppb = 16_250_000 (per existing table)
98 if q_big.param_a != 16250000 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
99
100 // ---- Memory cost disclosure ----
101 // lg_k=8: m=256 bytes regs + 32 header = ~288 B
102 // lg_k=12: m=4096 bytes regs + 32 header = ~4128 B
103 // 14x memory increase yields 4x accuracy improvement -- substrate
104 // honesty: not "free", but the structural option now exists.
105 let small_bytes: i64 = small.m + 32
106 let big_bytes: i64 = big.m + 32
107 if big_bytes <= small_bytes {
108 return __syscall(93, 40, 0, 0, 0, 0, 0)
109 }
110
111 return 0
112}