sketch_hllmap.nx
buildroot/runtime/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 · 2 importers
imports: syscalls.nxmurmur3.nxsketch_hll.nxsketch_types.nx
imported by: sketch_hllmap_merge_capability_bench.nxsketch_hllmap_test.nx
structs
| 31 | struct HllMapEntry { |
| 36 | struct HllMap { |
consts
| 28 | const NX_HMAP_EMPTY: i64 = 0 |
| 29 | const NX_HMAP_LF_MAX_PCT: i64 = 70 // resize at >70% load |
functions
| 46 | func nx_hmap_is_pow2(n: i64) -> i64 {
called by 1: nx_hllmap_alloc |
| 52 | func nx_hllmap_alloc(capacity: i64, lg_k: i64, seed: i64) -> *HllMap { |
| 75 | func nx_hmap_entry_at(m: *HllMap, i: i64) -> *HllMapEntry { |
| 85 | 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 |
| 115 | func nx_hllmap_key_hash(m: *HllMap, key: *u8, len: i64) -> i64 { |
| 121 | func nx_hllmap_add(m: *HllMap, key: *u8, key_len: i64,
called by 2: mainmain calls 5: nx_hllmap_key_hashnx_hllmap_probenx_hmap_entry_atnx_hll_allocnx_hll_add |
| 140 | func nx_hllmap_estimate(m: *HllMap, key: *u8, key_len: i64) -> i64 { |
| 148 | func nx_hllmap_query(m: *HllMap, key: *u8, key_len: i64) -> *ApproxI64 {
called by 1: main calls 5: nx_hllmap_key_hashnx_hllmap_probenx_hmap_entry_atnx_approx_newnx_hll_query |
| 167 | func nx_hllmap_max2(x: i64, y: i64) -> i64 {
called by 1: nx_hllmap_merge |
| 174 | func nx_hllmap_clone_hll(src: *Hll) -> *Hll { |
| 184 | func nx_hllmap_merge(a: *HllMap, b: *HllMap) -> *HllMap {
called by 2: mainmain calls 5: nx_hllmap_max2nx_hllmap_allocnx_hmap_entry_atnx_hllmap_probenx_hllmap_clone_hll |
| 236 | func nx_hllmap_memory_bytes(m: *HllMap) -> i64 { |
| 243 | func nx_hllmap_n_entries(m: *HllMap) -> i64 {
called by 1: main |