nx_sketch_hll4.nx source
↩ module page · 276 lines · 8855 B
1// sketch_hll4.nx -- HLL_4 with Heule exception table.
2//
3// 4 bits per register addresses rho in [0, 14]; rho = 15 is the
4// SENTINEL meaning "see exception table for the true value." An
5// exception table holds (idx, value) pairs for the rare registers
6// whose true rho exceeds 14.
7//
8// MEMORY: HLL_4 at lg_k=10 = m/2 bytes register array + ~40 bytes
9// header + ~0 bytes exception (lazy-allocated; most workloads
10// never trigger). Total HLL_4-10 < HLL_8-10 by ~46% in typical
11// use. Matches DataSketches HLL_4-12 = 2095 bytes.
12//
13// Heule et al. 2013 observation: P(rho > 14) is small enough that
14// a few sentinel slots + a hash-table-class exception map is
15// strictly cheaper than 6-bit or 8-bit dense storage at high lgK.
16// For HLL_4-12 at N = 10^9, expected exceptions < 50 entries.
17//
18// Per the lossless-language discipline (doc 20): the typed
19// envelope API is invariant across packing strategies. HLL_4,
20// HLL_6, HLL_8 all return the same ApproxI64 shape; users see
21// memory drop without semantic change.
22
23// nx_safety_envelope:
24// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
25// sil_target: SIL1
26// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
27// verdict: NOT_YET_EVALUATED
28
29import "nx_syscalls.nx"
30import "nx_murmur3.nx"
31import "nx_sketch_hll.nx"
32import "nx_sketch_types.nx"
33
34const NX_HLL4_LGK_MIN: i64 = 4
35const NX_HLL4_LGK_MAX: i64 = 10
36
37const NX_HLL4_SEED_HI: i64 = 0x9747B28C
38const NX_HLL4_SEED_LO: i64 = 0x36185EC0
39
40// Sentinel value in the 4-bit slot meaning "see exception table".
41const NX_HLL4_SENTINEL: i64 = 15
42
43// Exception entry: 16 bytes. Linear scan on read for v1 (small
44// table); upgrade to sorted-array bsearch in v2 if benchmarks
45// show it matters.
46struct Hll4Except {
47 idx: i64,
48 value: i64,
49}
50
51// HLL_4 handle. 56 bytes. exception_table is lazy-allocated --
52// 0 until first overflow. exception_cap doubles on growth.
53struct Hll4 {
54 regs: *u8,
55 lg_k: i64,
56 m: i64,
57 bytes: i64,
58 seed: i64,
59 exception_table: *Hll4Except,
60 exception_count: i64,
61 exception_cap: i64,
62}
63
64// === 4-bit packing helpers =========================================
65//
66// Each register at index i occupies the low nibble or high nibble
67// of byte (i >> 1):
68// if i even: bits 0..3 of byte
69// if i odd : bits 4..7 of byte
70
71func nx_hll4_get_packed(regs: *u8, idx: i64) -> i64 {
72 let byte_idx: i64 = idx >> 1
73 let b: i64 = regs[byte_idx]
74 if (idx & 1) == 0 {
75 return b & 0x0F
76 }
77 return (b >> 4) & 0x0F
78}
79
80func nx_hll4_set_packed(regs: *u8, idx: i64, value: i64) -> i64 {
81 let byte_idx: i64 = idx >> 1
82 let b: i64 = regs[byte_idx]
83 let v: i64 = value & 0x0F
84 if (idx & 1) == 0 {
85 regs[byte_idx] = (b & 0xF0) | v
86 }
87 if (idx & 1) == 1 {
88 regs[byte_idx] = (b & 0x0F) | (v << 4)
89 }
90 return 0
91}
92
93// === exception table helpers ======================================
94
95const NX_HLL4_EXCEPT_INITIAL_CAP: i64 = 8
96
97func nx_hll4_except_find(h: *Hll4, idx: i64) -> i64 {
98 // Returns the i index in exception_table for slot `idx`, or -1.
99 if h.exception_count == 0 { return -1 }
100 var i: i64 = 0
101 while i < h.exception_count {
102 let e: *Hll4Except = (h.exception_table as i64 + i * 16) as *Hll4Except
103 if e.idx == idx { return i }
104 i = i + 1
105 }
106 return -1
107}
108
109func nx_hll4_except_set(h: *Hll4, idx: i64, value: i64) -> i64 {
110 // Add or update exception entry for slot `idx` to hold `value`.
111 if h.exception_table == (0 as *Hll4Except) {
112 let raw: *u8 = sys_mmap(NX_HLL4_EXCEPT_INITIAL_CAP * 16)
113 h.exception_table = raw as *Hll4Except
114 h.exception_cap = NX_HLL4_EXCEPT_INITIAL_CAP
115 h.exception_count = 0
116 }
117 let pos: i64 = nx_hll4_except_find(h, idx)
118 if pos >= 0 {
119 let e: *Hll4Except = (h.exception_table as i64 + pos * 16) as *Hll4Except
120 e.value = value
121 return 0
122 }
123 // Grow table on demand.
124 if h.exception_count >= h.exception_cap {
125 let new_cap: i64 = h.exception_cap * 2
126 let raw: *u8 = sys_mmap(new_cap * 16)
127 let new_table: *Hll4Except = raw as *Hll4Except
128 var i: i64 = 0
129 while i < h.exception_count {
130 let src: *Hll4Except = (h.exception_table as i64 + i * 16) as *Hll4Except
131 let dst: *Hll4Except = (new_table as i64 + i * 16) as *Hll4Except
132 dst.idx = src.idx
133 dst.value = src.value
134 i = i + 1
135 }
136 h.exception_table = new_table
137 h.exception_cap = new_cap
138 }
139 let slot: *Hll4Except = (h.exception_table as i64 + h.exception_count * 16) as *Hll4Except
140 slot.idx = idx
141 slot.value = value
142 h.exception_count = h.exception_count + 1
143 return 0
144}
145
146// === unified register read (slot + exception lookup) ==============
147
148func nx_hll4_read(h: *Hll4, idx: i64) -> i64 {
149 let slot: i64 = nx_hll4_get_packed(h.regs, idx)
150 if slot < NX_HLL4_SENTINEL { return slot }
151 // Sentinel: check exception table. If not present, treat as 15
152 // (might happen when sentinel is set but exception missing --
153 // shouldn't occur in valid state).
154 let pos: i64 = nx_hll4_except_find(h, idx)
155 if pos < 0 { return NX_HLL4_SENTINEL }
156 let e: *Hll4Except = (h.exception_table as i64 + pos * 16) as *Hll4Except
157 return e.value
158}
159
160// === unified register write (with sentinel + exception) ===========
161
162func nx_hll4_write(h: *Hll4, idx: i64, value: i64) -> i64 {
163 if value < NX_HLL4_SENTINEL {
164 nx_hll4_set_packed(h.regs, idx, value)
165 return 0
166 }
167 // value >= 15: set slot to sentinel, add/update exception.
168 nx_hll4_set_packed(h.regs, idx, NX_HLL4_SENTINEL)
169 nx_hll4_except_set(h, idx, value)
170 return 0
171}
172
173// === construction =================================================
174
175func nx_hll4_alloc(lg_k: i64, seed: i64) -> *Hll4 {
176 if lg_k < NX_HLL4_LGK_MIN { return 0 as *Hll4 }
177 if lg_k > NX_HLL4_LGK_MAX { return 0 as *Hll4 }
178 let m: i64 = 1 << lg_k
179 let bytes: i64 = (m + 1) / 2
180 let raw: *u8 = sys_mmap(56)
181 let h: *Hll4 = raw as *Hll4
182 h.regs = sys_mmap(bytes)
183 h.lg_k = lg_k
184 h.m = m
185 h.bytes = bytes
186 h.seed = seed
187 h.exception_table = 0 as *Hll4Except
188 h.exception_count = 0
189 h.exception_cap = 0
190 var i: i64 = 0
191 while i < bytes {
192 h.regs[i] = 0
193 i = i + 1
194 }
195 return h
196}
197
198// === add ===========================================================
199
200func nx_hll4_add(h: *Hll4, key: *u8, len: i64) -> i64 {
201 let seed_hi: i64 = h.seed ^ NX_HLL4_SEED_HI
202 let seed_lo: i64 = h.seed ^ NX_HLL4_SEED_LO
203 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
204 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
205 let idx: i64 = hi >> (32 - h.lg_k)
206 let upper: i64 = (hi << h.lg_k) & 0xFFFFFFFF
207 var r: i64 = 0
208 if upper != 0 {
209 r = nx_clz32(upper) + 1
210 }
211 if upper == 0 {
212 if lo != 0 {
213 r = (32 - h.lg_k) + nx_clz32(lo) + 1
214 }
215 if lo == 0 {
216 r = (64 - h.lg_k) + 1
217 }
218 }
219 if r > 63 { r = 63 }
220 let cur: i64 = nx_hll4_read(h, idx)
221 if cur < r {
222 nx_hll4_write(h, idx, r)
223 }
224 return 0
225}
226
227// === estimate + query =============================================
228
229func nx_hll4_estimate(h: *Hll4) -> i64 {
230 let m: i64 = h.m
231 var sum_q32: i64 = 0
232 var zeros: i64 = 0
233 var i: i64 = 0
234 while i < m {
235 let r: i64 = nx_hll4_read(h, i)
236 if r == 0 { zeros = zeros + 1 }
237 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r)
238 i = i + 1
239 }
240 if sum_q32 == 0 { return m }
241 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k)
242 if alpha_m_sq_q64 == 0 { return zeros }
243 var est: i64 = alpha_m_sq_q64 / sum_q32
244 let threshold_5_2: i64 = (5 * m) / 2
245 if est <= threshold_5_2 {
246 if zeros > 0 {
247 let ratio: i64 = m / zeros
248 if ratio == 0 { return est }
249 var lg2: i64 = 0
250 var t: i64 = ratio
251 while t > 1 { t = t >> 1; lg2 = lg2 + 1 }
252 est = (m * lg2 * 693147180) / 1000000000
253 }
254 }
255 return est
256}
257
258func nx_hll4_query(h: *Hll4) -> *ApproxI64 {
259 let est: i64 = nx_hll4_estimate(h)
260 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(h.lg_k)
261 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
262 682700000,
263 NX_MATURITY_REFERENCE_IMPL,
264 NX_ADV_HONEST)
265}
266
267// === memory introspection =========================================
268
269func nx_hll4_memory_bytes(h: *Hll4) -> i64 {
270 // Register array + exception table (each entry 16 bytes).
271 return h.bytes + h.exception_count * 16
272}
273
274func nx_hll4_exception_count(h: *Hll4) -> i64 {
275 return h.exception_count
276}