code wiki / (root) / nx_sketch_hllmap.nx

nx_sketch_hllmap.nx

buildroot/runtime/nx_sketch_hllmap.nx

8422 B251 linesdepth 6pulls 11 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

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

nx_syscalls.nx nx_murmur3.nx nx_sketch_hll.nx nx_sketch_types.nx nx_sketch_hllmap.nx

imports: nx_syscalls.nxnx_murmur3.nxnx_sketch_hll.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

37struct HllMapEntry
42struct HllMap

consts

34const NX_HMAP_EMPTY: i64 = 0
35const NX_HMAP_LF_MAX_PCT: i64 = 70 // resize at >70% load

functions

52func nx_hmap_is_pow2(n: i64) -> i64
called by 1: nx_hllmap_alloc
58func nx_hllmap_alloc(capacity: i64, lg_k: i64, seed: i64) -> *HllMap
81func nx_hmap_entry_at(m: *HllMap, i: i64) -> *HllMapEntry
91func nx_hllmap_probe(m: *HllMap, key_hash: i64) -> i64
121func nx_hllmap_key_hash(m: *HllMap, key: *u8, len: i64) -> i64
127func nx_hllmap_add(m: *HllMap, key: *u8, key_len: i64,
146func nx_hllmap_estimate(m: *HllMap, key: *u8, key_len: i64) -> i64
154func nx_hllmap_query(m: *HllMap, key: *u8, key_len: i64) -> *ApproxI64
173func nx_hllmap_max2(x: i64, y: i64) -> i64
called by 1: nx_hllmap_merge
180func nx_hllmap_clone_hll(src: *Hll) -> *Hll
called by 1: nx_hllmap_merge calls 1: nx_hll_alloc
190func nx_hllmap_merge(a: *HllMap, b: *HllMap) -> *HllMap
242func nx_hllmap_memory_bytes(m: *HllMap) -> i64
249func nx_hllmap_n_entries(m: *HllMap) -> i64