bench_multiseed.nx source
↩ module page · 149 lines · 4003 B
1// bench_multiseed.nx -- 20-workload accuracy averaging for OUR HLL + CPC.
2//
3// Today's single-sample verdict (HLL: LOSES) was an artifact of variance,
4// not algorithm. Both ours and DS got estimates within their declared
5// rel-stddev bound; DS happened to land closer to truth on seed 42.
6//
7// This harness varies the WORKLOAD across 20 distinct streams (each of N
8// unique keys), runs both primitives on every stream, and reports mean
9// error. Combined with the same workloads run through DS Python (see
10// bench_vs_ds_multiseed.py), we get a statistically fair accuracy verdict.
11
12import "syscalls.nx"
13import "sketch_hll.nx"
14import "sketch_cpc_dense.nx"
15
16func ms_iabs(x: i64) -> i64 {
17 if x < 0 { return -x }
18 return x
19}
20
21// === decimal emitter (i64 -> stdout) ============================
22
23func ms_putc(c: i64) -> i64 {
24 let buf: *u8 = sys_mmap(1)
25 buf[0] = c & 0xFF
26 sys_write(1, buf, 1)
27 return 0
28}
29
30func ms_str(s: *u8, len: i64) -> i64 {
31 sys_write(1, s, len)
32 return 0
33}
34
35func ms_i64(n: i64) -> i64 {
36 if n < 0 {
37 ms_putc(45)
38 return ms_i64(-n)
39 }
40 if n == 0 {
41 ms_putc(48)
42 return 0
43 }
44 let digits: *u8 = sys_mmap(32)
45 var d: i64 = 0
46 var v: i64 = n
47 while v > 0 {
48 digits[d] = (v % 10) + 48
49 v = v / 10
50 d = d + 1
51 }
52 while d > 0 {
53 d = d - 1
54 ms_putc(digits[d])
55 }
56 return 0
57}
58
59func ms_nl() -> i64 {
60 ms_putc(10)
61 return 0
62}
63
64// === main =======================================================
65//
66// Vary workload across 20 seeds. Each seed produces a different stream
67// of N distinct 8-byte keys. Both HLL and CPC run on every stream.
68
69func main() -> i64 {
70 let n: i64 = 2000
71 let n_seeds: i64 = 20
72
73 var hll_sum_err: i64 = 0
74 var cpc_sum_err: i64 = 0
75 var hll_max_err: i64 = 0
76 var cpc_max_err: i64 = 0
77
78 let buf: *u8 = sys_mmap(8)
79
80 var s: i64 = 0
81 while s < n_seeds {
82 let workload_seed: i64 = s + 1
83 // Fresh sketches per workload run.
84 let hll: *Hll = nx_hll_alloc(7, 42)
85 let cpc: *CpcDense = nx_cpcd_alloc(3, 16, 42)
86
87 // Generate the workload deterministically from workload_seed.
88 var i: i64 = 0
89 while i < n {
90 let k: i64 = workload_seed * 100000 + i
91 buf[0] = (k ) & 0xFF
92 buf[1] = (k >> 8 ) & 0xFF
93 buf[2] = (k >> 16) & 0xFF
94 buf[3] = (k >> 24) & 0xFF
95 buf[4] = 0
96 buf[5] = 0
97 buf[6] = 0
98 buf[7] = 0
99 nx_hll_add(hll, buf, 8)
100 nx_cpcd_add(cpc, buf, 8)
101 i = i + 1
102 }
103
104 let hll_est: i64 = nx_hll_estimate(hll)
105 let cpc_est: i64 = nx_cpcd_estimate(cpc)
106 let hll_err: i64 = ms_iabs(hll_est - n)
107 let cpc_err: i64 = ms_iabs(cpc_est - n)
108
109 hll_sum_err = hll_sum_err + hll_err
110 cpc_sum_err = cpc_sum_err + cpc_err
111 if hll_err > hll_max_err { hll_max_err = hll_err }
112 if cpc_err > cpc_max_err { cpc_max_err = cpc_err }
113
114 // Emit per-seed line so the harness can cross-reference DS output.
115 ms_str("seed=", 5)
116 ms_i64(workload_seed)
117 ms_str(" hll_est=", 9)
118 ms_i64(hll_est)
119 ms_str(" cpc_est=", 9)
120 ms_i64(cpc_est)
121 ms_nl()
122
123 s = s + 1
124 }
125
126 let hll_mean_err: i64 = hll_sum_err / n_seeds
127 let cpc_mean_err: i64 = cpc_sum_err / n_seeds
128
129 ms_str("our_hll_mean_err=", 17)
130 ms_i64(hll_mean_err)
131 ms_nl()
132 ms_str("our_hll_max_err=", 16)
133 ms_i64(hll_max_err)
134 ms_nl()
135 ms_str("our_cpc_mean_err=", 17)
136 ms_i64(cpc_mean_err)
137 ms_nl()
138 ms_str("our_cpc_max_err=", 16)
139 ms_i64(cpc_max_err)
140 ms_nl()
141 ms_str("workload_n=", 11)
142 ms_i64(n)
143 ms_nl()
144 ms_str("n_seeds=", 8)
145 ms_i64(n_seeds)
146 ms_nl()
147
148 return 0
149}