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