sketch_hll_packed.nx
buildroot/runtime/sketch_hll_packed.nx
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 · 2 importers
imports: syscalls.nxmurmur3.nxsketch_hll.nxsketch_types.nx
imported by: sketch_hll_packed_test.nxsketch_hll_packed_vs_hll8_bench.nx
structs
| 45 | struct Hll6 { |
consts
| 37 | const NX_HLL6_LGK_MIN: i64 = 4 |
| 38 | const NX_HLL6_LGK_MAX: i64 = 10 |
| 40 | const NX_HLL6_SEED_HI: i64 = 0x9747B28C |
| 41 | const NX_HLL6_SEED_LO: i64 = 0x36185EC0 |
functions
| 66 | func nx_hll6_get(regs: *u8, idx: i64) -> i64 { |
| 77 | func nx_hll6_set(regs: *u8, idx: i64, value: i64) -> i64 { |
| 97 | func nx_hll6_alloc(lg_k: i64, seed: i64) -> *Hll6 { |
| 124 | func nx_hll6_add(h: *Hll6, key: *u8, len: i64) -> i64 { |
| 160 | func nx_hll6_estimate(h: *Hll6) -> i64 { |
| 189 | func nx_hll6_query(h: *Hll6) -> *ApproxI64 { |
| 204 | func nx_hll6_memory_bytes(h: *Hll6) -> i64 { |