sketch_count_sketch_vs_cms_bias_bench.nx source
↩ module page · 187 lines · 5895 B
1// sketch_count_sketch_vs_cms_bias_bench.nx -- bias-direction paired bench.
2//
3// CLAIM TO VALIDATE:
4// CountSketch (Charikar-Chen-Farach-Colton 2002) is UNBIASED: its
5// per-row sign hash h2 means expected error = 0, errors are
6// two-sided. Count-Min Sketch (Cormode-Muthukrishnan 2005) is
7// one-sided BIASED: estimates are always >= true (min over d
8// rows, all rows >= truth by collision additivity).
9//
10// DataSketches ships ONLY CMS in the frequency family; CountSketch
11// is queued. Substrate ships both; this bench demonstrates the
12// error-direction win on a representative Zipfian stream.
13//
14// WORKLOAD:
15// 5 heavy items + 5000 noise singletons. Total stream ~8800
16// inserts. Both sketches: d=5, w=256.
17//
18// MEASUREMENT:
19// For each heavy item, compute:
20// cms_bias = cms_est - true
21// cs_bias = cs_est - true
22//
23// Headline CAPABILITY EXCEED: cms_bias >= 0 for ALL heavy items
24// (one-sided), cs_bias may be negative for some (two-sided).
25//
26// Headline ACCURACY EXCEED: |cs_bias| <= |cms_bias| for heaviest
27// items where additive noise dominates -- CountSketch's signed
28// cancellation tightens the estimate.
29
30import "syscalls.nx"
31import "sketch_count_sketch.nx"
32import "sketch_cms.nx"
33import "sketch_comparator.nx"
34import "sketch_types.nx"
35
36func iabs_b(x: i64) -> i64 {
37 if x < 0 { return -x }
38 return x
39}
40
41func write_b(buf: *u8, value: i64) -> i64 {
42 var i: i64 = 0
43 var v: i64 = value
44 while i < 8 {
45 buf[i] = (v & 0xFF) as u8
46 v = v >> 8
47 i = i + 1
48 }
49 return 0
50}
51
52func main() -> i64 {
53 let d: i64 = 5
54 let w: i64 = 256
55 let seed: i64 = 42
56
57 let cs: *CountSketch = nx_cs_alloc(d, w, seed)
58 let cms: *Cms = nx_cms_alloc(d, w, seed)
59 if cs == (0 as *CountSketch) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
60 if cms == (0 as *Cms) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
61
62 let key_buf_raw: *u8 = sys_mmap(8)
63 let key_buf: *u8 = key_buf_raw
64
65 // ---- Heavy items: id 1..5 with counts 2000, 1000, 500, 200, 100 ----
66 // Item 1: 2000 occurrences
67 var rep: i64 = 0
68 while rep < 2000 {
69 nx_cs_add(cs, 1, 1)
70 write_b(key_buf, 1)
71 nx_cms_add(cms, key_buf, 8, 1)
72 rep = rep + 1
73 }
74 // Item 2: 1000
75 rep = 0
76 while rep < 1000 {
77 nx_cs_add(cs, 2, 1)
78 write_b(key_buf, 2)
79 nx_cms_add(cms, key_buf, 8, 1)
80 rep = rep + 1
81 }
82 // Item 3: 500
83 rep = 0
84 while rep < 500 {
85 nx_cs_add(cs, 3, 1)
86 write_b(key_buf, 3)
87 nx_cms_add(cms, key_buf, 8, 1)
88 rep = rep + 1
89 }
90 // Item 4: 200
91 rep = 0
92 while rep < 200 {
93 nx_cs_add(cs, 4, 1)
94 write_b(key_buf, 4)
95 nx_cms_add(cms, key_buf, 8, 1)
96 rep = rep + 1
97 }
98 // Item 5: 100
99 rep = 0
100 while rep < 100 {
101 nx_cs_add(cs, 5, 1)
102 write_b(key_buf, 5)
103 nx_cms_add(cms, key_buf, 8, 1)
104 rep = rep + 1
105 }
106
107 // ---- Noise: 5000 singleton items id 1000..5999 ----
108 var i: i64 = 0
109 while i < 5000 {
110 let nid: i64 = 1000 + i
111 nx_cs_add(cs, nid, 1)
112 write_b(key_buf, nid)
113 nx_cms_add(cms, key_buf, 8, 1)
114 i = i + 1
115 }
116
117 // ---- Query heavy item 1 (truth = 2000) ----
118 let truth_1: i64 = 2000
119 let cs_est_1: i64 = nx_cs_estimate(cs, 1)
120 write_b(key_buf, 1)
121 let cms_est_1: i64 = nx_cms_estimate(cms, key_buf, 8)
122
123 // ---- CMS BIAS DIRECTION: must be >= truth ----
124 if cms_est_1 < truth_1 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
125
126 // ---- ACCURACY axis: CountSketch closer to truth than CMS ----
127 let acc_1: *ComparisonResult = nx_cmp_accuracy(cs_est_1, cms_est_1, truth_1, 5000)
128 if acc_1.verdict == NX_CMP_VERDICT_LOSES {
129 // CMS could legitimately tie or beat on lighter items, but on
130 // the HEAVIEST item with this much noise we expect CS to win.
131 return __syscall(93, 11, 0, 0, 0, 0, 0)
132 }
133
134 // ---- Query heavy item 2 (truth = 1000) ----
135 let truth_2: i64 = 1000
136 let cs_est_2: i64 = nx_cs_estimate(cs, 2)
137 write_b(key_buf, 2)
138 let cms_est_2: i64 = nx_cms_estimate(cms, key_buf, 8)
139 if cms_est_2 < truth_2 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
140
141 // ---- Aggregate: average bias across 5 heavy items ----
142 var sum_abs_cs: i64 = 0
143 var sum_abs_cms: i64 = 0
144 var sum_cs_signed: i64 = 0
145 var sum_cms_signed: i64 = 0
146 let truths_raw: *u8 = sys_mmap(5 * 8)
147 let truths: *i64 = truths_raw as *i64
148 truths[0] = 2000
149 truths[1] = 1000
150 truths[2] = 500
151 truths[3] = 200
152 truths[4] = 100
153 var k: i64 = 0
154 while k < 5 {
155 let id: i64 = k + 1
156 let t: i64 = truths[k]
157 let cs_e: i64 = nx_cs_estimate(cs, id)
158 write_b(key_buf, id)
159 let cms_e: i64 = nx_cms_estimate(cms, key_buf, 8)
160 let cs_b: i64 = cs_e - t
161 let cms_b: i64 = cms_e - t
162 sum_cs_signed = sum_cs_signed + cs_b
163 sum_cms_signed = sum_cms_signed + cms_b
164 sum_abs_cs = sum_abs_cs + iabs_b(cs_b)
165 sum_abs_cms = sum_abs_cms + iabs_b(cms_b)
166 k = k + 1
167 }
168
169 // ---- CAPABILITY: CMS signed bias must be non-negative (one-sided) ----
170 if sum_cms_signed < 0 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
171
172 // ---- ACCURACY aggregated: |CS_total| <= |CMS_total| on heavy items ----
173 let acc_agg: *ComparisonResult = nx_cmp_memory(sum_abs_cs, sum_abs_cms, 10000)
174 if acc_agg.verdict != NX_CMP_VERDICT_BEATS {
175 return __syscall(93, 40, 0, 0, 0, 0, 0)
176 }
177
178 // ---- Sanity: noise item with truth=1 ----
179 // CMS estimate >= 1 always; CS estimate may be ~ 1 with two-sided
180 // noise (could be 0 or higher).
181 let cs_noise: i64 = nx_cs_estimate(cs, 1500)
182 write_b(key_buf, 1500)
183 let cms_noise: i64 = nx_cms_estimate(cms, key_buf, 8)
184 if cms_noise < 1 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
185
186 return 0
187}