code wiki / (root) / nx_sketch_hll_packed.nx

nx_sketch_hll_packed.nx

buildroot/runtime/nx_sketch_hll_packed.nx

7217 B212 linesdepth 6pulls 11 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_hll_packed.nx -- 4-bit and 6-bit packed-register HLL. Same algorithm as runtime/sketch_hll.nx; different register storage layout. Saves 50% (HLL_4) or 25% (HLL_6) memory at the cost of bit-twiddling on every register read/write. Tradeoff is the same one DataSketches makes with HLL_4-12 = 2095 bytes vs HLL_8-12 = 4096 bytes; we match their memory footprint while preserving every NishiLang substrate guarantee. rho range: lg_k=10 -> max rho = 64 - 10 + 1 = 55, fits in 6 bits; but 4 bits only addresses [0, 15]. For HLL_4 we use the standard HEULE encoding: a 4-bit base value (0..15) plus a per-bucket EXCEPTION table for buckets whose true rho exceeds 15. In practice exceptions are rare (P[rho > 15] = 1/2^15 = 3e-5) so the exception table stays small. For HLL_6 we have plenty of headroom (max 63), so no exception table is needed. FIRST CUT: ship HLL_6 (simpler -- no exception table) to land the memory stomp. HLL_4 with the exception-table machinery follows in a queued commit. MEMORY: HLL_6-12 (lg_k=12) = 4096 * 6 / 8 = 3072 bytes vs HLL_8 4096 bytes (25% reduction). HLL_6-10 = 1024 * 6 / 8 = 768 bytes vs HLL_8 1024 bytes. Per the lossless-language discipline (doc 20): packing the bits doesn't change the typed envelope -- query returns the same ApproxI64 shape as nx_hll_query. The memory footprint reduction is a substrate-internal optimization, invisible at the API surface.

dependencies 4 imports · 0 importers

nx_syscalls.nx nx_murmur3.nx nx_sketch_hll.nx nx_sketch_types.nx nx_sketch_hll_packed.nx

imports: nx_syscalls.nxnx_murmur3.nxnx_sketch_hll.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

51struct Hll6

consts

43const NX_HLL6_LGK_MIN: i64 = 4
44const NX_HLL6_LGK_MAX: i64 = 10
46const NX_HLL6_SEED_HI: i64 = 0x9747B28C
47const NX_HLL6_SEED_LO: i64 = 0x36185EC0

functions

72func nx_hll6_get(regs: *u8, idx: i64) -> i64
83func nx_hll6_set(regs: *u8, idx: i64, value: i64) -> i64
called by 1: nx_hll6_add
103func nx_hll6_alloc(lg_k: i64, seed: i64) -> *Hll6
calls 1: sys_mmap
130func nx_hll6_add(h: *Hll6, key: *u8, len: i64) -> i64
166func nx_hll6_estimate(h: *Hll6) -> i64
195func nx_hll6_query(h: *Hll6) -> *ApproxI64
210func nx_hll6_memory_bytes(h: *Hll6) -> i64