nx_sketch_hll_provenance.nx source
↩ module page · 87 lines · 4406 B
1// sketch_hll_provenance.nx -- sample CAPABILITY + IMPROVEMENT_OPP entries
2// for sketch_hll.
3//
4// Every primitive should ship one of these alongside its smoke gate. The
5// CAPABILITY entry declares what the primitive does (so a human/AI reading
6// the repo for the first time sees the full Genealogy + Lineage at a
7// glance). The IMPROVEMENT_OPP entry calls out any lineage step that's
8// still TODO -- in this case, Heule 2013's bias-correction table, which
9// is on sketch_hll's lineage but not yet shipped.
10//
11// Reading the provenance ledger gives the SAME insight as reading every
12// commit message and source comment: where this primitive came from,
13// what math it stands on, and what's missing.
14
15// nx_safety_envelope:
16// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
17// sil_target: SIL1
18// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
19// verdict: NOT_YET_EVALUATED
20
21import "nx_syscalls.nx"
22import "nx_sketch_buglog.nx"
23import "nx_sketch_types.nx"
24
25func main() -> i64 {
26 // ============================================================
27 // Entry 1: CAPABILITY registration for sketch_hll
28 // ============================================================
29 let cap: *BugLog = nx_buglog_alloc()
30 nx_buglog_set_kind(cap, NX_PROV_KIND_CAPABILITY)
31 nx_buglog_set_who_z(cap, "sketch_hll")
32 nx_buglog_set_what_z(cap, "HyperLogLog cardinality sketch, lg_k in [4,10], rel-stddev = 1.04/sqrt(m)")
33 nx_buglog_set_when_z(cap, "2026-05-12")
34 nx_buglog_set_axis(cap, NX_BUG_AXIS_CAPABILITY)
35 nx_buglog_set_why_z(cap, "approximate distinct-count over arbitrary streams; bounded memory")
36 nx_buglog_set_how_z(cap, "nx_hll_alloc(lg_k, seed); nx_hll_add(h, key, len); nx_hll_estimate(h)")
37
38 nx_buglog_add_genealogy_z(cap, "carter_wegman")
39 nx_buglog_add_genealogy_z(cap, "flajolet_martin")
40 nx_buglog_add_genealogy_z(cap, "durand_flajolet")
41 nx_buglog_add_genealogy_z(cap, "flajolet_2007")
42 nx_buglog_add_genealogy_z(cap, "heule_2013")
43 nx_buglog_add_genealogy_z(cap, "datasketches")
44 nx_buglog_add_genealogy_z(cap, "ours")
45
46 nx_buglog_add_lineage_z(cap, "uniform_hash")
47 nx_buglog_add_lineage_z(cap, "k_wise_indep")
48 nx_buglog_add_lineage_z(cap, "leading_zero_rank")
49 nx_buglog_add_lineage_z(cap, "fm85_max")
50 nx_buglog_add_lineage_z(cap, "stochastic_avg")
51 nx_buglog_add_lineage_z(cap, "loglog_2003")
52 nx_buglog_add_lineage_z(cap, "hyperloglog_2007")
53 nx_buglog_add_lineage_z(cap, "alpha_m_correction")
54 nx_buglog_add_lineage_z(cap, "lc_fallback")
55
56 nx_buglog_set_performance_z(cap,
57 "{\"lg_k_range\":\"[4,10]\",\"rel_stddev\":\"1.04/sqrt(m)\",\"memory_bytes_lg_k_7\":152,\"composes_against\":[\"murmur3_32\"]}")
58
59 nx_buglog_emit(cap)
60
61 // ============================================================
62 // Entry 2: IMPROVEMENT_OPP for the unshipped Heule bias table
63 // ============================================================
64 // The lineage above lists alpha_m_correction + lc_fallback but NOT
65 // heule_bias_table. Heule 2013's bias table is the next math step
66 // (see docs/lineage.md). Shipping it should close our remaining
67 // 7% mean-error gap vs DataSketches.
68 let opp: *BugLog = nx_buglog_alloc()
69 nx_buglog_set_kind(opp, NX_PROV_KIND_IMPROVEMENT_OPP)
70 nx_buglog_set_who_z(opp, "sketch_hll")
71 nx_buglog_set_what_z(opp, "lineage step heule_bias_table is referenced but not implemented")
72 nx_buglog_set_when_z(opp, "2026-05-12")
73 nx_buglog_set_axis(opp, NX_BUG_AXIS_ACCURACY)
74 nx_buglog_set_why_z(opp, "Heule 2013 bias-correction table is the next link in the math chain after alpha_m_correction; shipping it should flip our 7% accuracy LOSES verdict to BEATS")
75 nx_buglog_set_how_z(opp, "implement Heule's per-lg_k bias-correction tables (~200 entries per lg_k); apply in mid-range zone between LC and raw HLL formula")
76
77 nx_buglog_add_genealogy_z(opp, "heule_2013")
78 nx_buglog_add_lineage_z(opp, "alpha_m_correction")
79 nx_buglog_add_lineage_z(opp, "heule_bias_table")
80
81 nx_buglog_set_performance_z(opp,
82 "{\"current_gap_pct\":7,\"current_our_mean_err\":57,\"current_ds_mean_err\":53,\"expected_after_fix\":\"our_mean_err <= ds_mean_err (BEATS)\",\"effort_estimate\":\"~1 session: port Heule tables for lg_k 4..10\"}")
83
84 nx_buglog_emit(opp)
85
86 return 0
87}