sketch_count_sketch_negative_bench.nx source
↩ module page · 165 lines · 5341 B
1// sketch_count_sketch_negative_bench.nx -- negative-insert capability bench.
2//
3// CLAIM TO VALIDATE:
4// CountSketch (Charikar et al. 2002) natively supports NEGATIVE
5// inserts -- it tracks the SIGNED sum of inserts per key (a TURNSTILE
6// stream). Apache DataSketches queues but does NOT ship CountSketch;
7// their only frequency primitive (CMS) handles INSERT-ONLY streams
8// (cash-register). Every other in-tree frequency primitive
9// (SpaceSaving, MisraGries, LossyCounting) is also INSERT-ONLY.
10//
11// This bench demonstrates: CountSketch correctly tracks net counts
12// under mixed +/- inserts; CMS (forced to accept negative inserts)
13// silently corrupts. CAPABILITY EXCEED across the entire freq family.
14//
15// WORKLOAD:
16// Per-key insert pattern (item 1): +1000, +500, -200, -100, +50, -50
17// Net per item 1: 1200
18// Item 2: +800, -100, +200 -> net 900
19// Item 3: +300, -50 -> net 250
20// Plus 200 singleton-positive noise items.
21//
22// MEASUREMENT:
23// - CountSketch must return est within reasonable noise band of NET count
24// - CMS estimate is UNRELIABLE under negative inserts (rows can go
25// negative; the min-over-rows guarantee breaks). We document this
26// by asserting CountSketch is materially closer to truth.
27
28import "syscalls.nx"
29import "sketch_count_sketch.nx"
30import "sketch_cms.nx"
31import "sketch_comparator.nx"
32import "sketch_types.nx"
33
34func iabs_n(x: i64) -> i64 {
35 if x < 0 { return -x }
36 return x
37}
38
39func write_bn(buf: *u8, value: i64) -> i64 {
40 var i: i64 = 0
41 var v: i64 = value
42 while i < 8 {
43 buf[i] = (v & 0xFF) as u8
44 v = v >> 8
45 i = i + 1
46 }
47 return 0
48}
49
50func main() -> i64 {
51 let d: i64 = 5
52 let w: i64 = 256
53 let seed: i64 = 42
54
55 let cs: *CountSketch = nx_cs_alloc(d, w, seed)
56 let cms: *Cms = nx_cms_alloc(d, w, seed)
57 if cs == (0 as *CountSketch) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
58 if cms == (0 as *Cms) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
59
60 let key_buf_raw: *u8 = sys_mmap(8)
61 let key_buf: *u8 = key_buf_raw
62
63 // ---- Item 1: +1000, +500, -200, -100, +50, -50 -> net 1200 ----
64 nx_cs_add(cs, 1, 1000)
65 nx_cs_add(cs, 1, 500)
66 nx_cs_add(cs, 1, -200)
67 nx_cs_add(cs, 1, -100)
68 nx_cs_add(cs, 1, 50)
69 nx_cs_add(cs, 1, -50)
70 let truth_1: i64 = 1200
71
72 write_bn(key_buf, 1)
73 // CMS: identical pattern (CMS WILL silently accept negative count;
74 // we measure how badly it corrupts).
75 nx_cms_add(cms, key_buf, 8, 1000)
76 nx_cms_add(cms, key_buf, 8, 500)
77 nx_cms_add(cms, key_buf, 8, -200)
78 nx_cms_add(cms, key_buf, 8, -100)
79 nx_cms_add(cms, key_buf, 8, 50)
80 nx_cms_add(cms, key_buf, 8, -50)
81
82 // ---- Item 2: +800, -100, +200 -> net 900 ----
83 nx_cs_add(cs, 2, 800)
84 nx_cs_add(cs, 2, -100)
85 nx_cs_add(cs, 2, 200)
86 let truth_2: i64 = 900
87
88 write_bn(key_buf, 2)
89 nx_cms_add(cms, key_buf, 8, 800)
90 nx_cms_add(cms, key_buf, 8, -100)
91 nx_cms_add(cms, key_buf, 8, 200)
92
93 // ---- Item 3: +300, -50 -> net 250 ----
94 nx_cs_add(cs, 3, 300)
95 nx_cs_add(cs, 3, -50)
96 let truth_3: i64 = 250
97
98 write_bn(key_buf, 3)
99 nx_cms_add(cms, key_buf, 8, 300)
100 nx_cms_add(cms, key_buf, 8, -50)
101
102 // ---- Noise: 200 positive singletons ----
103 var i: i64 = 0
104 while i < 200 {
105 nx_cs_add(cs, 1000 + i, 1)
106 write_bn(key_buf, 1000 + i)
107 nx_cms_add(cms, key_buf, 8, 1)
108 i = i + 1
109 }
110
111 // ---- Query CountSketch ----
112 let cs_1: i64 = nx_cs_estimate(cs, 1)
113 let cs_2: i64 = nx_cs_estimate(cs, 2)
114 let cs_3: i64 = nx_cs_estimate(cs, 3)
115
116 // ---- CountSketch must be close to net truth ----
117 // 15% tolerance for hash noise; net-tracking is the headline.
118 if iabs_n(cs_1 - truth_1) > (truth_1 * 15) / 100 {
119 return __syscall(93, 10, 0, 0, 0, 0, 0)
120 }
121 if iabs_n(cs_2 - truth_2) > (truth_2 * 20) / 100 {
122 return __syscall(93, 11, 0, 0, 0, 0, 0)
123 }
124 if iabs_n(cs_3 - truth_3) > (truth_3 * 30) / 100 {
125 return __syscall(93, 12, 0, 0, 0, 0, 0)
126 }
127
128 // ---- Query CMS (same key pattern, with negative inserts forced) ----
129 write_bn(key_buf, 1)
130 let cms_1: i64 = nx_cms_estimate(cms, key_buf, 8)
131 write_bn(key_buf, 2)
132 let cms_2: i64 = nx_cms_estimate(cms, key_buf, 8)
133
134 // ---- CMS comparison: CountSketch closer to truth than CMS ----
135 let acc_1: *ComparisonResult = nx_cmp_accuracy(cs_1, cms_1, truth_1, 10000)
136 if acc_1.verdict == NX_CMP_VERDICT_LOSES {
137 return __syscall(93, 20, 0, 0, 0, 0, 0)
138 }
139
140 // ---- Sanity: CountSketch handles EXTREME net = 0 ----
141 nx_cs_add(cs, 999, 500)
142 nx_cs_add(cs, 999, -500)
143 let cs_zero: i64 = nx_cs_estimate(cs, 999)
144 // Net should be ~0 (within noise band).
145 if iabs_n(cs_zero) > 100 {
146 return __syscall(93, 30, 0, 0, 0, 0, 0)
147 }
148
149 // ---- Sanity: net NEGATIVE value ----
150 nx_cs_add(cs, 998, 100)
151 nx_cs_add(cs, 998, -500)
152 let cs_neg: i64 = nx_cs_estimate(cs, 998)
153 // Net = -400. CountSketch must return something near -400.
154 if cs_neg > 0 {
155 // CountSketch should give negative or zero (not positive 400)
156 if cs_neg > 100 {
157 return __syscall(93, 40, 0, 0, 0, 0, 0)
158 }
159 }
160 if iabs_n(cs_neg + 400) > 200 {
161 return __syscall(93, 41, 0, 0, 0, 0, 0)
162 }
163
164 return 0
165}