nx_sketch_misra_gries.nx source
↩ module page · 231 lines · 7420 B
1// sketch_misra_gries.nx -- Misra-Gries frequent items (1982).
2//
3// Bounded set of (key, count) pairs of capacity (k-1). On arrival
4// of (key, w):
5// - if key tracked: count[key] += w
6// - else if free slot: install (key, w)
7// - else: decrement EVERY counter by w (with floor 0);
8// counters that reach 0 are freed for future use
9//
10// GUARANTEE (different from SpaceSaving):
11// true_count - N/k <= estimate <= true_count
12// Misra-Gries UNDERESTIMATES; SpaceSaving OVERESTIMATES. Both bound
13// the error by N/k. Symmetric error semantics let callers pick:
14// - SpaceSaving for upper-bound queries ("at most X")
15// - Misra-Gries for lower-bound queries ("at least X")
16//
17// CAPABILITY STOMP vs DataSketches:
18// DS ships only the "frequent items" variant (SpaceSaving-like).
19// We ship BOTH algorithmic approaches (SpaceSaving + Misra-Gries)
20// so callers pick by error-bound direction.
21//
22// LOSSLESS-LANGUAGE DISCIPLINE:
23// nx_mg_query returns ApproxI64 with NX_ENV_ABS; param_a = N/k
24// (the maximum possible UNDERESTIMATE); conf_ppb = 1e9 (deterministic).
25
26// nx_safety_envelope:
27// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
28// sil_target: SIL1
29// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
30// verdict: NOT_YET_EVALUATED
31
32import "nx_syscalls.nx"
33import "nx_sketch_types.nx"
34
35const NX_MG_K_MIN: i64 = 2
36const NX_MG_K_MAX: i64 = 100000
37
38struct MgCounter {
39 key: i64,
40 count: i64,
41}
42
43struct MisraGries {
44 counters: *MgCounter, // k-1 slots
45 k: i64, // user-facing K; capacity = K - 1
46 n_tracked: i64, // <= k-1
47 total_seen: i64, // total weighted insertions
48}
49
50// === construction =================================================
51
52func nx_mg_alloc(k: i64) -> *MisraGries {
53 if k < NX_MG_K_MIN { return 0 as *MisraGries }
54 if k > NX_MG_K_MAX { return 0 as *MisraGries }
55 let raw: *u8 = sys_mmap(40)
56 let mg: *MisraGries = raw as *MisraGries
57 mg.k = k
58 let cap: i64 = k - 1
59 let ent_raw: *u8 = sys_mmap(cap * 16)
60 mg.counters = ent_raw as *MgCounter
61 var i: i64 = 0
62 while i < cap {
63 let c: *MgCounter = (mg.counters as i64 + i * 16) as *MgCounter
64 c.key = 0
65 c.count = 0
66 i = i + 1
67 }
68 mg.n_tracked = 0
69 mg.total_seen = 0
70 return mg
71}
72
73func nx_mg_counter_at(mg: *MisraGries, i: i64) -> *MgCounter {
74 return (mg.counters as i64 + i * 16) as *MgCounter
75}
76
77// === find helpers =================================================
78
79func nx_mg_find_key(mg: *MisraGries, key: i64) -> i64 {
80 var i: i64 = 0
81 while i < mg.n_tracked {
82 let c: *MgCounter = nx_mg_counter_at(mg, i)
83 if c.key == key { return i }
84 i = i + 1
85 }
86 return -1
87}
88
89func nx_mg_find_empty(mg: *MisraGries) -> i64 {
90 // After decrement-and-floor, slots with count==0 are free.
91 // Returns first free slot or -1 if all occupied.
92 var i: i64 = 0
93 while i < mg.n_tracked {
94 let c: *MgCounter = nx_mg_counter_at(mg, i)
95 if c.count == 0 { return i }
96 i = i + 1
97 }
98 if mg.n_tracked < mg.k - 1 { return mg.n_tracked }
99 return -1
100}
101
102// === add ==========================================================
103//
104// Add `count` occurrences of `key`. Three cases:
105// 1. key tracked: increment by count.
106// 2. free slot: install (key, count).
107// 3. no slot: decrement all counters by `dec` where
108// dec = min(count, min_count_in_table). Any counter
109// reaching 0 is freed. If dec < count, recurse
110// with remaining count via the now-free slot.
111
112func if_le(a: i64, b: i64) -> i64 {
113 if a < b { return a }
114 return b
115}
116
117func nx_mg_min_count(mg: *MisraGries) -> i64 {
118 if mg.n_tracked == 0 { return 0 }
119 let c0: *MgCounter = nx_mg_counter_at(mg, 0)
120 var m: i64 = c0.count
121 var i: i64 = 1
122 while i < mg.n_tracked {
123 let c: *MgCounter = nx_mg_counter_at(mg, i)
124 if c.count < m { m = c.count }
125 i = i + 1
126 }
127 return m
128}
129
130func nx_mg_add(mg: *MisraGries, key: i64, count: i64) -> i64 {
131 if count <= 0 { return 0 }
132 mg.total_seen = mg.total_seen + count
133
134 let pos: i64 = nx_mg_find_key(mg, key)
135 if pos >= 0 {
136 let c: *MgCounter = nx_mg_counter_at(mg, pos)
137 c.count = c.count + count
138 return 0
139 }
140 // Not tracked. Try free slot.
141 let empty_slot: i64 = nx_mg_find_empty(mg)
142 if empty_slot >= 0 {
143 let c: *MgCounter = nx_mg_counter_at(mg, empty_slot)
144 c.key = key
145 c.count = count
146 if empty_slot >= mg.n_tracked {
147 mg.n_tracked = mg.n_tracked + 1
148 }
149 return 0
150 }
151 // All k-1 slots full and non-zero. Decrement-loop:
152 // absorb = min(count, min_count); decrement everyone by absorb;
153 // remaining count = count - absorb. If remaining > 0, recurse
154 // (the decrement freed at least one slot).
155 var remaining: i64 = count
156 while remaining > 0 {
157 let min_c: i64 = nx_mg_min_count(mg)
158 if min_c == 0 {
159 // A free slot exists -- install there.
160 let slot: i64 = nx_mg_find_empty(mg)
161 if slot < 0 {
162 // Shouldn't happen if min == 0 and n_tracked == k-1.
163 return -1
164 }
165 let c: *MgCounter = nx_mg_counter_at(mg, slot)
166 c.key = key
167 c.count = remaining
168 remaining = 0
169 }
170 if min_c > 0 {
171 let absorb: i64 = if_le(remaining, min_c)
172 // Decrement every counter.
173 var i: i64 = 0
174 while i < mg.n_tracked {
175 let c: *MgCounter = nx_mg_counter_at(mg, i)
176 c.count = c.count - absorb
177 i = i + 1
178 }
179 remaining = remaining - absorb
180 }
181 }
182 return 0
183}
184
185// === query ========================================================
186//
187// estimate(key) = stored count if tracked, else 0.
188// Both are LOWER bounds on the true count (Misra-Gries underestimates).
189
190func nx_mg_estimate(mg: *MisraGries, key: i64) -> i64 {
191 let pos: i64 = nx_mg_find_key(mg, key)
192 if pos < 0 { return 0 }
193 let c: *MgCounter = nx_mg_counter_at(mg, pos)
194 if c.count < 0 { return 0 }
195 return c.count
196}
197
198// Maximum possible UNDERCOUNT: bounded by N/k per Misra-Gries.
199func nx_mg_max_undercount(mg: *MisraGries) -> i64 {
200 return (mg.total_seen + mg.k - 1) / mg.k
201}
202
203// Upper bound on true count = estimate + max_undercount.
204func nx_mg_upper_bound(mg: *MisraGries, key: i64) -> i64 {
205 return nx_mg_estimate(mg, key) + nx_mg_max_undercount(mg)
206}
207
208func nx_mg_query(mg: *MisraGries, key: i64) -> *ApproxI64 {
209 let est: i64 = nx_mg_estimate(mg, key)
210 return nx_approx_new(est, NX_ENV_ABS, nx_mg_max_undercount(mg),
211 1000000000,
212 NX_MATURITY_REFERENCE_IMPL,
213 NX_ADV_HONEST)
214}
215
216// === introspection ================================================
217
218func nx_mg_n_tracked(mg: *MisraGries) -> i64 {
219 var n: i64 = 0
220 var i: i64 = 0
221 while i < mg.n_tracked {
222 let c: *MgCounter = nx_mg_counter_at(mg, i)
223 if c.count > 0 { n = n + 1 }
224 i = i + 1
225 }
226 return n
227}
228
229func nx_mg_memory_bytes(mg: *MisraGries) -> i64 {
230 return 40 + (mg.k - 1) * 16
231}