nx_sketch_cpc_dense.nx source
↩ module page · 214 lines · 7186 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"
38import "nx_vecmath.nx"
39const NX_MAGIC_1000000: i64 = 1000000
40const NX_MAGIC_1000000000: i64 = 1000000000
41const NX_MAGIC_682700000: i64 = 682700000
42
43const NX_CPCD_MIN_LG_K: i64 = 2
44const NX_CPCD_MAX_LG_K: i64 = 12
45const NX_CPCD_MIN_W: i64 = 4
46const NX_CPCD_MAX_W: i64 = 64
47
48struct CpcDense {
49 bitmap: *u8,
50 n_bytes: i64,
51 lg_k: i64,
52 m: i64, // = 1 << lg_k
53 w: i64, // window/rows per column
54 big_m: i64, // = m * w
55 n_set: i64, // count of set bits
56 kappa_ppm: i64, // HIP accumulator in PPM
57 seed: i64,
58}
59
60// === clz32 helper =================================================
61
62// Delegated to nx_bits_clz32 (intrinsic dispatch -- bsr+xor / clzw).
63func nx_cpcd_clz32(x: i64) -> i64 {
64 return nx_bits_clz32(x)
65}
66
67// === construction =================================================
68
69func nx_cpcd_alloc(lg_k: i64, w: i64, seed: i64) -> *CpcDense {
70 if lg_k < NX_CPCD_MIN_LG_K { return 0 as *CpcDense }
71 if lg_k > NX_CPCD_MAX_LG_K { return 0 as *CpcDense }
72 if w < NX_CPCD_MIN_W { return 0 as *CpcDense }
73 if w > NX_CPCD_MAX_W { return 0 as *CpcDense }
74 let raw: *u8 = sys_mmap(72)
75 let c: *CpcDense = raw as *CpcDense
76 c.lg_k = lg_k
77 c.m = 1 << lg_k
78 c.w = w
79 c.big_m = c.m * w
80 let n_bits: i64 = c.big_m
81 let n_bytes: i64 = (n_bits + 7) / 8
82 c.bitmap = sys_mmap(n_bytes)
83 var i: i64 = 0
84 while i < n_bytes {
85 c.bitmap[i] = 0
86 i = i + 1
87 }
88 c.n_bytes = n_bytes
89 c.n_set = 0
90 c.kappa_ppm = 0
91 c.seed = seed
92 return c
93}
94
95// === bit access ===================================================
96
97func nx_cpcd_bit_get(c: *CpcDense, idx: i64) -> i64 {
98 let byte_idx: i64 = idx >> 3
99 let bit_pos: i64 = idx & 7
100 return (c.bitmap[byte_idx] >> bit_pos) & 1
101}
102
103func nx_cpcd_bit_set(c: *CpcDense, idx: i64) -> i64 {
104 let byte_idx: i64 = idx >> 3
105 let bit_pos: i64 = idx & 7
106 let prev: i64 = c.bitmap[byte_idx]
107 let mask: i64 = 1 << bit_pos
108 c.bitmap[byte_idx] = prev | mask
109 return 0
110}
111
112// === coupon derivation ============================================
113//
114// column = high lg_k bits of mh1
115// row = clz32(mh2) mod w
116// bit_idx = column * w + row
117
118func nx_cpcd_coupon_pos(c: *CpcDense, key: *u8, len: i64) -> i64 {
119 let h_hi: i64 = murmur3_32(c.seed ^ 0x9747B28C, key, len) & 0xFFFFFFFF
120 let h_lo: i64 = murmur3_32(c.seed ^ 0x36185EC0, key, len) & 0xFFFFFFFF
121 let column: i64 = (h_hi >> (32 - c.lg_k)) & (c.m - 1)
122 var row: i64 = nx_cpcd_clz32(h_lo)
123 if row >= c.w { row = c.w - 1 }
124 return column * c.w + row
125}
126
127// === add ==========================================================
128
129func nx_cpcd_add(c: *CpcDense, key: *u8, len: i64) -> i64 {
130 let idx: i64 = nx_cpcd_coupon_pos(c, key, len)
131 if nx_cpcd_bit_get(c, idx) == 1 { return 0 }
132 // New bit: HIP update.
133 let denom: i64 = c.big_m - c.n_set
134 if denom <= 0 { return -1 } // saturated
135 let delta: i64 = (c.big_m * NX_MAGIC_1000000) / denom
136 c.kappa_ppm = c.kappa_ppm + delta
137 nx_cpcd_bit_set(c, idx)
138 c.n_set = c.n_set + 1
139 return 0
140}
141
142// === estimate =====================================================
143
144func nx_cpcd_estimate(c: *CpcDense) -> i64 {
145 return c.kappa_ppm / NX_MAGIC_1000000
146}
147
148// === isqrt ========================================================
149
150func nx_cpcd_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
151
152// === typed envelope ===============================================
153
154func nx_cpcd_stddev_rel_ppb(c: *CpcDense) -> i64 {
155 let sq: i64 = nx_cpcd_isqrt(c.big_m)
156 if sq == 0 { return NX_MAGIC_1000000000 }
157 return NX_MAGIC_1000000000 / sq
158}
159
160func nx_cpcd_query(c: *CpcDense) -> *ApproxI64 {
161 let est: i64 = nx_cpcd_estimate(c)
162 return nx_approx_new(est, NX_ENV_REL_STDDEV,
163 nx_cpcd_stddev_rel_ppb(c),
164 NX_MAGIC_682700000,
165 NX_MATURITY_PRODUCTION,
166 NX_ADV_HONEST)
167}
168
169// === merge ========================================================
170//
171// Bitwise OR; HIP must be recomputed because shared bits add only once.
172
173func nx_cpcd_merge(a: *CpcDense, b: *CpcDense) -> *CpcDense {
174 if a.lg_k != b.lg_k { return 0 as *CpcDense }
175 if a.w != b.w { return 0 as *CpcDense }
176 if a.seed != b.seed { return 0 as *CpcDense }
177 let out: *CpcDense = nx_cpcd_alloc(a.lg_k, a.w, a.seed)
178 // Walk every bit position; for each set in either input, HIP-add.
179 var i: i64 = 0
180 while i < a.big_m {
181 let bit_a: i64 = nx_cpcd_bit_get(a, i)
182 let bit_b: i64 = nx_cpcd_bit_get(b, i)
183 if bit_a == 1 {
184 nx_cpcd_bit_set(out, i)
185 let denom: i64 = out.big_m - out.n_set
186 if denom > 0 {
187 out.kappa_ppm = out.kappa_ppm + (out.big_m * NX_MAGIC_1000000) / denom
188 }
189 out.n_set = out.n_set + 1
190 }
191 if bit_a == 0 {
192 if bit_b == 1 {
193 nx_cpcd_bit_set(out, i)
194 let denom: i64 = out.big_m - out.n_set
195 if denom > 0 {
196 out.kappa_ppm = out.kappa_ppm + (out.big_m * NX_MAGIC_1000000) / denom
197 }
198 out.n_set = out.n_set + 1
199 }
200 }
201 i = i + 1
202 }
203 return out
204}
205
206// === introspection ================================================
207
208func nx_cpcd_n_set(c: *CpcDense) -> i64 { return c.n_set }
209func nx_cpcd_big_m(c: *CpcDense) -> i64 { return c.big_m }
210
211// Memory: header + bitmap bytes (NO hash map overhead).
212func nx_cpcd_memory_bytes(c: *CpcDense) -> i64 {
213 return 72 + c.n_bytes
214}