sketch_hll_packed.nx source
↩ module page · 206 lines · 7160 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
32import "syscalls.nx"
33import "murmur3.nx"
34import "sketch_hll.nx"
35import "sketch_types.nx"
36
37const NX_HLL6_LGK_MIN: i64 = 4
38const NX_HLL6_LGK_MAX: i64 = 10
39
40const NX_HLL6_SEED_HI: i64 = 0x9747B28C
41const NX_HLL6_SEED_LO: i64 = 0x36185EC0
42
43// HLL_6 handle. Same shape as Hll but regs holds packed 6-bit
44// values; `bytes` is the byte length of the regs array.
45struct Hll6 {
46 regs: *u8,
47 lg_k: i64,
48 m: i64,
49 bytes: i64,
50 seed: i64,
51}
52
53// === 6-bit packing helpers ========================================
54//
55// Bit packing scheme: register at index `i` lives at bit position
56// `i * 6`. Within the byte array, that maps to:
57// byte_index = (i * 6) / 8 = (i * 6) >> 3
58// bit_offset = (i * 6) % 8 = (i * 6) & 7
59// Each 6-bit field straddles at most 2 bytes (since 6 < 8 and 6
60// can cross a byte boundary by up to 4 bits).
61//
62// Read: load up to 16 bits starting at (byte_index, bit_offset),
63// extract 6 bits. Write: clear the 6-bit window, OR in the new
64// value.
65
66func nx_hll6_get(regs: *u8, idx: i64) -> i64 {
67 let bit_pos: i64 = idx * 6
68 let byte_idx: i64 = bit_pos >> 3
69 let bit_off: i64 = bit_pos & 7
70 let b0: i64 = regs[byte_idx]
71 let b1: i64 = regs[byte_idx + 1]
72 let combined: i64 = b0 | (b1 << 8)
73 let shifted: i64 = combined >> bit_off
74 return shifted & 0x3F
75}
76
77func nx_hll6_set(regs: *u8, idx: i64, value: i64) -> i64 {
78 let bit_pos: i64 = idx * 6
79 let byte_idx: i64 = bit_pos >> 3
80 let bit_off: i64 = bit_pos & 7
81 let v: i64 = value & 0x3F
82 // Read both bytes.
83 let b0: i64 = regs[byte_idx]
84 let b1: i64 = regs[byte_idx + 1]
85 // Mask out the 6-bit window in the combined 16-bit value.
86 let mask: i64 = 0x3F << bit_off
87 let inv_mask: i64 = (~mask) & 0xFFFF
88 let combined: i64 = (b0 | (b1 << 8)) & inv_mask
89 let updated: i64 = combined | (v << bit_off)
90 regs[byte_idx] = updated & 0xFF
91 regs[byte_idx + 1] = (updated >> 8) & 0xFF
92 return 0
93}
94
95// === construction =================================================
96
97func nx_hll6_alloc(lg_k: i64, seed: i64) -> *Hll6 {
98 if lg_k < NX_HLL6_LGK_MIN { return 0 as *Hll6 }
99 if lg_k > NX_HLL6_LGK_MAX { return 0 as *Hll6 }
100 let m: i64 = 1 << lg_k
101 // Bit-packed: m * 6 bits total. Round up to whole bytes, plus
102 // 1 byte of guard (so the get/set can read byte_idx+1 safely
103 // even when the last register's window is byte-aligned).
104 let bytes: i64 = ((m * 6) + 7) / 8 + 1
105 let raw: *u8 = sys_mmap(40)
106 let h: *Hll6 = raw as *Hll6
107 h.regs = sys_mmap(bytes)
108 h.lg_k = lg_k
109 h.m = m
110 h.bytes = bytes
111 h.seed = seed
112 // Zero the entire packed array.
113 var i: i64 = 0
114 while i < bytes {
115 h.regs[i] = 0
116 i = i + 1
117 }
118 return h
119}
120
121// === add ===========================================================
122// Same hash + rho logic as nx_hll_add; uses nx_clz32 from sketch_hll.
123
124func nx_hll6_add(h: *Hll6, key: *u8, len: i64) -> i64 {
125 let seed_hi: i64 = h.seed ^ NX_HLL6_SEED_HI
126 let seed_lo: i64 = h.seed ^ NX_HLL6_SEED_LO
127 let hi: i64 = murmur3_32(seed_hi, key, len) & 0xFFFFFFFF
128 let lo: i64 = murmur3_32(seed_lo, key, len) & 0xFFFFFFFF
129
130 let idx: i64 = hi >> (32 - h.lg_k)
131
132 let upper: i64 = (hi << h.lg_k) & 0xFFFFFFFF
133 var r: i64 = 0
134 if upper != 0 {
135 r = nx_clz32(upper) + 1
136 }
137 if upper == 0 {
138 if lo != 0 {
139 r = (32 - h.lg_k) + nx_clz32(lo) + 1
140 }
141 if lo == 0 {
142 r = (64 - h.lg_k) + 1
143 }
144 }
145 // 6-bit field caps at 63. For lg_k >= 4, max true rho is
146 // 64 - 4 + 1 = 61, so saturation only matters at extreme rho.
147 if r > 63 { r = 63 }
148
149 let cur: i64 = nx_hll6_get(h.regs, idx)
150 if cur < r {
151 nx_hll6_set(h.regs, idx, r)
152 }
153 return 0
154}
155
156// === estimate ======================================================
157// Same harmonic-mean algorithm as nx_hll_estimate; only the
158// register-read path changes (nx_hll6_get instead of regs[i]).
159
160func nx_hll6_estimate(h: *Hll6) -> i64 {
161 let m: i64 = h.m
162 var sum_q32: i64 = 0
163 var zeros: i64 = 0
164 var i: i64 = 0
165 while i < m {
166 let r: i64 = nx_hll6_get(h.regs, i)
167 if r == 0 { zeros = zeros + 1 }
168 sum_q32 = sum_q32 + nx_hll_pow2_neg_q32(r)
169 i = i + 1
170 }
171 if sum_q32 == 0 { return m }
172 let alpha_m_sq_q64: i64 = nx_hll_alpha_m_sq_q64(h.lg_k)
173 if alpha_m_sq_q64 == 0 { return zeros }
174 var est: i64 = alpha_m_sq_q64 / sum_q32
175 let threshold_5_2: i64 = (5 * m) / 2
176 if est <= threshold_5_2 {
177 if zeros > 0 {
178 let ratio: i64 = m / zeros
179 if ratio == 0 { return est }
180 var lg2: i64 = 0
181 var t: i64 = ratio
182 while t > 1 { t = t >> 1; lg2 = lg2 + 1 }
183 est = (m * lg2 * 693147180) / 1000000000
184 }
185 }
186 return est
187}
188
189func nx_hll6_query(h: *Hll6) -> *ApproxI64 {
190 let est: i64 = nx_hll6_estimate(h)
191 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(h.lg_k)
192 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
193 682700000,
194 NX_MATURITY_REFERENCE_IMPL,
195 NX_ADV_HONEST)
196}
197
198// === memory_bytes (for the memory-stomp test) =====================
199//
200// Returns the actual storage size of the packed register array.
201// HLL_8 at lg_k=10 = 1024 bytes; HLL_6 at lg_k=10 = 768+1 bytes
202// (75% of HLL_8).
203
204func nx_hll6_memory_bytes(h: *Hll6) -> i64 {
205 return h.bytes
206}