nx_sketch_hllmap.nx source
↩ module page · 251 lines · 8422 B
1// sketch_hllmap.nx -- Map<key, HLL> for "distinct count per key" queries.
2//
3// E.g. distinct-IPs-per-URL, distinct-events-per-user, distinct-terms-
4// per-document. Compose a hash map with the HLL primitive: each map
5// entry holds a separate HLL sketch.
6//
7// CAPABILITY STOMP vs DataSketches:
8// DS HllMap supports add + estimate but does NOT support merge of
9// two HllMaps (their docs flag this as future work). We ship merge
10// on day one because:
11// - HLL merge is register-wise max (cheap)
12// - hash-map merge is set-union of keys (linear)
13// together they compose without state surgery.
14//
15// Hash table: linear-probing, power-of-2 capacity, open addressing.
16// Entry = {key_hash: i64, hll: *Hll}. Empty slots: key_hash == 0
17// (we map true-hash 0 -> 1 to avoid collision with the empty
18// sentinel).
19//
20// Per the lossless-language doctrine: per-key estimates ship the
21// same Approximate<i64> envelope as base HLL (rel_stddev = 1.04/sqrt(m)).
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_HMAP_EMPTY: i64 = 0
35const NX_HMAP_LF_MAX_PCT: i64 = 70 // resize at >70% load
36
37struct HllMapEntry {
38 key_hash: i64,
39 hll: *Hll,
40}
41
42struct HllMap {
43 entries: *HllMapEntry,
44 capacity: i64, // power of 2
45 n_entries: i64,
46 lg_k: i64,
47 seed: i64,
48}
49
50// === construction =================================================
51
52func nx_hmap_is_pow2(n: i64) -> i64 {
53 if n < 4 { return 0 }
54 if (n & (n - 1)) != 0 { return 0 }
55 return 1
56}
57
58func nx_hllmap_alloc(capacity: i64, lg_k: i64, seed: i64) -> *HllMap {
59 if nx_hmap_is_pow2(capacity) != 1 { return 0 as *HllMap }
60 if lg_k < 4 { return 0 as *HllMap }
61 if lg_k > 10 { return 0 as *HllMap }
62 let raw: *u8 = sys_mmap(48)
63 let m: *HllMap = raw as *HllMap
64 let ent_bytes: i64 = capacity * 16
65 let ent_raw: *u8 = sys_mmap(ent_bytes)
66 m.entries = ent_raw as *HllMapEntry
67 var i: i64 = 0
68 while i < ent_bytes {
69 ent_raw[i] = 0 // zero-init: key_hash=0 (empty), hll=NULL
70 i = i + 1
71 }
72 m.capacity = capacity
73 m.n_entries = 0
74 m.lg_k = lg_k
75 m.seed = seed
76 return m
77}
78
79// === entry access =================================================
80
81func nx_hmap_entry_at(m: *HllMap, i: i64) -> *HllMapEntry {
82 return (m.entries as i64 + i * 16) as *HllMapEntry
83}
84
85// === probe for a key's slot =======================================
86//
87// Returns the entry index (0..capacity-1) holding `key_hash`, or the
88// first empty slot we'd insert into. Always finds a target because
89// load factor capped at 70%.
90
91func nx_hllmap_probe(m: *HllMap, key_hash: i64) -> i64 {
92 let mask: i64 = m.capacity - 1
93 var i: i64 = key_hash & mask
94 var found_idx: i64 = -1
95 var done: i64 = 0
96 while done == 0 {
97 let e: *HllMapEntry = nx_hmap_entry_at(m, i)
98 if e.key_hash == NX_HMAP_EMPTY {
99 found_idx = i
100 done = 1
101 }
102 if done == 0 {
103 if e.key_hash == key_hash {
104 found_idx = i
105 done = 1
106 }
107 }
108 if done == 0 {
109 i = (i + 1) & mask
110 }
111 }
112 return found_idx
113}
114
115// === insert / lookup ==============================================
116//
117// nx_hllmap_add finds-or-creates the per-key HLL and adds the value
118// to it. Returns 0 on success, -1 if map is too full (no expansion
119// in v1 -- caller sized capacity appropriately).
120
121func nx_hllmap_key_hash(m: *HllMap, key: *u8, len: i64) -> i64 {
122 let h: i64 = murmur3_32(m.seed, key, len) & 0xFFFFFFFF
123 if h == NX_HMAP_EMPTY { return 1 }
124 return h
125}
126
127func nx_hllmap_add(m: *HllMap, key: *u8, key_len: i64,
128 value: *u8, value_len: i64) -> i64 {
129 // Refuse insert if at load limit AND no existing entry.
130 let key_hash: i64 = nx_hllmap_key_hash(m, key, key_len)
131 let idx: i64 = nx_hllmap_probe(m, key_hash)
132 let e: *HllMapEntry = nx_hmap_entry_at(m, idx)
133 if e.key_hash == NX_HMAP_EMPTY {
134 // New entry.
135 let load_after: i64 = ((m.n_entries + 1) * 100) / m.capacity
136 if load_after > NX_HMAP_LF_MAX_PCT { return -1 }
137 e.key_hash = key_hash
138 e.hll = nx_hll_alloc(m.lg_k, m.seed)
139 if e.hll == (0 as *Hll) { return -1 }
140 m.n_entries = m.n_entries + 1
141 }
142 nx_hll_add(e.hll, value, value_len)
143 return 0
144}
145
146func nx_hllmap_estimate(m: *HllMap, key: *u8, key_len: i64) -> i64 {
147 let key_hash: i64 = nx_hllmap_key_hash(m, key, key_len)
148 let idx: i64 = nx_hllmap_probe(m, key_hash)
149 let e: *HllMapEntry = nx_hmap_entry_at(m, idx)
150 if e.key_hash == NX_HMAP_EMPTY { return 0 }
151 return nx_hll_estimate(e.hll)
152}
153
154func nx_hllmap_query(m: *HllMap, key: *u8, key_len: i64) -> *ApproxI64 {
155 let key_hash: i64 = nx_hllmap_key_hash(m, key, key_len)
156 let idx: i64 = nx_hllmap_probe(m, key_hash)
157 let e: *HllMapEntry = nx_hmap_entry_at(m, idx)
158 if e.key_hash == NX_HMAP_EMPTY {
159 return nx_approx_new(0, NX_ENV_ABS, 0, 1000000000,
160 NX_MATURITY_REFERENCE_IMPL, NX_ADV_HONEST)
161 }
162 return nx_hll_query(e.hll)
163}
164
165// === merge ========================================================
166//
167// new_map = HllMapWithCapacity max(a.cap, b.cap)
168// for each entry in a: copy hll over (set entry, install pointer to copy)
169// for each entry in b: probe; if exists, merge into existing; else copy
170//
171// Requires a.lg_k == b.lg_k and a.seed == b.seed.
172
173func nx_hllmap_max2(x: i64, y: i64) -> i64 {
174 if x > y { return x }
175 return y
176}
177
178// Copy an HLL into a freshly-allocated one (for the case where we
179// own the result lifetime).
180func nx_hllmap_clone_hll(src: *Hll) -> *Hll {
181 let out: *Hll = nx_hll_alloc(src.lg_k, src.seed)
182 var i: i64 = 0
183 while i < src.m {
184 out.regs[i] = src.regs[i]
185 i = i + 1
186 }
187 return out
188}
189
190func nx_hllmap_merge(a: *HllMap, b: *HllMap) -> *HllMap {
191 if a.lg_k != b.lg_k { return 0 as *HllMap }
192 if a.seed != b.seed { return 0 as *HllMap }
193 let cap: i64 = nx_hllmap_max2(a.capacity, b.capacity)
194 let out: *HllMap = nx_hllmap_alloc(cap, a.lg_k, a.seed)
195 // Copy a's entries.
196 var i: i64 = 0
197 while i < a.capacity {
198 let ea: *HllMapEntry = nx_hmap_entry_at(a, i)
199 if ea.key_hash != NX_HMAP_EMPTY {
200 let idx_o: i64 = nx_hllmap_probe(out, ea.key_hash)
201 let eo: *HllMapEntry = nx_hmap_entry_at(out, idx_o)
202 eo.key_hash = ea.key_hash
203 eo.hll = nx_hllmap_clone_hll(ea.hll)
204 out.n_entries = out.n_entries + 1
205 }
206 i = i + 1
207 }
208 // Merge b's entries.
209 i = 0
210 while i < b.capacity {
211 let eb: *HllMapEntry = nx_hmap_entry_at(b, i)
212 if eb.key_hash != NX_HMAP_EMPTY {
213 let idx_o: i64 = nx_hllmap_probe(out, eb.key_hash)
214 let eo: *HllMapEntry = nx_hmap_entry_at(out, idx_o)
215 var just_installed: i64 = 0
216 if eo.key_hash == NX_HMAP_EMPTY {
217 // Key wasn't in a; install fresh clone of eb's HLL.
218 eo.key_hash = eb.key_hash
219 eo.hll = nx_hllmap_clone_hll(eb.hll)
220 out.n_entries = out.n_entries + 1
221 just_installed = 1
222 }
223 if just_installed == 0 {
224 // Pre-existing from a's pass -- merge eb's HLL into
225 // eo's HLL in-place via register-wise max.
226 var r: i64 = 0
227 while r < eo.hll.m {
228 let va: i64 = eo.hll.regs[r]
229 let vb: i64 = eb.hll.regs[r]
230 if vb > va { eo.hll.regs[r] = vb }
231 r = r + 1
232 }
233 }
234 }
235 i = i + 1
236 }
237 return out
238}
239
240// === introspection ================================================
241
242func nx_hllmap_memory_bytes(m: *HllMap) -> i64 {
243 // 48 (HllMap) + cap*16 (entries) + n_entries * (24 + m_bytes) (HLLs).
244 // m_bytes = 1 << lg_k for HLL_8.
245 let m_per_hll: i64 = 1 << m.lg_k
246 return 48 + m.capacity * 16 + m.n_entries * (24 + m_per_hll)
247}
248
249func nx_hllmap_n_entries(m: *HllMap) -> i64 {
250 return m.n_entries
251}