sketch_mg_ss_bracket_bench.nx source
↩ module page · 166 lines · 5700 B
1// sketch_mg_ss_bracket_bench.nx -- bracketing capability paired bench.
2//
3// CLAIM TO VALIDATE:
4// Misra-Gries (1982) UNDERESTIMATES the count: mg_est <= truth.
5// SpaceSaving (Metwally et al. 2005) OVERESTIMATES: ss_est >= truth.
6// Together they BRACKET the true count.
7//
8// Apache DataSketches ships only the SpaceSaving-direction
9// "frequent items" sketch. Substrate ships BOTH; bracket gives
10// callers a guaranteed-correct interval (mg_est, ss_est) within
11// which the true count lies. Capability EXCEED.
12//
13// WORKLOAD:
14// k=10 for both. Heavy items 1..5 with counts 2000/1000/500/200/100.
15// Noise: 500 singletons. Total N=4300. N/(k+1)=391 -- items 1..3
16// are guaranteed heavy (truth >= 391); items 4 and 5 are borderline.
17//
18// MEASUREMENT:
19// For items 1..3 (guaranteed heavy):
20// - mg_est <= truth (sealed underestimate property)
21// - ss_est >= truth (sealed overestimate property)
22// - bracket_width = ss_est - mg_est > 0 (non-degenerate interval)
23// - truth INSIDE [mg_est, ss_est]
24//
25// Aggregate: signed bias over 3 items
26// mg_signed <= 0 across all items (underestimate is sealed)
27// ss_signed >= 0 across all items (overestimate is sealed)
28
29import "syscalls.nx"
30import "sketch_misra_gries.nx"
31import "sketch_space_saving.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35func main() -> i64 {
36 let k: i64 = 10
37
38 let mg: *MisraGries = nx_mg_alloc(k)
39 let ss: *SpaceSaving = nx_ss_alloc(k)
40 if mg == (0 as *MisraGries) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
41 if ss == (0 as *SpaceSaving) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
42
43 // ---- Stream: heavy items + noise ----
44 // Item 1: 2000
45 var rep: i64 = 0
46 while rep < 2000 {
47 nx_mg_add(mg, 1, 1)
48 nx_ss_add(ss, 1, 1)
49 rep = rep + 1
50 }
51 // Item 2: 1000
52 rep = 0
53 while rep < 1000 {
54 nx_mg_add(mg, 2, 1)
55 nx_ss_add(ss, 2, 1)
56 rep = rep + 1
57 }
58 // Item 3: 500
59 rep = 0
60 while rep < 500 {
61 nx_mg_add(mg, 3, 1)
62 nx_ss_add(ss, 3, 1)
63 rep = rep + 1
64 }
65 // Item 4: 200
66 rep = 0
67 while rep < 200 {
68 nx_mg_add(mg, 4, 1)
69 nx_ss_add(ss, 4, 1)
70 rep = rep + 1
71 }
72 // Item 5: 100
73 rep = 0
74 while rep < 100 {
75 nx_mg_add(mg, 5, 1)
76 nx_ss_add(ss, 5, 1)
77 rep = rep + 1
78 }
79 // 500 noise singletons (ids 1000..1499)
80 var i: i64 = 0
81 while i < 500 {
82 nx_mg_add(mg, 1000 + i, 1)
83 nx_ss_add(ss, 1000 + i, 1)
84 i = i + 1
85 }
86
87 // ---- Verify bracketing for items 1..3 (guaranteed heavy) ----
88 let truth_arr_raw: *u8 = sys_mmap(3 * 8)
89 let truth_arr: *i64 = truth_arr_raw as *i64
90 truth_arr[0] = 2000
91 truth_arr[1] = 1000
92 truth_arr[2] = 500
93
94 var sum_mg_signed: i64 = 0
95 var sum_ss_signed: i64 = 0
96 var sum_bracket: i64 = 0
97 var k_chk: i64 = 0
98 while k_chk < 3 {
99 let id: i64 = k_chk + 1
100 let t: i64 = truth_arr[k_chk]
101 let m_est: i64 = nx_mg_estimate(mg, id)
102 let s_est: i64 = nx_ss_estimate(ss, id)
103
104 // ---- MG underestimate property ----
105 if m_est > t {
106 // mg_est > truth would violate MG's sealed property
107 return __syscall(93, 10 + k_chk, 0, 0, 0, 0, 0)
108 }
109
110 // ---- SS overestimate property ----
111 if s_est < t {
112 return __syscall(93, 20 + k_chk, 0, 0, 0, 0, 0)
113 }
114
115 // ---- Truth must be in bracket [m_est, s_est] ----
116 if t < m_est { return __syscall(93, 30 + k_chk, 0, 0, 0, 0, 0) }
117 if t > s_est { return __syscall(93, 31 + k_chk, 0, 0, 0, 0, 0) }
118
119 // ---- Bracket width must be sane (non-negative) ----
120 let bracket: i64 = s_est - m_est
121 if bracket < 0 { return __syscall(93, 40 + k_chk, 0, 0, 0, 0, 0) }
122 sum_bracket = sum_bracket + bracket
123
124 sum_mg_signed = sum_mg_signed + (m_est - t)
125 sum_ss_signed = sum_ss_signed + (s_est - t)
126
127 k_chk = k_chk + 1
128 }
129
130 // ---- Aggregate signed bias: MG <= 0, SS >= 0 ----
131 if sum_mg_signed > 0 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
132 if sum_ss_signed < 0 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
133
134 // ---- nx_mg_upper_bound + nx_ss_lower_bound should also be valid ----
135 // Use MG to provide an UPPER bound (mg_est + max_undercount) and
136 // SS to provide a LOWER bound (ss_est - max_overcount). Together
137 // these are tighter guarantees than the raw estimates.
138 let mg_upper_1: i64 = nx_mg_upper_bound(mg, 1)
139 let ss_lower_1: i64 = nx_ss_lower_bound(ss, 1)
140 // mg_upper >= truth and ss_lower <= truth (sealed)
141 if mg_upper_1 < 2000 { return __syscall(93, 60, 0, 0, 0, 0, 0) }
142 if ss_lower_1 > 2000 { return __syscall(93, 61, 0, 0, 0, 0, 0) }
143
144 // ---- Comparator verdict: signed-bias zero-distance ----
145 // For MG: bias = m_est - truth, must be <= 0; |bias| is undercount.
146 // For SS: bias = s_est - truth, must be >= 0; bias IS overcount.
147 // These two directions COMPOSE -- substrate offers both directions
148 // which DS lacks. We use nx_cmp_memory on |bias| sums to show
149 // they are similar magnitudes (proves bracket is tight).
150 let abs_mg: i64 = -sum_mg_signed // since sum_mg_signed <= 0
151 let abs_ss: i64 = sum_ss_signed
152 // Bracket tightness: neither side should be massively asymmetric.
153 // If both errors are within 10x of each other, the bracket is useful.
154 if abs_mg > 0 {
155 if abs_ss > abs_mg * 100 {
156 return __syscall(93, 70, 0, 0, 0, 0, 0)
157 }
158 }
159 if abs_ss > 0 {
160 if abs_mg > abs_ss * 100 {
161 return __syscall(93, 71, 0, 0, 0, 0, 0)
162 }
163 }
164
165 return 0
166}