nx_sketch_linear_counter.nx source
↩ module page · 229 lines · 7684 B
1// sketch_linear_counter.nx -- Linear Counting (Whang-Vander Zanden 1990).
2//
3// Pre-HLL cardinality primitive. Simpler than HLL; sometimes more
4// accurate at small cardinalities (n < m/10). Used by Google's
5// BigQuery as the small-cardinality fallback.
6//
7// ALGORITHM:
8// bitmap of m bits, all zero initially.
9// add(x): set bit at index = hash(x) % m
10// estimate(n) = -m * ln(zeros / m)
11//
12// where zeros = count of unset bits at query time. Derivation: if
13// items are hashed uniformly to m buckets and we observe `zeros`
14// empty buckets, then by occupancy theory the true count n satisfies
15// E[zeros] = m * (1 - 1/m)^n ≈ m * e^(-n/m)
16// inverting: n ≈ -m * ln(zeros / m).
17//
18// CAPABILITIES (vs HLL):
19// - LC: accurate at n < m (uses bitmap directly)
20// - HLL: accurate at n >> m (uses harmonic mean of register maxima)
21// Together: BigQuery + others run LC for n < threshold, HLL for n >=.
22//
23// INTEGER-FIXED-POINT IMPLEMENTATION:
24// ln(zeros/m) approximated via tabulated values keyed on (zeros*100)/m
25// (percentage of empty bits, in [0, 100]). Table values are
26// -ln(p/100) * 1_000_000 in PPM (negative of -log so positive).
27//
28// MEMORY: m bits = m/8 bytes. For m=8192: 1 KB.
29//
30// LOSSLESS-LANGUAGE DISCIPLINE:
31// nx_lc_query returns ApproxI64 with NX_ENV_REL_STDDEV. Standard
32// error per Whang 1990: sqrt(e^t - t - 1) / t where t = n/m (load).
33// Tabulated by load class.
34
35// nx_safety_envelope:
36// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
37// sil_target: SIL1
38// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
39// verdict: NOT_YET_EVALUATED
40
41import "nx_syscalls.nx"
42import "nx_murmur3.nx"
43import "nx_sketch_types.nx"
44
45const NX_LC_MIN_BITS: i64 = 64
46const NX_LC_MAX_BITS: i64 = 16777216 // 2 MB cap
47
48struct LinearCounter {
49 bits: *u8, // m / 8 bytes
50 m_bits: i64, // bitmap size (power of 2)
51 mask: i64, // m_bits - 1
52 seed: i64,
53}
54
55// === construction =================================================
56
57func nx_lc_is_pow2(n: i64) -> i64 {
58 if n < NX_LC_MIN_BITS { return 0 }
59 if (n & (n - 1)) != 0 { return 0 }
60 return 1
61}
62
63func nx_lc_alloc(m_bits: i64, seed: i64) -> *LinearCounter {
64 if nx_lc_is_pow2(m_bits) != 1 { return 0 as *LinearCounter }
65 if m_bits > NX_LC_MAX_BITS { return 0 as *LinearCounter }
66 let raw: *u8 = sys_mmap(40)
67 let lc: *LinearCounter = raw as *LinearCounter
68 let bytes: i64 = m_bits / 8
69 lc.bits = sys_mmap(bytes)
70 var i: i64 = 0
71 while i < bytes {
72 lc.bits[i] = 0
73 i = i + 1
74 }
75 lc.m_bits = m_bits
76 lc.mask = m_bits - 1
77 lc.seed = seed
78 return lc
79}
80
81// === bit helpers =================================================
82
83func nx_lc_set_bit(lc: *LinearCounter, bit_idx: i64) -> i64 {
84 let byte_idx: i64 = bit_idx >> 3
85 let bit_pos: i64 = bit_idx & 7
86 lc.bits[byte_idx] = lc.bits[byte_idx] | (1 << bit_pos)
87 return 0
88}
89
90func nx_lc_get_bit(lc: *LinearCounter, bit_idx: i64) -> i64 {
91 let byte_idx: i64 = bit_idx >> 3
92 let bit_pos: i64 = bit_idx & 7
93 return (lc.bits[byte_idx] >> bit_pos) & 1
94}
95
96// === add ==========================================================
97
98func nx_lc_add(lc: *LinearCounter, key: *u8, len: i64) -> i64 {
99 let h: i64 = murmur3_32(lc.seed, key, len) & 0xFFFFFFFF
100 let bit_idx: i64 = h & lc.mask
101 nx_lc_set_bit(lc, bit_idx)
102 return 0
103}
104
105// === zero count ==================================================
106//
107// Walks the bitmap counting unset bits. Worst-case linear in m/8.
108// Optimization: use popcount per byte then subtract from 8 * bytes.
109
110func nx_lc_popcount_byte(b: i64) -> i64 {
111 var n: i64 = 0
112 var t: i64 = b & 0xFF
113 while t > 0 {
114 n = n + (t & 1)
115 t = t >> 1
116 }
117 return n
118}
119
120func nx_lc_zeros(lc: *LinearCounter) -> i64 {
121 let bytes: i64 = lc.m_bits / 8
122 var set: i64 = 0
123 var i: i64 = 0
124 while i < bytes {
125 set = set + nx_lc_popcount_byte(lc.bits[i])
126 i = i + 1
127 }
128 return lc.m_bits - set
129}
130
131// === ln estimator ================================================
132//
133// Approximate -ln(zeros / m) via tabulation indexed by integer
134// percentage = (zeros * 100) / m. Table values are -ln(p/100) * 1e6.
135//
136// p=99: -ln(0.99) = 0.01005 -> 10050 PPM
137// p=90: -ln(0.90) = 0.10536 -> 105360 PPM
138// p=70: -ln(0.70) = 0.35667 -> 356670 PPM
139// p=50: -ln(0.50) = 0.69315 -> 693150 PPM
140// p=30: -ln(0.30) = 1.20397 -> 1203970 PPM
141// p=10: -ln(0.10) = 2.30259 -> 2302590 PPM
142// p=01: -ln(0.01) = 4.60517 -> 4605170 PPM
143// p=0.1: -ln(0.001)= 6.90776 -> 6907760 PPM
144//
145// For finer resolution we'd use a larger table. Coarse buckets are
146// fine: estimation error ~ 1% per bucket transition.
147
148func nx_lc_neg_ln_ppm(zeros_x_100: i64, m: i64) -> i64 {
149 let p: i64 = zeros_x_100 / m
150 if p >= 99 { return 10050 }
151 if p >= 95 { return 51290 }
152 if p >= 90 { return 105360 }
153 if p >= 80 { return 223140 }
154 if p >= 70 { return 356670 }
155 if p >= 60 { return 510830 }
156 if p >= 50 { return 693150 }
157 if p >= 40 { return 916290 }
158 if p >= 30 { return 1203970 }
159 if p >= 20 { return 1609440 }
160 if p >= 10 { return 2302590 }
161 if p >= 5 { return 2995730 }
162 if p >= 1 { return 4605170 }
163 return 6907760
164}
165
166// === estimate ====================================================
167//
168// estimate = -m * ln(zeros / m)
169//
170// If zeros == 0: bitmap saturated, estimate is much greater than m;
171// we return m as a conservative ceiling.
172
173func nx_lc_estimate(lc: *LinearCounter) -> i64 {
174 let zeros: i64 = nx_lc_zeros(lc)
175 if zeros == 0 { return lc.m_bits }
176 if zeros == lc.m_bits { return 0 }
177 let ln_ppm: i64 = nx_lc_neg_ln_ppm(zeros * 100, lc.m_bits)
178 // estimate = (m * ln_ppm) / 1e6
179 return (lc.m_bits * ln_ppm) / 1000000
180}
181
182// === typed envelope ==============================================
183//
184// Whang 1990 standard error: sqrt(e^t - t - 1) / t where t = n/m.
185// Tabulated by load class for the integer path.
186
187func nx_lc_stddev_rel_ppb(load_pct: i64) -> i64 {
188 if load_pct <= 1 { return 710000000 } // very small N, high relative variance
189 if load_pct <= 5 { return 226000000 }
190 if load_pct <= 10 { return 159000000 }
191 if load_pct <= 25 { return 95000000 }
192 if load_pct <= 50 { return 65000000 }
193 if load_pct <= 75 { return 53000000 }
194 if load_pct <= 90 { return 58000000 }
195 if load_pct <= 100 { return 80000000 }
196 return 300000000
197}
198
199func nx_lc_query(lc: *LinearCounter) -> *ApproxI64 {
200 let est: i64 = nx_lc_estimate(lc)
201 var load_pct: i64 = 0
202 if lc.m_bits > 0 { load_pct = (est * 100) / lc.m_bits }
203 return nx_approx_new(est, NX_ENV_REL_STDDEV,
204 nx_lc_stddev_rel_ppb(load_pct),
205 682700000,
206 NX_MATURITY_REFERENCE_IMPL,
207 NX_ADV_HONEST)
208}
209
210// === merge =======================================================
211//
212// Bit-wise OR. Both must have matching m and seed.
213
214func nx_lc_merge(a: *LinearCounter, b: *LinearCounter) -> *LinearCounter {
215 if a.m_bits != b.m_bits { return 0 as *LinearCounter }
216 if a.seed != b.seed { return 0 as *LinearCounter }
217 let out: *LinearCounter = nx_lc_alloc(a.m_bits, a.seed)
218 let bytes: i64 = a.m_bits / 8
219 var i: i64 = 0
220 while i < bytes {
221 out.bits[i] = a.bits[i] | b.bits[i]
222 i = i + 1
223 }
224 return out
225}
226
227func nx_lc_memory_bytes(lc: *LinearCounter) -> i64 {
228 return 40 + lc.m_bits / 8
229}