sketch_hll_provenance.nx source
↩ module page · 81 lines · 4227 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
15import "syscalls.nx"
16import "sketch_buglog.nx"
17import "sketch_types.nx"
18
19func main() -> i64 {
20 // ============================================================
21 // Entry 1: CAPABILITY registration for sketch_hll
22 // ============================================================
23 let cap: *BugLog = nx_buglog_alloc()
24 nx_buglog_set_kind(cap, NX_PROV_KIND_CAPABILITY)
25 nx_buglog_set_who_z(cap, "sketch_hll")
26 nx_buglog_set_what_z(cap, "HyperLogLog cardinality sketch, lg_k in [4,10], rel-stddev = 1.04/sqrt(m)")
27 nx_buglog_set_when_z(cap, "2026-05-12")
28 nx_buglog_set_axis(cap, NX_BUG_AXIS_CAPABILITY)
29 nx_buglog_set_why_z(cap, "approximate distinct-count over arbitrary streams; bounded memory")
30 nx_buglog_set_how_z(cap, "nx_hll_alloc(lg_k, seed); nx_hll_add(h, key, len); nx_hll_estimate(h)")
31
32 nx_buglog_add_genealogy_z(cap, "carter_wegman")
33 nx_buglog_add_genealogy_z(cap, "flajolet_martin")
34 nx_buglog_add_genealogy_z(cap, "durand_flajolet")
35 nx_buglog_add_genealogy_z(cap, "flajolet_2007")
36 nx_buglog_add_genealogy_z(cap, "heule_2013")
37 nx_buglog_add_genealogy_z(cap, "datasketches")
38 nx_buglog_add_genealogy_z(cap, "ours")
39
40 nx_buglog_add_lineage_z(cap, "uniform_hash")
41 nx_buglog_add_lineage_z(cap, "k_wise_indep")
42 nx_buglog_add_lineage_z(cap, "leading_zero_rank")
43 nx_buglog_add_lineage_z(cap, "fm85_max")
44 nx_buglog_add_lineage_z(cap, "stochastic_avg")
45 nx_buglog_add_lineage_z(cap, "loglog_2003")
46 nx_buglog_add_lineage_z(cap, "hyperloglog_2007")
47 nx_buglog_add_lineage_z(cap, "alpha_m_correction")
48 nx_buglog_add_lineage_z(cap, "lc_fallback")
49
50 nx_buglog_set_performance_z(cap,
51 "{\"lg_k_range\":\"[4,10]\",\"rel_stddev\":\"1.04/sqrt(m)\",\"memory_bytes_lg_k_7\":152,\"composes_against\":[\"murmur3_32\"]}")
52
53 nx_buglog_emit(cap)
54
55 // ============================================================
56 // Entry 2: IMPROVEMENT_OPP for the unshipped Heule bias table
57 // ============================================================
58 // The lineage above lists alpha_m_correction + lc_fallback but NOT
59 // heule_bias_table. Heule 2013's bias table is the next math step
60 // (see docs/lineage.md). Shipping it should close our remaining
61 // 7% mean-error gap vs DataSketches.
62 let opp: *BugLog = nx_buglog_alloc()
63 nx_buglog_set_kind(opp, NX_PROV_KIND_IMPROVEMENT_OPP)
64 nx_buglog_set_who_z(opp, "sketch_hll")
65 nx_buglog_set_what_z(opp, "lineage step heule_bias_table is referenced but not implemented")
66 nx_buglog_set_when_z(opp, "2026-05-12")
67 nx_buglog_set_axis(opp, NX_BUG_AXIS_ACCURACY)
68 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")
69 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")
70
71 nx_buglog_add_genealogy_z(opp, "heule_2013")
72 nx_buglog_add_lineage_z(opp, "alpha_m_correction")
73 nx_buglog_add_lineage_z(opp, "heule_bias_table")
74
75 nx_buglog_set_performance_z(opp,
76 "{\"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\"}")
77
78 nx_buglog_emit(opp)
79
80 return 0
81}