nx_sketch_cms.nx source
↩ module page · 219 lines · 7593 B
1// sketch_cms.nx -- Count-Min Sketch in NishiLang.
2//
3// Cormode-Muthukrishnan 2005. d-row x w-column counter grid;
4// add() increments d counters chosen by d hash functions of the
5// item; estimate() returns the MIN across rows -- overestimate-
6// only by construction (no false negatives).
7//
8// Provable bound:
9// Pr[estimate(x) <= true(x) + eps * totalCount] >= 1 - delta
10// for d = ceil(ln(1/delta)), w = ceil(e / eps)
11//
12// Defaults d=5, w=2718 -> eps ~ 0.001, delta ~ 0.007 (~ e^-5).
13// Memory: 8 * d * w bytes (i64 counters). d=5, w=2718 -> 109 KB.
14//
15// KIRSCH-MITZENMACHER 2008 double-hashing:
16// Instead of d independent murmur calls, compute ONE 64-bit hash
17// (hi, lo) and derive d row indices via h_i(x) = (hi + i * lo) ^
18// seeds[i] mod w. Gives near-independent rows at single-hash
19// cost. Mirrors core-sketch/cms.ts.
20//
21// LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
22// nx_cms_query returns ApproxI64 with envelope_kind = NX_ENV_ABS
23// (absolute additive bound = eps * totalCount), NOT rel_stddev.
24// Substrate's typed envelope discriminator forces callers to
25// handle the abs-vs-relative distinction explicitly.
26
27// nx_safety_envelope:
28// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
29// sil_target: SIL1
30// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
31// verdict: NOT_YET_EVALUATED
32
33import "nx_syscalls.nx"
34import "nx_murmur3.nx"
35import "nx_sketch_hll.nx"
36import "nx_sketch_types.nx"
37
38const NX_CMS_D_MIN: i64 = 1
39const NX_CMS_D_MAX: i64 = 32
40const NX_CMS_W_MIN: i64 = 16
41const NX_CMS_W_MAX: i64 = 16777216 // 16M counters per row
42
43const NX_CMS_SEED_DERIVE: i64 = 0x9E3779B9
44const NX_CMS_SEED_HI: i64 = 0x9747B28C
45const NX_CMS_SEED_LO: i64 = 0x36185EC0
46const NX_CMS_U32_MAX: i64 = 0xFFFFFFFF
47
48// Counter saturation: cap at U32_MAX (4.29e9) so a single counter
49// can hold up to 4-billion increments without overflow. Beyond
50// that, the overestimate already failed the user; saturating
51// avoids silent wraparound.
52
53struct Cms {
54 d: i64,
55 w: i64,
56 seed_base: i64,
57 seeds: *i64, // d entries
58 table: *i64, // d * w entries
59 total_count: i64,
60}
61
62// === construction =================================================
63
64func nx_cms_alloc(d: i64, w: i64, seed_base: i64) -> *Cms {
65 if d < NX_CMS_D_MIN { return 0 as *Cms }
66 if d > NX_CMS_D_MAX { return 0 as *Cms }
67 if w < NX_CMS_W_MIN { return 0 as *Cms }
68 if w > NX_CMS_W_MAX { return 0 as *Cms }
69 let raw: *u8 = sys_mmap(56)
70 let c: *Cms = raw as *Cms
71 c.d = d
72 c.w = w
73 c.seed_base = seed_base
74 let seeds_raw: *u8 = sys_mmap(d * 8)
75 c.seeds = seeds_raw as *i64
76 var i: i64 = 0
77 while i < d {
78 // Derive per-row salt via golden-ratio multiplication.
79 let mix: i64 = (i + 1) * NX_CMS_SEED_DERIVE
80 c.seeds[i] = (seed_base ^ mix) & 0xFFFFFFFF
81 i = i + 1
82 }
83 let table_bytes: i64 = d * w * 8
84 let table_raw: *u8 = sys_mmap(table_bytes)
85 c.table = table_raw as *i64
86 var j: i64 = 0
87 while j < d * w {
88 c.table[j] = 0
89 j = j + 1
90 }
91 c.total_count = 0
92 return c
93}
94
95// === hash64 (two-pass murmur3, same pattern as HLL) ===============
96//
97// Returns (hi, lo) packed: hi in low 32 bits of one i64, lo in
98// low 32 of another. Caller passes the result via two return
99// values is awkward without struct returns; we instead use two
100// separate functions or pack hi/lo into one i64. For CMS we
101// need both so we use Kirsch-Mitzenmacher derivation inline.
102
103func nx_cms_row_index(c: *Cms, hi: i64, lo: i64, i: i64) -> i64 {
104 // h_i(x) = ((hi + i * lo) ^ seeds[i]) mod w
105 let x: i64 = ((hi + (i + 1) * lo) ^ c.seeds[i]) & 0xFFFFFFFF
106 return x % c.w
107}
108
109// === add ==========================================================
110
111func nx_cms_add(c: *Cms, key: *u8, len: i64, count: i64) -> i64 {
112 if count <= 0 { return 0 }
113 let seed_hi: i64 = c.seed_base ^ NX_CMS_SEED_HI
114 let seed_lo: i64 = c.seed_base ^ NX_CMS_SEED_LO
115 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
116 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
117 var i: i64 = 0
118 while i < c.d {
119 let j: i64 = nx_cms_row_index(c, hi, lo, i)
120 let idx: i64 = i * c.w + j
121 let cur: i64 = c.table[idx]
122 let next: i64 = cur + count
123 if next > NX_CMS_U32_MAX {
124 c.table[idx] = NX_CMS_U32_MAX
125 }
126 if next <= NX_CMS_U32_MAX {
127 c.table[idx] = next
128 }
129 i = i + 1
130 }
131 c.total_count = c.total_count + count
132 return 0
133}
134
135// === estimate (min across rows) ===================================
136
137func nx_cms_estimate(c: *Cms, key: *u8, len: i64) -> i64 {
138 let seed_hi: i64 = c.seed_base ^ NX_CMS_SEED_HI
139 let seed_lo: i64 = c.seed_base ^ NX_CMS_SEED_LO
140 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
141 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
142 var min: i64 = NX_CMS_U32_MAX
143 var i: i64 = 0
144 while i < c.d {
145 let j: i64 = nx_cms_row_index(c, hi, lo, i)
146 let v: i64 = c.table[i * c.w + j]
147 if v < min { min = v }
148 i = i + 1
149 }
150 return min
151}
152
153// === error bound: eps * totalCount ================================
154//
155// CMS theory: Pr[est <= true + eps * N] >= 1 - delta
156// with eps ~ e / w. For w = 2718, eps ~ 0.001.
157// param_a in ApproxI64 holds the ABSOLUTE additive bound:
158// abs_bound = eps * totalCount = (e * totalCount) / w
159// We pre-multiply by 1000 and divide by 1000 to keep fixed-point
160// fidelity (~3 decimal places of eps). e_milli = 2718 (i.e. e * 1000).
161
162const NX_E_MILLI: i64 = 2718
163
164func nx_cms_abs_bound(c: *Cms) -> i64 {
165 // (NX_E_MILLI * total_count) / (1000 * w) ~ eps * N
166 let num: i64 = NX_E_MILLI * c.total_count
167 return num / (1000 * c.w)
168}
169
170// 1 - delta confidence. delta = e^-d. For d=5, delta ~ 0.0067 ~
171// confidence 0.9933. Hardcoded per d-value table.
172func nx_cms_conf_ppb(d: i64) -> i64 {
173 if d == 1 { return 632000000 } // 1 - 1/e ~ 0.632
174 if d == 2 { return 864700000 } // 1 - 1/e^2 ~ 0.865
175 if d == 3 { return 950200000 } // 1 - 1/e^3 ~ 0.950
176 if d == 4 { return 981700000 } // 1 - 1/e^4 ~ 0.982
177 if d == 5 { return 993300000 } // 1 - 1/e^5 ~ 0.993
178 if d == 6 { return 997500000 }
179 if d == 7 { return 999100000 }
180 if d == 8 { return 999700000 }
181 return 999900000
182}
183
184func nx_cms_query(c: *Cms, key: *u8, len: i64) -> *ApproxI64 {
185 let est: i64 = nx_cms_estimate(c, key, len)
186 return nx_approx_new(est, NX_ENV_ABS, nx_cms_abs_bound(c),
187 nx_cms_conf_ppb(c.d),
188 NX_MATURITY_REFERENCE_IMPL,
189 NX_ADV_HONEST)
190}
191
192// === merge =========================================================
193
194func nx_cms_merge(a: *Cms, b: *Cms) -> *Cms {
195 if a.d != b.d { return 0 as *Cms }
196 if a.w != b.w { return 0 as *Cms }
197 if a.seed_base != b.seed_base { return 0 as *Cms }
198 let out: *Cms = nx_cms_alloc(a.d, a.w, a.seed_base)
199 let n: i64 = a.d * a.w
200 var i: i64 = 0
201 while i < n {
202 let sum: i64 = a.table[i] + b.table[i]
203 if sum > NX_CMS_U32_MAX {
204 out.table[i] = NX_CMS_U32_MAX
205 }
206 if sum <= NX_CMS_U32_MAX {
207 out.table[i] = sum
208 }
209 i = i + 1
210 }
211 out.total_count = a.total_count + b.total_count
212 return out
213}
214
215// === memory introspection =========================================
216
217func nx_cms_memory_bytes(c: *Cms) -> i64 {
218 return 56 + c.d * 8 + c.d * c.w * 8
219}