sketch_hll4.nx source
↩ module page · 270 lines · 8862 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
23import "syscalls.nx"
24import "murmur3.nx"
25import "sketch_hll.nx"
26import "sketch_types.nx"
27
28const NX_HLL4_LGK_MIN: i64 = 4
29const NX_HLL4_LGK_MAX: i64 = 10
30
31const NX_HLL4_SEED_HI: i64 = 0x9747B28C
32const NX_HLL4_SEED_LO: i64 = 0x36185EC0
33
34// Sentinel value in the 4-bit slot meaning "see exception table".
35const NX_HLL4_SENTINEL: i64 = 15
36
37// Exception entry: 16 bytes. Linear scan on read for v1 (small
38// table); upgrade to sorted-array bsearch in v2 if benchmarks
39// show it matters.
40struct Hll4Except {
41 idx: i64,
42 value: i64,
43}
44
45// HLL_4 handle. 56 bytes. exception_table is lazy-allocated --
46// 0 until first overflow. exception_cap doubles on growth.
47struct Hll4 {
48 regs: *u8,
49 lg_k: i64,
50 m: i64,
51 bytes: i64,
52 seed: i64,
53 exception_table: *Hll4Except,
54 exception_count: i64,
55 exception_cap: i64,
56}
57
58// === 4-bit packing helpers =========================================
59//
60// Each register at index i occupies the low nibble or high nibble
61// of byte (i >> 1):
62// if i even: bits 0..3 of byte
63// if i odd : bits 4..7 of byte
64
65func nx_hll4_get_packed(regs: *u8, idx: i64) -> i64 {
66 let byte_idx: i64 = idx >> 1
67 let b: i64 = regs[byte_idx]
68 if (idx & 1) == 0 {
69 return b & 0x0F
70 }
71 return (b >> 4) & 0x0F
72}
73
74func nx_hll4_set_packed(regs: *u8, idx: i64, value: i64) -> i64 {
75 let byte_idx: i64 = idx >> 1
76 let b: i64 = regs[byte_idx]
77 let v: i64 = value & 0x0F
78 if (idx & 1) == 0 {
79 regs[byte_idx] = (b & 0xF0) | v
80 }
81 if (idx & 1) == 1 {
82 regs[byte_idx] = (b & 0x0F) | (v << 4)
83 }
84 return 0
85}
86
87// === exception table helpers ======================================
88
89const NX_HLL4_EXCEPT_INITIAL_CAP: i64 = 8
90
91func nx_hll4_except_find(h: *Hll4, idx: i64) -> i64 {
92 // Returns the i index in exception_table for slot `idx`, or -1.
93 if h.exception_count == 0 { return -1 }
94 var i: i64 = 0
95 while i < h.exception_count {
96 let e: *Hll4Except = (h.exception_table as i64 + i * 16) as *Hll4Except
97 if e.idx == idx { return i }
98 i = i + 1
99 }
100 return -1
101}
102
103func nx_hll4_except_set(h: *Hll4, idx: i64, value: i64) -> i64 {
104 // Add or update exception entry for slot `idx` to hold `value`.
105 if h.exception_table == (0 as *Hll4Except) {
106 let raw: *u8 = sys_mmap(NX_HLL4_EXCEPT_INITIAL_CAP * 16)
107 h.exception_table = raw as *Hll4Except
108 h.exception_cap = NX_HLL4_EXCEPT_INITIAL_CAP
109 h.exception_count = 0
110 }
111 let pos: i64 = nx_hll4_except_find(h, idx)
112 if pos >= 0 {
113 let e: *Hll4Except = (h.exception_table as i64 + pos * 16) as *Hll4Except
114 e.value = value
115 return 0
116 }
117 // Grow table on demand.
118 if h.exception_count >= h.exception_cap {
119 let new_cap: i64 = h.exception_cap * 2
120 let raw: *u8 = sys_mmap(new_cap * 16)
121 let new_table: *Hll4Except = raw as *Hll4Except
122 var i: i64 = 0
123 while i < h.exception_count {
124 let src: *Hll4Except = (h.exception_table as i64 + i * 16) as *Hll4Except
125 let dst: *Hll4Except = (new_table as i64 + i * 16) as *Hll4Except
126 dst.idx = src.idx
127 dst.value = src.value
128 i = i + 1
129 }
130 h.exception_table = new_table
131 h.exception_cap = new_cap
132 }
133 let slot: *Hll4Except = (h.exception_table as i64 + h.exception_count * 16) as *Hll4Except
134 slot.idx = idx
135 slot.value = value
136 h.exception_count = h.exception_count + 1
137 return 0
138}
139
140// === unified register read (slot + exception lookup) ==============
141
142func nx_hll4_read(h: *Hll4, idx: i64) -> i64 {
143 let slot: i64 = nx_hll4_get_packed(h.regs, idx)
144 if slot < NX_HLL4_SENTINEL { return slot }
145 // Sentinel: check exception table. If not present, treat as 15
146 // (might happen when sentinel is set but exception missing --
147 // shouldn't occur in valid state).
148 let pos: i64 = nx_hll4_except_find(h, idx)
149 if pos < 0 { return NX_HLL4_SENTINEL }
150 let e: *Hll4Except = (h.exception_table as i64 + pos * 16) as *Hll4Except
151 return e.value
152}
153
154// === unified register write (with sentinel + exception) ===========
155
156func nx_hll4_write(h: *Hll4, idx: i64, value: i64) -> i64 {
157 if value < NX_HLL4_SENTINEL {
158 nx_hll4_set_packed(h.regs, idx, value)
159 return 0
160 }
161 // value >= 15: set slot to sentinel, add/update exception.
162 nx_hll4_set_packed(h.regs, idx, NX_HLL4_SENTINEL)
163 nx_hll4_except_set(h, idx, value)
164 return 0
165}
166
167// === construction =================================================
168
169func nx_hll4_alloc(lg_k: i64, seed: i64) -> *Hll4 {
170 if lg_k < NX_HLL4_LGK_MIN { return 0 as *Hll4 }
171 if lg_k > NX_HLL4_LGK_MAX { return 0 as *Hll4 }
172 let m: i64 = 1 << lg_k
173 let bytes: i64 = (m + 1) / 2
174 let raw: *u8 = sys_mmap(56)
175 let h: *Hll4 = raw as *Hll4
176 h.regs = sys_mmap(bytes)
177 h.lg_k = lg_k
178 h.m = m
179 h.bytes = bytes
180 h.seed = seed
181 h.exception_table = 0 as *Hll4Except
182 h.exception_count = 0
183 h.exception_cap = 0
184 var i: i64 = 0
185 while i < bytes {
186 h.regs[i] = 0
187 i = i + 1
188 }
189 return h
190}
191
192// === add ===========================================================
193
194func nx_hll4_add(h: *Hll4, key: *u8, len: i64) -> i64 {
195 let seed_hi: i64 = h.seed ^ NX_HLL4_SEED_HI
196 let seed_lo: i64 = h.seed ^ NX_HLL4_SEED_LO
197 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
198 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
199 let idx: i64 = hi >> (32 - h.lg_k)
200 let upper: i64 = (hi << h.lg_k) & 0xFFFFFFFF
201 var r: i64 = 0
202 if upper != 0 {
203 r = nx_clz32(upper) + 1
204 }
205 if upper == 0 {
206 if lo != 0 {
207 r = (32 - h.lg_k) + nx_clz32(lo) + 1
208 }
209 if lo == 0 {
210 r = (64 - h.lg_k) + 1
211 }
212 }
213 if r > 63 { r = 63 }
214 let cur: i64 = nx_hll4_read(h, idx)
215 if cur < r {
216 nx_hll4_write(h, idx, r)
217 }
218 return 0
219}
220
221// === estimate + query =============================================
222
223func nx_hll4_estimate(h: *Hll4) -> i64 {
224 let m: i64 = h.m
225 var sum_q32: i64 = 0
226 var zeros: i64 = 0
227 var i: i64 = 0
228 while i < m {
229 let r: i64 = nx_hll4_read(h, i)
230 if r == 0 { zeros = zeros + 1 }
231 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r)
232 i = i + 1
233 }
234 if sum_q32 == 0 { return m }
235 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k)
236 if alpha_m_sq_q64 == 0 { return zeros }
237 var est: i64 = alpha_m_sq_q64 / sum_q32
238 let threshold_5_2: i64 = (5 * m) / 2
239 if est <= threshold_5_2 {
240 if zeros > 0 {
241 let ratio: i64 = m / zeros
242 if ratio == 0 { return est }
243 var lg2: i64 = 0
244 var t: i64 = ratio
245 while t > 1 { t = t >> 1; lg2 = lg2 + 1 }
246 est = (m * lg2 * 693147180) / 1000000000
247 }
248 }
249 return est
250}
251
252func nx_hll4_query(h: *Hll4) -> *ApproxI64 {
253 let est: i64 = nx_hll4_estimate(h)
254 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(h.lg_k)
255 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
256 682700000,
257 NX_MATURITY_REFERENCE_IMPL,
258 NX_ADV_HONEST)
259}
260
261// === memory introspection =========================================
262
263func nx_hll4_memory_bytes(h: *Hll4) -> i64 {
264 // Register array + exception table (each entry 16 bytes).
265 return h.bytes + h.exception_count * 16
266}
267
268func nx_hll4_exception_count(h: *Hll4) -> i64 {
269 return h.exception_count
270}