nx_sketch_hll_packed.nx source
↩ module page · 212 lines · 7217 B
1// sketch_hll_packed.nx -- 4-bit and 6-bit packed-register HLL.
2//
3// Same algorithm as runtime/sketch_hll.nx; different register
4// storage layout. Saves 50% (HLL_4) or 25% (HLL_6) memory at the
5// cost of bit-twiddling on every register read/write. Tradeoff
6// is the same one DataSketches makes with HLL_4-12 = 2095 bytes
7// vs HLL_8-12 = 4096 bytes; we match their memory footprint while
8// preserving every NishiLang substrate guarantee.
9//
10// rho range: lg_k=10 -> max rho = 64 - 10 + 1 = 55, fits in 6 bits;
11// but 4 bits only addresses [0, 15]. For HLL_4 we use the standard
12// HEULE encoding: a 4-bit base value (0..15) plus a per-bucket
13// EXCEPTION table for buckets whose true rho exceeds 15. In
14// practice exceptions are rare (P[rho > 15] = 1/2^15 = 3e-5) so
15// the exception table stays small. For HLL_6 we have plenty of
16// headroom (max 63), so no exception table is needed.
17//
18// FIRST CUT: ship HLL_6 (simpler -- no exception table) to land
19// the memory stomp. HLL_4 with the exception-table machinery
20// follows in a queued commit.
21//
22// MEMORY: HLL_6-12 (lg_k=12) = 4096 * 6 / 8 = 3072 bytes vs HLL_8
23// 4096 bytes (25% reduction). HLL_6-10 = 1024 * 6 / 8 = 768 bytes
24// vs HLL_8 1024 bytes.
25//
26// Per the lossless-language discipline (doc 20): packing the bits
27// doesn't change the typed envelope -- query returns the same
28// ApproxI64 shape as nx_hll_query. The memory footprint reduction
29// is a substrate-internal optimization, invisible at the API
30// surface.
31
32// nx_safety_envelope:
33// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
34// sil_target: SIL1
35// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
36// verdict: NOT_YET_EVALUATED
37
38import "nx_syscalls.nx"
39import "nx_murmur3.nx"
40import "nx_sketch_hll.nx"
41import "nx_sketch_types.nx"
42
43const NX_HLL6_LGK_MIN: i64 = 4
44const NX_HLL6_LGK_MAX: i64 = 10
45
46const NX_HLL6_SEED_HI: i64 = 0x9747B28C
47const NX_HLL6_SEED_LO: i64 = 0x36185EC0
48
49// HLL_6 handle. Same shape as Hll but regs holds packed 6-bit
50// values; `bytes` is the byte length of the regs array.
51struct Hll6 {
52 regs: *u8,
53 lg_k: i64,
54 m: i64,
55 bytes: i64,
56 seed: i64,
57}
58
59// === 6-bit packing helpers ========================================
60//
61// Bit packing scheme: register at index `i` lives at bit position
62// `i * 6`. Within the byte array, that maps to:
63// byte_index = (i * 6) / 8 = (i * 6) >> 3
64// bit_offset = (i * 6) % 8 = (i * 6) & 7
65// Each 6-bit field straddles at most 2 bytes (since 6 < 8 and 6
66// can cross a byte boundary by up to 4 bits).
67//
68// Read: load up to 16 bits starting at (byte_index, bit_offset),
69// extract 6 bits. Write: clear the 6-bit window, OR in the new
70// value.
71
72func nx_hll6_get(regs: *u8, idx: i64) -> i64 {
73 let bit_pos: i64 = idx * 6
74 let byte_idx: i64 = bit_pos >> 3
75 let bit_off: i64 = bit_pos & 7
76 let b0: i64 = regs[byte_idx]
77 let b1: i64 = regs[byte_idx + 1]
78 let combined: i64 = b0 | (b1 << 8)
79 let shifted: i64 = combined >> bit_off
80 return shifted & 0x3F
81}
82
83func nx_hll6_set(regs: *u8, idx: i64, value: i64) -> i64 {
84 let bit_pos: i64 = idx * 6
85 let byte_idx: i64 = bit_pos >> 3
86 let bit_off: i64 = bit_pos & 7
87 let v: i64 = value & 0x3F
88 // Read both bytes.
89 let b0: i64 = regs[byte_idx]
90 let b1: i64 = regs[byte_idx + 1]
91 // Mask out the 6-bit window in the combined 16-bit value.
92 let mask: i64 = 0x3F << bit_off
93 let inv_mask: i64 = (~mask) & 0xFFFF
94 let combined: i64 = (b0 | (b1 << 8)) & inv_mask
95 let updated: i64 = combined | (v << bit_off)
96 regs[byte_idx] = updated & 0xFF
97 regs[byte_idx + 1] = (updated >> 8) & 0xFF
98 return 0
99}
100
101// === construction =================================================
102
103func nx_hll6_alloc(lg_k: i64, seed: i64) -> *Hll6 {
104 if lg_k < NX_HLL6_LGK_MIN { return 0 as *Hll6 }
105 if lg_k > NX_HLL6_LGK_MAX { return 0 as *Hll6 }
106 let m: i64 = 1 << lg_k
107 // Bit-packed: m * 6 bits total. Round up to whole bytes, plus
108 // 1 byte of guard (so the get/set can read byte_idx+1 safely
109 // even when the last register's window is byte-aligned).
110 let bytes: i64 = ((m * 6) + 7) / 8 + 1
111 let raw: *u8 = sys_mmap(40)
112 let h: *Hll6 = raw as *Hll6
113 h.regs = sys_mmap(bytes)
114 h.lg_k = lg_k
115 h.m = m
116 h.bytes = bytes
117 h.seed = seed
118 // Zero the entire packed array.
119 var i: i64 = 0
120 while i < bytes {
121 h.regs[i] = 0
122 i = i + 1
123 }
124 return h
125}
126
127// === add ===========================================================
128// Same hash + rho logic as nx_hll_add; uses nx_clz32 from sketch_hll.
129
130func nx_hll6_add(h: *Hll6, key: *u8, len: i64) -> i64 {
131 let seed_hi: i64 = h.seed ^ NX_HLL6_SEED_HI
132 let seed_lo: i64 = h.seed ^ NX_HLL6_SEED_LO
133 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
134 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
135
136 let idx: i64 = hi >> (32 - h.lg_k)
137
138 let upper: i64 = (hi << h.lg_k) & 0xFFFFFFFF
139 var r: i64 = 0
140 if upper != 0 {
141 r = nx_clz32(upper) + 1
142 }
143 if upper == 0 {
144 if lo != 0 {
145 r = (32 - h.lg_k) + nx_clz32(lo) + 1
146 }
147 if lo == 0 {
148 r = (64 - h.lg_k) + 1
149 }
150 }
151 // 6-bit field caps at 63. For lg_k >= 4, max true rho is
152 // 64 - 4 + 1 = 61, so saturation only matters at extreme rho.
153 if r > 63 { r = 63 }
154
155 let cur: i64 = nx_hll6_get(h.regs, idx)
156 if cur < r {
157 nx_hll6_set(h.regs, idx, r)
158 }
159 return 0
160}
161
162// === estimate ======================================================
163// Same harmonic-mean algorithm as nx_hll_estimate; only the
164// register-read path changes (nx_hll6_get instead of regs[i]).
165
166func nx_hll6_estimate(h: *Hll6) -> i64 {
167 let m: i64 = h.m
168 var sum_q32: i64 = 0
169 var zeros: i64 = 0
170 var i: i64 = 0
171 while i < m {
172 let r: i64 = nx_hll6_get(h.regs, i)
173 if r == 0 { zeros = zeros + 1 }
174 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r)
175 i = i + 1
176 }
177 if sum_q32 == 0 { return m }
178 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k)
179 if alpha_m_sq_q64 == 0 { return zeros }
180 var est: i64 = alpha_m_sq_q64 / sum_q32
181 let threshold_5_2: i64 = (5 * m) / 2
182 if est <= threshold_5_2 {
183 if zeros > 0 {
184 let ratio: i64 = m / zeros
185 if ratio == 0 { return est }
186 var lg2: i64 = 0
187 var t: i64 = ratio
188 while t > 1 { t = t >> 1; lg2 = lg2 + 1 }
189 est = (m * lg2 * 693147180) / 1000000000
190 }
191 }
192 return est
193}
194
195func nx_hll6_query(h: *Hll6) -> *ApproxI64 {
196 let est: i64 = nx_hll6_estimate(h)
197 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(h.lg_k)
198 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
199 682700000,
200 NX_MATURITY_REFERENCE_IMPL,
201 NX_ADV_HONEST)
202}
203
204// === memory_bytes (for the memory-stomp test) =====================
205//
206// Returns the actual storage size of the packed register array.
207// HLL_8 at lg_k=10 = 1024 bytes; HLL_6 at lg_k=10 = 768+1 bytes
208// (75% of HLL_8).
209
210func nx_hll6_memory_bytes(h: *Hll6) -> i64 {
211 return h.bytes
212}