nx_sketch_hll.nx
buildroot/runtime/nx_sketch_hll.nx
about
sketch_hll.nx -- HyperLogLog cardinality sketch in NishiLang.
Flajolet 2007 + Heule 2013 small-range correction. Sovereign-
tier sibling port of nishi-engine/packages/core-sketch/src/hll.ts.
All-i64 implementation: no f64 source-level types, no float
literals; harmonic-mean estimator computed in Q32.32 fixed-point
so the file compiles through both the C-anchor (Wheeler comparator)
and the NishiLang sibling.
Per the lossless-language meta-cardinal (nishi-engine doc 20):
the cardinality estimate ships in an Approximate<i64> envelope
declaring stddev_rel = 1.04/sqrt(m) at confidence 0.6827, with
MaturityClass = ReferenceImpl and AdversarialSafety = Honest.
Bounded-loss-by-typing, not silent-loss.
Memory: 1 byte per register. lgK=11 -> 2048 bytes; lgK=12 ->
4096 bytes. Standard error: 1.04 / sqrt(2^lgK).
Roadmap citations:
doc 19 -- DataSketches stomp roadmap
doc 20 -- universal lossless language
doc 21 -- research partnership not isolation
dependencies 8 imports · 13 importers
diagram shows first 10 each side; +0 more imports, +3 more importers in the complete lists below.
imports: nx_syscalls.nxnx_murmur3.nxnx_xxhash.nxnx_bit.nxnx_bits.nxnx_sketch_types.nxnx_hll_bias_table.nxnx_i128.nx
imported by: nx_bench_emit.nxnx_bench_hll_throughput.nxnx_bench_hll_vs_cpc.nxnx_bench_hll_vs_cpcd.nxnx_bench_hll_vs_datasketches.nxnx_bench_multiseed.nxnx_dataframe_approx.nxnx_gen_hll_bias_nx.nxnx_sketch_cms.nxnx_sketch_hll4.nxnx_sketch_hll_packed.nxnx_sketch_hllmap.nxnx_sketch_robust_hll.nx
structs
| 71 | struct Hll |
consts
| 45 | const NX_HLL_LGK_MIN: i64 = 4 |
| 46 | const NX_HLL_LGK_MAX: i64 = 10 |
| 51 | const NX_HLL_SEED_HI: i64 = 0x9747B28C |
| 52 | const NX_HLL_SEED_LO: i64 = 0x36185EC0 |
| 59 | const NX_HLL_PPM_SCALE: i64 = 1000000 |
| 60 | const NX_HLL_LN2_PPM: i64 = 693147 // ln(2) * 1e6 |
| 66 | const NX_HLL_LC_PEG_NUM: i64 = 7 |
| 67 | const NX_HLL_LC_PEG_DEN: i64 = 10 |
| 213 | const NX_HLL_HEULE_THRESH_LGK4: i64 = 10 |
| 214 | const NX_HLL_HEULE_THRESH_LGK5: i64 = 20 |
| 215 | const NX_HLL_HEULE_THRESH_LGK6: i64 = 40 |
| 216 | const NX_HLL_HEULE_THRESH_LGK7: i64 = 80 |
| 217 | const NX_HLL_HEULE_THRESH_LGK8: i64 = 220 |
| 218 | const NX_HLL_HEULE_THRESH_LGK9: i64 = 400 |
| 219 | const NX_HLL_HEULE_THRESH_LGK10: i64 = 900 |
| 306 | const NX_HLL_LAGRANGE_Q: i64 = 24 // 24-bit fractional Q-format |
| 307 | const NX_HLL_LAGRANGE_Q_SCALE: i64 = 16777216 // 1 << 24 |
functions
| 93 | func nx_hll_alloc(lg_k: i64, seed: i64) -> *Hll |
| 135 | func nx_hll_add(h: *Hll, key: *u8, len: i64) -> i64 |
| 191 | func nx_hll_alpha_m_sq_q64(lg_k: i64) -> i64 |
| 202 | func nx_hll_pow2_neg_q32(r: i64) -> i64 |
| 221 | func nx_hll_heule_threshold(lg_k: i64) -> i64 called by 1: main |
| 247 | func nx_hll_log2_ppm(x: i64) -> i64 called by 1: nx_hll_estimate |
| 274 | func nx_hll_bias_table_get(lg_k: i64, i: i64) -> i64 |
| 285 | func nx_hll_bias_table_n(lg_k: i64) -> i64 |
| 309 | func nx_hll_bias_correct(lg_k: i64, raw_est: i64) -> i64 |
| 387 | func nx_hll_estimate(h: *Hll) -> i64 |
| 460 | func nx_hll_stddev_rel_ppb(lg_k: i64) -> i64 |
| 476 | func nx_hll_query(h: *Hll) -> *ApproxI64 |
| 487 | func nx_hll_merge(a: *Hll, b: *Hll) -> *Hll calls 1: nx_hll_alloc |