code wiki / (root) / sketch_hll.nx

sketch_hll.nx

buildroot/runtime/sketch_hll.nx

23495 B563 linesdepth 5pulls 10 transitivereach 31 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

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 · 26 importers

syscalls.nx murmur3.nx nx_xxhash.nx nx_bit.nx nx_bits.nx sketch_types.nx hll_bias_table.nx nx_i128.nx sketch_hll.nx _a2a_hll_i64_x100.nx _a2a_hll_x100.nx _a2a_subst.nx _py_head2head_substrate.nx bench_emit.nx bench_hll_vs_cpc.nx bench_hll_vs_cpcd.nx bench_multiseed.nx gen_hll_bias_nx.nx sketch_cms.nx

diagram shows first 10 each side; +0 more imports, +16 more importers in the complete lists below.

imports: syscalls.nxmurmur3.nxnx_xxhash.nxnx_bit.nxnx_bits.nxsketch_types.nxhll_bias_table.nxnx_i128.nx

imported by: _a2a_hll_i64_x100.nx_a2a_hll_x100.nx_a2a_subst.nx_py_head2head_substrate.nxbench_emit.nxbench_hll_vs_cpc.nxbench_hll_vs_cpcd.nxbench_multiseed.nxgen_hll_bias_nx.nxsketch_cms.nxsketch_hll4.nxsketch_hll4_vs_hll8_bench.nxsketch_hll_lgk12_vs_lgk8_bench.nxsketch_hll_packed.nxsketch_hll_packed_test.nxsketch_hll_packed_vs_hll8_bench.nxsketch_hll_test.nxsketch_hll_vs_materialized_set_bench.nxsketch_hllmap.nxsketch_hllmap_merge_capability_bench.nxsketch_hllmap_test.nxsketch_lc_vs_hll_small_n_bench.nxsketch_observability_dashboard_bench.nxsketch_robust_hll.nxsketch_robust_hll_vs_hll_adv_bench.nxsketch_theta_intersect_vs_hll_bench.nx

structs

69struct Hll {

consts

39const NX_HLL_LGK_MIN: i64 = 4
40const NX_HLL_LGK_MAX: i64 = 12 // bits-up scale 2026-05-20 (was 10).
49const NX_HLL_SEED_HI: i64 = 0x9747B28C
50const NX_HLL_SEED_LO: i64 = 0x36185EC0
57const NX_HLL_PPM_SCALE: i64 = 1000000
58const NX_HLL_LN2_PPM: i64 = 693147 // ln(2) * 1e6
64const NX_HLL_LC_PEG_NUM: i64 = 7
65const NX_HLL_LC_PEG_DEN: i64 = 10
216const NX_HLL_HEULE_THRESH_LGK4: i64 = 10
217const NX_HLL_HEULE_THRESH_LGK5: i64 = 20
218const NX_HLL_HEULE_THRESH_LGK6: i64 = 40
219const NX_HLL_HEULE_THRESH_LGK7: i64 = 80
220const NX_HLL_HEULE_THRESH_LGK8: i64 = 220
221const NX_HLL_HEULE_THRESH_LGK9: i64 = 400
222const NX_HLL_HEULE_THRESH_LGK10: i64 = 900
223const NX_HLL_HEULE_THRESH_LGK11: i64 = 1800 // bits-up extrapolation (2x trend)
224const NX_HLL_HEULE_THRESH_LGK12: i64 = 3100 // Heule paper canonical for lg_k=12
313const NX_HLL_LAGRANGE_Q: i64 = 24 // 24-bit fractional Q-format
314const NX_HLL_LAGRANGE_Q_SCALE: i64 = 16777216 // 1 << 24

functions

82func _sketch_hll_clz32_superseded(x: i64) -> i64 {
calls 1: nx_bits_clz32
88func nx_hll_alloc(lg_k: i64, seed: i64) -> *Hll {
called by 21: mainmainmainmainmainmain+15
130func nx_hll_add(h: *Hll, key: *u8, len: i64) -> i64 {
called by 18: mainmainmainmainmainmain+12 calls 2: murmur3_32nx_clz32
186func nx_hll_alpha_m_sq_q64(lg_k: i64) -> i64 {
called by 4: nx_hll_raw_estimatenx_hll_estimatenx_hll4_estimatenx_hll6_estimate
205func nx_hll_pow2_neg_q32(r: i64) -> i64 {
called by 4: nx_hll_raw_estimatenx_hll_estimatenx_hll4_estimatenx_hll6_estimate
226func nx_hll_heule_threshold(lg_k: i64) -> i64 {
called by 1: main
254func nx_hll_log2_ppm(x: i64) -> i64 {
called by 1: nx_hll_estimate
281func nx_hll_bias_table_get(lg_k: i64, i: i64) -> i64 {
called by 2: nx_hll_bias_correctnx_hll_estimate calls 7: nx_hll_bias_lgk4nx_hll_bias_lgk5nx_hll_bias_lgk6nx_hll_bias_lgk7nx_hll_bias_lgk8nx_hll_bias_lgk9+1
292func nx_hll_bias_table_n(lg_k: i64) -> i64 {
called by 2: nx_hll_bias_correctnx_hll_estimate
316func nx_hll_bias_correct(lg_k: i64, raw_est: i64) -> i64 {
called by 1: nx_hll_estimate calls 3: nx_hll_bias_table_nnx_hll_bias_table_getnx_mulshl_div_i64
394func nx_hll_estimate(h: *Hll) -> i64 {
called by 21: mainmainmainmainmainmain+15 calls 6: nx_hll_pow2_neg_q32nx_hll_alpha_m_sq_q64nx_hll_bias_table_nnx_hll_bias_table_getnx_hll_log2_ppmnx_hll_bias_correct
467func nx_hll_stddev_rel_ppb(lg_k: i64) -> i64 {
called by 4: nx_hll_querynx_hll4_querynx_hll6_querynx_robust_hll_query
483func nx_hll_query(h: *Hll) -> *ApproxI64 {
called by 3: mainmainnx_hllmap_query calls 3: nx_hll_estimatenx_hll_stddev_rel_ppbnx_approx_new
521func nx_hll_add_i64(h: *Hll, key: i64) -> i64 {
called by 1: main calls 1: nx_clz32
550func nx_hll_merge(a: *Hll, b: *Hll) -> *Hll {
calls 1: nx_hll_alloc