sketch_cpc.nx source
↩ module page · 188 lines · 6779 B
1// sketch_cpc.nx -- CPC sparse-mode cardinality sketch (Lang 2017 / FM85).
2//
3// "Back to the Future: An Even More Nearly Optimal Cardinality Estimation
4// Algorithm" -- arXiv:1708.06839. CPC is the headline cardinality stomp
5// over HLL: same memory, tighter rel-stddev via the HIP estimator.
6//
7// THIS V1 SHIPS THE SPARSE MODE + HIP ESTIMATOR:
8// - sparse mode: store coupons in a hash set until capacity reached
9// - HIP estimator: kappa accumulates 1/theta on every distinct coupon
10//
11// DENSE MODE (pinned + sliding) queued for v2. Sparse mode alone is
12// sufficient for cardinalities up to ~K coupons (typical K=4096 -> exact
13// for n < ~3000, then accurate-via-HIP up to ~tens-of-thousands).
14//
15// COUPON DERIVATION:
16// hash(key) -> 64-bit value
17// column = (hash >> 32) & (m - 1) (high bits choose register column)
18// row = clz32(hash & 0xFFFFFFFF) + 1 (low bits drive rho, capped at w)
19// coupon_id = column * w + row (unique pair encoding)
20//
21// HIP ESTIMATOR (Cohen 2015, Lang 2017):
22// For each distinct coupon arrival i (0..n-1):
23// theta_i = (M - i) / M where M = m * w (total possible coupons)
24// kappa += 1 / theta_i = M / (M - i)
25// estimate = kappa
26// At i = 0 (first coupon): theta = 1.0; kappa += 1.
27// At i = M-1: theta = 1/M; kappa += M.
28//
29// COMPLEMENTS the cardinality family:
30// - HLL/LC/KMV/Theta: classical estimators, lots of variance
31// - CPC (this): HIP-based, near-optimal variance via online accounting
32//
33// COMPOSES against sketch_hash_map for sparse coupon storage.
34//
35// LOSSLESS-LANGUAGE DISCIPLINE: estimate has rel_stddev approx
36// 1/sqrt(M) at confidence 0.6827. For m=128, w=32 (M=4096): ~1.56% rel.
37// For HLL_8 lg_k=7 (m=128): ~9.2% rel. CPC stomp ~6x improvement.
38
39import "syscalls.nx"
40import "murmur3.nx"
41import "nx_bits.nx"
42import "sketch_hash_map.nx"
43import "sketch_types.nx"
44
45const NX_CPC_MIN_LG_K: i64 = 4
46const NX_CPC_MAX_LG_K: i64 = 14
47const NX_CPC_WINDOW: i64 = 32 // rows per column (bits of rho)
48const NX_CPC_SEED_HI: i64 = 0x9747B28C
49const NX_CPC_SEED_LO: i64 = 0x36185EC0
50
51struct Cpc {
52 coupons: *HashMap, // set of distinct coupon_ids
53 lg_k: i64,
54 m: i64, // = 1 << lg_k
55 big_m: i64, // = m * NX_CPC_WINDOW (total possible coupons)
56 kappa_ppm: i64, // HIP accumulator in PPM
57 seed: i64,
58}
59
60// === bit-length helper (count leading zeros, 32-bit) ==============
61
62// Delegated to nx_bits_clz32 (intrinsic dispatch -- bsr+xor / clzw).
63// CPC's rho computation is in the hot insert path.
64func nx_cpc_clz32(x: i64) -> i64 {
65 return nx_bits_clz32(x)
66}
67
68// === construction =================================================
69//
70// HashMap capacity should be at least 2 * expected_coupons to keep
71// load factor under 50% (linear-probe efficiency).
72
73func nx_cpc_alloc(lg_k: i64, hashmap_cap: i64, seed: i64) -> *Cpc {
74 if lg_k < NX_CPC_MIN_LG_K { return 0 as *Cpc }
75 if lg_k > NX_CPC_MAX_LG_K { return 0 as *Cpc }
76 let hmap: *HashMap = nx_hmap_alloc(hashmap_cap)
77 if hmap == (0 as *HashMap) { return 0 as *Cpc }
78 let raw: *u8 = sys_mmap(56)
79 let c: *Cpc = raw as *Cpc
80 c.coupons = hmap
81 c.lg_k = lg_k
82 c.m = 1 << lg_k
83 c.big_m = c.m * NX_CPC_WINDOW
84 c.kappa_ppm = 0
85 c.seed = seed
86 return c
87}
88
89// === coupon derivation ============================================
90//
91// Hash key -> 64-bit value, split into (column, row).
92// column = high lg_k bits of murmur3_32 with HI seed
93// row = clz32(low 32 bits) + 1, capped at NX_CPC_WINDOW
94// coupon_id = column * window + (row - 1)
95
96func nx_cpc_coupon(c: *Cpc, key: *u8, len: i64) -> i64 {
97 let h_hi: i64 = murmur3_32(c.seed ^ NX_CPC_SEED_HI, key, len) & 0xFFFFFFFF
98 let h_lo: i64 = murmur3_32(c.seed ^ NX_CPC_SEED_LO, key, len) & 0xFFFFFFFF
99 let column: i64 = h_hi & (c.m - 1)
100 var row: i64 = nx_cpc_clz32(h_lo) + 1
101 if row > NX_CPC_WINDOW { row = NX_CPC_WINDOW }
102 return column * NX_CPC_WINDOW + (row - 1) + 1 // shift +1 to avoid hashmap sentinel 0
103}
104
105// === HIP accumulator on new coupon ===============================
106//
107// On insertion of a new (previously-unseen) coupon at distinct-count i
108// (before counting this one):
109// kappa += big_M / (big_M - i)
110// in PPM scale: kappa_ppm += big_M * 1_000_000 / (big_M - i)
111
112func nx_cpc_hip_add(c: *Cpc, n_before: i64) -> i64 {
113 let denom: i64 = c.big_m - n_before
114 if denom <= 0 { return -1 } // saturated; rare for sparse mode
115 let delta: i64 = (c.big_m * 1000000) / denom
116 c.kappa_ppm = c.kappa_ppm + delta
117 return 0
118}
119
120// === add ==========================================================
121
122func nx_cpc_add(c: *Cpc, key: *u8, len: i64) -> i64 {
123 let coupon: i64 = nx_cpc_coupon(c, key, len)
124 if nx_hmap_has(c.coupons, coupon) == 1 { return 0 } // duplicate
125 let n_before: i64 = nx_hmap_size(c.coupons)
126 let r: i64 = nx_hmap_put(c.coupons, coupon, 1)
127 if r < 0 { return r } // table full
128 nx_cpc_hip_add(c, n_before)
129 return 0
130}
131
132// === estimate =====================================================
133//
134// HIP estimate is kappa itself (in PPM, then divided).
135
136func nx_cpc_estimate(c: *Cpc) -> i64 {
137 return c.kappa_ppm / 1000000
138}
139
140// === typed envelope ===============================================
141//
142// rel_stddev_ppb = 1 / sqrt(big_M) approximately. Tabulate by lg_k.
143
144func nx_cpc_isqrt(x: i64) -> i64 {
145 if x < 0 { return 0 }
146 if x == 0 { return 0 }
147 if x < 4 { return 1 }
148 var g: i64 = (x >> 1) + 1
149 var iter: i64 = 0
150 while iter < 64 {
151 let next_g: i64 = (g + x / g) / 2
152 if next_g >= g { iter = 64 }
153 if next_g < g {
154 g = next_g
155 iter = iter + 1
156 }
157 }
158 return g
159}
160
161func nx_cpc_stddev_rel_ppb(c: *Cpc) -> i64 {
162 let sq: i64 = nx_cpc_isqrt(c.big_m)
163 if sq == 0 { return 1000000000 }
164 return 1000000000 / sq
165}
166
167func nx_cpc_query(c: *Cpc) -> *ApproxI64 {
168 let est: i64 = nx_cpc_estimate(c)
169 return nx_approx_new(est, NX_ENV_REL_STDDEV,
170 nx_cpc_stddev_rel_ppb(c),
171 682700000,
172 NX_MATURITY_REFERENCE_IMPL,
173 NX_ADV_HONEST)
174}
175
176// === introspection ================================================
177
178func nx_cpc_n_coupons(c: *Cpc) -> i64 {
179 return nx_hmap_size(c.coupons)
180}
181
182func nx_cpc_big_m(c: *Cpc) -> i64 {
183 return c.big_m
184}
185
186func nx_cpc_memory_bytes(c: *Cpc) -> i64 {
187 return 56 + nx_hmap_memory_bytes(c.coupons)
188}