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