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