sketch_cpc.nx source
↩ module page · 174 lines · 6470 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"
44import "nx_vecmath.nx"
45
46const NX_CPC_MIN_LG_K: i64 = 4
47const NX_CPC_MAX_LG_K: i64 = 14
48const NX_CPC_WINDOW: i64 = 32 // rows per column (bits of rho)
49const NX_CPC_SEED_HI: i64 = 0x9747B28C
50const NX_CPC_SEED_LO: i64 = 0x36185EC0
51
52struct Cpc {
53 coupons: *HashMap, // set of distinct coupon_ids
54 lg_k: i64,
55 m: i64, // = 1 << lg_k
56 big_m: i64, // = m * NX_CPC_WINDOW (total possible coupons)
57 kappa_ppm: i64, // HIP accumulator in PPM
58 seed: i64,
59}
60
61// === bit-length helper (count leading zeros, 32-bit) ==============
62
63// Delegated to nx_bits_clz32 (intrinsic dispatch -- bsr+xor / clzw).
64// CPC's rho computation is in the hot insert path.
65func nx_cpc_clz32(x: i64) -> i64 {
66 return nx_bits_clz32(x)
67}
68
69// === construction =================================================
70//
71// HashMap capacity should be at least 2 * expected_coupons to keep
72// load factor under 50% (linear-probe efficiency).
73
74func nx_cpc_alloc(lg_k: i64, hashmap_cap: i64, seed: i64) -> *Cpc {
75 if lg_k < NX_CPC_MIN_LG_K { return 0 as *Cpc }
76 if lg_k > NX_CPC_MAX_LG_K { return 0 as *Cpc }
77 let hmap: *HashMap = nx_hmap_alloc(hashmap_cap)
78 if hmap == (0 as *HashMap) { return 0 as *Cpc }
79 let raw: *u8 = sys_mmap(56)
80 let c: *Cpc = raw as *Cpc
81 c.coupons = hmap
82 c.lg_k = lg_k
83 c.m = 1 << lg_k
84 c.big_m = c.m * NX_CPC_WINDOW
85 c.kappa_ppm = 0
86 c.seed = seed
87 return c
88}
89
90// === coupon derivation ============================================
91//
92// Hash key -> 64-bit value, split into (column, row).
93// column = high lg_k bits of murmur3_32 with HI seed
94// row = clz32(low 32 bits) + 1, capped at NX_CPC_WINDOW
95// coupon_id = column * window + (row - 1)
96
97func nx_cpc_coupon(c: *Cpc, key: *u8, len: i64) -> i64 {
98 let h_hi: i64 = murmur3_32(c.seed ^ NX_CPC_SEED_HI, key, len) & 0xFFFFFFFF
99 let h_lo: i64 = murmur3_32(c.seed ^ NX_CPC_SEED_LO, key, len) & 0xFFFFFFFF
100 let column: i64 = h_hi & (c.m - 1)
101 var row: i64 = nx_cpc_clz32(h_lo) + 1
102 if row > NX_CPC_WINDOW { row = NX_CPC_WINDOW }
103 return column * NX_CPC_WINDOW + (row - 1) + 1 // shift +1 to avoid hashmap sentinel 0
104}
105
106// === HIP accumulator on new coupon ===============================
107//
108// On insertion of a new (previously-unseen) coupon at distinct-count i
109// (before counting this one):
110// kappa += big_M / (big_M - i)
111// in PPM scale: kappa_ppm += big_M * 1_000_000 / (big_M - i)
112
113func nx_cpc_hip_add(c: *Cpc, n_before: i64) -> i64 {
114 let denom: i64 = c.big_m - n_before
115 if denom <= 0 { return -1 } // saturated; rare for sparse mode
116 let delta: i64 = (c.big_m * 1000000) / denom
117 c.kappa_ppm = c.kappa_ppm + delta
118 return 0
119}
120
121// === add ==========================================================
122
123func nx_cpc_add(c: *Cpc, key: *u8, len: i64) -> i64 {
124 let coupon: i64 = nx_cpc_coupon(c, key, len)
125 if nx_hmap_has(c.coupons, coupon) == 1 { return 0 } // duplicate
126 let n_before: i64 = nx_hmap_size(c.coupons)
127 let r: i64 = nx_hmap_put(c.coupons, coupon, 1)
128 if r < 0 { return r } // table full
129 nx_cpc_hip_add(c, n_before)
130 return 0
131}
132
133// === estimate =====================================================
134//
135// HIP estimate is kappa itself (in PPM, then divided).
136
137func nx_cpc_estimate(c: *Cpc) -> i64 {
138 return c.kappa_ppm / 1000000
139}
140
141// === typed envelope ===============================================
142//
143// rel_stddev_ppb = 1 / sqrt(big_M) approximately. Tabulate by lg_k.
144
145func nx_cpc_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
146
147func nx_cpc_stddev_rel_ppb(c: *Cpc) -> i64 {
148 let sq: i64 = nx_cpc_isqrt(c.big_m)
149 if sq == 0 { return 1000000000 }
150 return 1000000000 / sq
151}
152
153func nx_cpc_query(c: *Cpc) -> *ApproxI64 {
154 let est: i64 = nx_cpc_estimate(c)
155 return nx_approx_new(est, NX_ENV_REL_STDDEV,
156 nx_cpc_stddev_rel_ppb(c),
157 682700000,
158 NX_MATURITY_REFERENCE_IMPL,
159 NX_ADV_HONEST)
160}
161
162// === introspection ================================================
163
164func nx_cpc_n_coupons(c: *Cpc) -> i64 {
165 return nx_hmap_size(c.coupons)
166}
167
168func nx_cpc_big_m(c: *Cpc) -> i64 {
169 return c.big_m
170}
171
172func nx_cpc_memory_bytes(c: *Cpc) -> i64 {
173 return 56 + nx_hmap_memory_bytes(c.coupons)
174}