sketch_cms.nx source
↩ module page · 213 lines · 7543 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
27import "syscalls.nx"
28import "murmur3.nx"
29import "sketch_hll.nx"
30import "sketch_types.nx"
31
32const NX_CMS_D_MIN: i64 = 1
33const NX_CMS_D_MAX: i64 = 32
34const NX_CMS_W_MIN: i64 = 16
35const NX_CMS_W_MAX: i64 = 16777216 // 16M counters per row
36
37const NX_CMS_SEED_DERIVE: i64 = 0x9E3779B9
38const NX_CMS_SEED_HI: i64 = 0x9747B28C
39const NX_CMS_SEED_LO: i64 = 0x36185EC0
40const NX_CMS_U32_MAX: i64 = 0xFFFFFFFF
41
42// Counter saturation: cap at U32_MAX (4.29e9) so a single counter
43// can hold up to 4-billion increments without overflow. Beyond
44// that, the overestimate already failed the user; saturating
45// avoids silent wraparound.
46
47struct Cms {
48 d: i64,
49 w: i64,
50 seed_base: i64,
51 seeds: *i64, // d entries
52 table: *i64, // d * w entries
53 total_count: i64,
54}
55
56// === construction =================================================
57
58func nx_cms_alloc(d: i64, w: i64, seed_base: i64) -> *Cms {
59 if d < NX_CMS_D_MIN { return 0 as *Cms }
60 if d > NX_CMS_D_MAX { return 0 as *Cms }
61 if w < NX_CMS_W_MIN { return 0 as *Cms }
62 if w > NX_CMS_W_MAX { return 0 as *Cms }
63 let raw: *u8 = sys_mmap(56)
64 let c: *Cms = raw as *Cms
65 c.d = d
66 c.w = w
67 c.seed_base = seed_base
68 let seeds_raw: *u8 = sys_mmap(d * 8)
69 c.seeds = seeds_raw as *i64
70 var i: i64 = 0
71 while i < d {
72 // Derive per-row salt via golden-ratio multiplication.
73 let mix: i64 = (i + 1) * NX_CMS_SEED_DERIVE
74 c.seeds[i] = (seed_base ^ mix) & 0xFFFFFFFF
75 i = i + 1
76 }
77 let table_bytes: i64 = d * w * 8
78 let table_raw: *u8 = sys_mmap(table_bytes)
79 c.table = table_raw as *i64
80 var j: i64 = 0
81 while j < d * w {
82 c.table[j] = 0
83 j = j + 1
84 }
85 c.total_count = 0
86 return c
87}
88
89// === hash64 (two-pass murmur3, same pattern as HLL) ===============
90//
91// Returns (hi, lo) packed: hi in low 32 bits of one i64, lo in
92// low 32 of another. Caller passes the result via two return
93// values is awkward without struct returns; we instead use two
94// separate functions or pack hi/lo into one i64. For CMS we
95// need both so we use Kirsch-Mitzenmacher derivation inline.
96
97func nx_cms_row_index(c: *Cms, hi: i64, lo: i64, i: i64) -> i64 {
98 // h_i(x) = ((hi + i * lo) ^ seeds[i]) mod w
99 let x: i64 = ((hi + (i + 1) * lo) ^ c.seeds[i]) & 0xFFFFFFFF
100 return x % c.w
101}
102
103// === add ==========================================================
104
105func nx_cms_add(c: *Cms, key: *u8, len: i64, count: i64) -> i64 {
106 if count <= 0 { return 0 }
107 let seed_hi: i64 = c.seed_base ^ NX_CMS_SEED_HI
108 let seed_lo: i64 = c.seed_base ^ NX_CMS_SEED_LO
109 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
110 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
111 var i: i64 = 0
112 while i < c.d {
113 let j: i64 = nx_cms_row_index(c, hi, lo, i)
114 let idx: i64 = i * c.w + j
115 let cur: i64 = c.table[idx]
116 let next: i64 = cur + count
117 if next > NX_CMS_U32_MAX {
118 c.table[idx] = NX_CMS_U32_MAX
119 }
120 if next <= NX_CMS_U32_MAX {
121 c.table[idx] = next
122 }
123 i = i + 1
124 }
125 c.total_count = c.total_count + count
126 return 0
127}
128
129// === estimate (min across rows) ===================================
130
131func nx_cms_estimate(c: *Cms, key: *u8, len: i64) -> i64 {
132 let seed_hi: i64 = c.seed_base ^ NX_CMS_SEED_HI
133 let seed_lo: i64 = c.seed_base ^ NX_CMS_SEED_LO
134 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
135 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
136 var min: i64 = NX_CMS_U32_MAX
137 var i: i64 = 0
138 while i < c.d {
139 let j: i64 = nx_cms_row_index(c, hi, lo, i)
140 let v: i64 = c.table[i * c.w + j]
141 if v < min { min = v }
142 i = i + 1
143 }
144 return min
145}
146
147// === error bound: eps * totalCount ================================
148//
149// CMS theory: Pr[est <= true + eps * N] >= 1 - delta
150// with eps ~ e / w. For w = 2718, eps ~ 0.001.
151// param_a in ApproxI64 holds the ABSOLUTE additive bound:
152// abs_bound = eps * totalCount = (e * totalCount) / w
153// We pre-multiply by 1000 and divide by 1000 to keep fixed-point
154// fidelity (~3 decimal places of eps). e_milli = 2718 (i.e. e * 1000).
155
156const NX_E_MILLI: i64 = 2718
157
158func nx_cms_abs_bound(c: *Cms) -> i64 {
159 // (NX_E_MILLI * total_count) / (1000 * w) ~ eps * N
160 let num: i64 = NX_E_MILLI * c.total_count
161 return num / (1000 * c.w)
162}
163
164// 1 - delta confidence. delta = e^-d. For d=5, delta ~ 0.0067 ~
165// confidence 0.9933. Hardcoded per d-value table.
166func nx_cms_conf_ppb(d: i64) -> i64 {
167 if d == 1 { return 632000000 } // 1 - 1/e ~ 0.632
168 if d == 2 { return 864700000 } // 1 - 1/e^2 ~ 0.865
169 if d == 3 { return 950200000 } // 1 - 1/e^3 ~ 0.950
170 if d == 4 { return 981700000 } // 1 - 1/e^4 ~ 0.982
171 if d == 5 { return 993300000 } // 1 - 1/e^5 ~ 0.993
172 if d == 6 { return 997500000 }
173 if d == 7 { return 999100000 }
174 if d == 8 { return 999700000 }
175 return 999900000
176}
177
178func nx_cms_query(c: *Cms, key: *u8, len: i64) -> *ApproxI64 {
179 let est: i64 = nx_cms_estimate(c, key, len)
180 return nx_approx_new(est, NX_ENV_ABS, nx_cms_abs_bound(c),
181 nx_cms_conf_ppb(c.d),
182 NX_MATURITY_REFERENCE_IMPL,
183 NX_ADV_HONEST)
184}
185
186// === merge =========================================================
187
188func nx_cms_merge(a: *Cms, b: *Cms) -> *Cms {
189 if a.d != b.d { return 0 as *Cms }
190 if a.w != b.w { return 0 as *Cms }
191 if a.seed_base != b.seed_base { return 0 as *Cms }
192 let out: *Cms = nx_cms_alloc(a.d, a.w, a.seed_base)
193 let n: i64 = a.d * a.w
194 var i: i64 = 0
195 while i < n {
196 let sum: i64 = a.table[i] + b.table[i]
197 if sum > NX_CMS_U32_MAX {
198 out.table[i] = NX_CMS_U32_MAX
199 }
200 if sum <= NX_CMS_U32_MAX {
201 out.table[i] = sum
202 }
203 i = i + 1
204 }
205 out.total_count = a.total_count + b.total_count
206 return out
207}
208
209// === memory introspection =========================================
210
211func nx_cms_memory_bytes(c: *Cms) -> i64 {
212 return 56 + c.d * 8 + c.d * c.w * 8
213}