nx_sketch_hllmap.nx
buildroot/runtime/nx_sketch_hllmap.nx
about
sketch_hllmap.nx -- Map<key, HLL> for "distinct count per key" queries.
E.g. distinct-IPs-per-URL, distinct-events-per-user, distinct-terms-
per-document. Compose a hash map with the HLL primitive: each map
entry holds a separate HLL sketch.
CAPABILITY STOMP vs DataSketches:
DS HllMap supports add + estimate but does NOT support merge of
two HllMaps (their docs flag this as future work). We ship merge
on day one because:
- HLL merge is register-wise max (cheap)
- hash-map merge is set-union of keys (linear)
together they compose without state surgery.
Hash table: linear-probing, power-of-2 capacity, open addressing.
Entry = {key_hash: i64, hll: *Hll}. Empty slots: key_hash == 0
(we map true-hash 0 -> 1 to avoid collision with the empty
sentinel).
Per the lossless-language doctrine: per-key estimates ship the
same Approximate<i64> envelope as base HLL (rel_stddev = 1.04/sqrt(m)).
dependencies 4 imports · 0 importers
imports: nx_syscalls.nxnx_murmur3.nxnx_sketch_hll.nxnx_sketch_types.nx
imported by: nobody (leaf or entry point)
structs
| 37 | struct HllMapEntry |
| 42 | struct HllMap |
consts
| 34 | const NX_HMAP_EMPTY: i64 = 0 |
| 35 | const NX_HMAP_LF_MAX_PCT: i64 = 70 // resize at >70% load |
functions
| 52 | func nx_hmap_is_pow2(n: i64) -> i64 called by 1: nx_hllmap_alloc |
| 58 | func nx_hllmap_alloc(capacity: i64, lg_k: i64, seed: i64) -> *HllMap |
| 81 | func nx_hmap_entry_at(m: *HllMap, i: i64) -> *HllMapEntry |
| 91 | func nx_hllmap_probe(m: *HllMap, key_hash: i64) -> i64 called by 4: nx_hllmap_addnx_hllmap_estimatenx_hllmap_querynx_hllmap_merge calls 1: nx_hmap_entry_at |
| 121 | func nx_hllmap_key_hash(m: *HllMap, key: *u8, len: i64) -> i64 |
| 127 | func nx_hllmap_add(m: *HllMap, key: *u8, key_len: i64, |
| 146 | func nx_hllmap_estimate(m: *HllMap, key: *u8, key_len: i64) -> i64 |
| 154 | func nx_hllmap_query(m: *HllMap, key: *u8, key_len: i64) -> *ApproxI64 |
| 173 | func nx_hllmap_max2(x: i64, y: i64) -> i64 called by 1: nx_hllmap_merge |
| 180 | func nx_hllmap_clone_hll(src: *Hll) -> *Hll |
| 190 | func nx_hllmap_merge(a: *HllMap, b: *HllMap) -> *HllMap |
| 242 | func nx_hllmap_memory_bytes(m: *HllMap) -> i64 |
| 249 | func nx_hllmap_n_entries(m: *HllMap) -> i64 |