nx_sketch_cpc.nx source

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