nx_sketch_cpc_dense.nx source
↩ module page · 228 lines · 7480 B
1// sketch_cpc_dense.nx -- CPC dense bitmap mode + HIP estimator.
2//
3// FIXES THE V1 SPARSE-MODE MEMORY LOSS.
4//
5// Sparse mode (sketch_cpc.nx) stores explicit coupons in a hash map: ~24
6// bytes per distinct coupon. At 1000 coupons: ~24KB, much larger than
7// HLL_8's 128 bytes. That's why the v1 bench reported MEMORY: LOSES.
8//
9// DENSE MODE bitmap: m * w bits total (m columns x w rows per column).
10// For matched accuracy with HLL_8 (m_hll=128, 9.2% stddev), CPC needs
11// big_M ~= 128 coupons. Configurations:
12// m=8, w=16 -> 128 bits = 16 bytes (8x smaller than HLL_8)
13// m=16, w=8 -> 128 bits = 16 bytes
14// m=32, w=32 -> 1024 bits = 128 bytes (matched accuracy as HLL_8x8)
15//
16// HIP ESTIMATOR (Cohen 2015, Lang 2017):
17// On each NEW bit set (n_set transitions from k to k+1):
18// kappa += big_M / (big_M - k)
19// estimate = kappa
20//
21// COMPLEMENTS sketch_cpc (sparse mode):
22// - sparse: small N, exact storage, larger memory per coupon
23// - dense: bounded memory, HIP estimator, near-optimal variance
24//
25// LOSSLESS-LANGUAGE DISCIPLINE: rel_stddev ~ 1/sqrt(big_M), same as
26// sparse-mode CPC. Production tier (bounded memory, deterministic).
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_murmur3.nx"
36import "nx_bits.nx"
37import "nx_sketch_types.nx"
38const NX_MAGIC_1000000: i64 = 1000000
39const NX_MAGIC_1000000000: i64 = 1000000000
40const NX_MAGIC_682700000: i64 = 682700000
41
42const NX_CPCD_MIN_LG_K: i64 = 2
43const NX_CPCD_MAX_LG_K: i64 = 12
44const NX_CPCD_MIN_W: i64 = 4
45const NX_CPCD_MAX_W: i64 = 64
46
47struct CpcDense {
48 bitmap: *u8,
49 n_bytes: i64,
50 lg_k: i64,
51 m: i64, // = 1 << lg_k
52 w: i64, // window/rows per column
53 big_m: i64, // = m * w
54 n_set: i64, // count of set bits
55 kappa_ppm: i64, // HIP accumulator in PPM
56 seed: i64,
57}
58
59// === clz32 helper =================================================
60
61// Delegated to nx_bits_clz32 (intrinsic dispatch -- bsr+xor / clzw).
62func nx_cpcd_clz32(x: i64) -> i64 {
63 return nx_bits_clz32(x)
64}
65
66// === construction =================================================
67
68func nx_cpcd_alloc(lg_k: i64, w: i64, seed: i64) -> *CpcDense {
69 if lg_k < NX_CPCD_MIN_LG_K { return 0 as *CpcDense }
70 if lg_k > NX_CPCD_MAX_LG_K { return 0 as *CpcDense }
71 if w < NX_CPCD_MIN_W { return 0 as *CpcDense }
72 if w > NX_CPCD_MAX_W { return 0 as *CpcDense }
73 let raw: *u8 = sys_mmap(72)
74 let c: *CpcDense = raw as *CpcDense
75 c.lg_k = lg_k
76 c.m = 1 << lg_k
77 c.w = w
78 c.big_m = c.m * w
79 let n_bits: i64 = c.big_m
80 let n_bytes: i64 = (n_bits + 7) / 8
81 c.bitmap = sys_mmap(n_bytes)
82 var i: i64 = 0
83 while i < n_bytes {
84 c.bitmap[i] = 0
85 i = i + 1
86 }
87 c.n_bytes = n_bytes
88 c.n_set = 0
89 c.kappa_ppm = 0
90 c.seed = seed
91 return c
92}
93
94// === bit access ===================================================
95
96func nx_cpcd_bit_get(c: *CpcDense, idx: i64) -> i64 {
97 let byte_idx: i64 = idx >> 3
98 let bit_pos: i64 = idx & 7
99 return (c.bitmap[byte_idx] >> bit_pos) & 1
100}
101
102func nx_cpcd_bit_set(c: *CpcDense, idx: i64) -> i64 {
103 let byte_idx: i64 = idx >> 3
104 let bit_pos: i64 = idx & 7
105 let prev: i64 = c.bitmap[byte_idx]
106 let mask: i64 = 1 << bit_pos
107 c.bitmap[byte_idx] = prev | mask
108 return 0
109}
110
111// === coupon derivation ============================================
112//
113// column = high lg_k bits of mh1
114// row = clz32(mh2) mod w
115// bit_idx = column * w + row
116
117func nx_cpcd_coupon_pos(c: *CpcDense, key: *u8, len: i64) -> i64 {
118 let h_hi: i64 = murmur3_32(c.seed ^ 0x9747B28C, key, len) & 0xFFFFFFFF
119 let h_lo: i64 = murmur3_32(c.seed ^ 0x36185EC0, key, len) & 0xFFFFFFFF
120 let column: i64 = (h_hi >> (32 - c.lg_k)) & (c.m - 1)
121 var row: i64 = nx_cpcd_clz32(h_lo)
122 if row >= c.w { row = c.w - 1 }
123 return column * c.w + row
124}
125
126// === add ==========================================================
127
128func nx_cpcd_add(c: *CpcDense, key: *u8, len: i64) -> i64 {
129 let idx: i64 = nx_cpcd_coupon_pos(c, key, len)
130 if nx_cpcd_bit_get(c, idx) == 1 { return 0 }
131 // New bit: HIP update.
132 let denom: i64 = c.big_m - c.n_set
133 if denom <= 0 { return -1 } // saturated
134 let delta: i64 = (c.big_m * NX_MAGIC_1000000) / denom
135 c.kappa_ppm = c.kappa_ppm + delta
136 nx_cpcd_bit_set(c, idx)
137 c.n_set = c.n_set + 1
138 return 0
139}
140
141// === estimate =====================================================
142
143func nx_cpcd_estimate(c: *CpcDense) -> i64 {
144 return c.kappa_ppm / NX_MAGIC_1000000
145}
146
147// === isqrt ========================================================
148
149func nx_cpcd_isqrt(x: i64) -> i64 {
150 if x < 0 { return 0 }
151 if x == 0 { return 0 }
152 if x < 4 { return 1 }
153 var g: i64 = (x >> 1) + 1
154 var iter: i64 = 0
155 while iter < 64 {
156 let next_g: i64 = (g + x / g) / 2
157 if next_g >= g { iter = 64 }
158 if next_g < g {
159 g = next_g
160 iter = iter + 1
161 }
162 }
163 return g
164}
165
166// === typed envelope ===============================================
167
168func nx_cpcd_stddev_rel_ppb(c: *CpcDense) -> i64 {
169 let sq: i64 = nx_cpcd_isqrt(c.big_m)
170 if sq == 0 { return NX_MAGIC_1000000000 }
171 return NX_MAGIC_1000000000 / sq
172}
173
174func nx_cpcd_query(c: *CpcDense) -> *ApproxI64 {
175 let est: i64 = nx_cpcd_estimate(c)
176 return nx_approx_new(est, NX_ENV_REL_STDDEV,
177 nx_cpcd_stddev_rel_ppb(c),
178 NX_MAGIC_682700000,
179 NX_MATURITY_PRODUCTION,
180 NX_ADV_HONEST)
181}
182
183// === merge ========================================================
184//
185// Bitwise OR; HIP must be recomputed because shared bits add only once.
186
187func nx_cpcd_merge(a: *CpcDense, b: *CpcDense) -> *CpcDense {
188 if a.lg_k != b.lg_k { return 0 as *CpcDense }
189 if a.w != b.w { return 0 as *CpcDense }
190 if a.seed != b.seed { return 0 as *CpcDense }
191 let out: *CpcDense = nx_cpcd_alloc(a.lg_k, a.w, a.seed)
192 // Walk every bit position; for each set in either input, HIP-add.
193 var i: i64 = 0
194 while i < a.big_m {
195 let bit_a: i64 = nx_cpcd_bit_get(a, i)
196 let bit_b: i64 = nx_cpcd_bit_get(b, i)
197 if bit_a == 1 {
198 nx_cpcd_bit_set(out, i)
199 let denom: i64 = out.big_m - out.n_set
200 if denom > 0 {
201 out.kappa_ppm = out.kappa_ppm + (out.big_m * NX_MAGIC_1000000) / denom
202 }
203 out.n_set = out.n_set + 1
204 }
205 if bit_a == 0 {
206 if bit_b == 1 {
207 nx_cpcd_bit_set(out, i)
208 let denom: i64 = out.big_m - out.n_set
209 if denom > 0 {
210 out.kappa_ppm = out.kappa_ppm + (out.big_m * NX_MAGIC_1000000) / denom
211 }
212 out.n_set = out.n_set + 1
213 }
214 }
215 i = i + 1
216 }
217 return out
218}
219
220// === introspection ================================================
221
222func nx_cpcd_n_set(c: *CpcDense) -> i64 { return c.n_set }
223func nx_cpcd_big_m(c: *CpcDense) -> i64 { return c.big_m }
224
225// Memory: header + bitmap bytes (NO hash map overhead).
226func nx_cpcd_memory_bytes(c: *CpcDense) -> i64 {
227 return 72 + c.n_bytes
228}