sketch_hll_provenance_v2.nx source
↩ module page · 64 lines · 3908 B
1// sketch_hll_provenance_v2.nx -- post-bias-table provenance entries.
2//
3// Emits two entries after shipping the Heule bias-correction table:
4// 1. BUG (resolved): the prior IMPROVEMENT_OPP's hypothesis tested
5// and confirmed.
6// 2. IMPROVEMENT_OPP: next math step toward sub-1 mean error
7// (use DS's exact CompositeInterpolationXTable + cubic interp).
8
9import "syscalls.nx"
10import "sketch_buglog.nx"
11import "sketch_types.nx"
12
13func main() -> i64 {
14 // ============================================================
15 // Entry 1: BUG (RESOLVED) -- the prior IMPROVEMENT_OPP's hypothesis
16 // tested and CONFIRMED. This is the system working.
17 // ============================================================
18 let resolved: *BugLog = nx_buglog_alloc()
19 nx_buglog_set_kind(resolved, NX_PROV_KIND_BUG)
20 nx_buglog_set_who_z(resolved, "sketch_hll")
21 nx_buglog_set_what_z(resolved, "RESOLVED: mid-range bias gap closed by shipping bias-correction table")
22 nx_buglog_set_when_z(resolved, "2026-05-12T-bias-ship")
23 nx_buglog_set_axis(resolved, NX_BUG_AXIS_ACCURACY)
24 nx_buglog_set_why_z(resolved, "raw HLL biased high in (threshold, 5m] range; Heule 2013 bias-correction table maps biased raw_est back to corrected_n")
25 nx_buglog_set_how_z(resolved, "empirical 32-entry table per lg_k via bench/gen_hll_bias_table.py (Python HLL simulator, 200 seeds per sample point); linear interp lookup at query time")
26
27 nx_buglog_add_genealogy_z(resolved, "heule_2013")
28 nx_buglog_add_genealogy_z(resolved, "ours")
29
30 nx_buglog_add_lineage_z(resolved, "heule_bias_table")
31 nx_buglog_add_lineage_z(resolved, "alpha_m_correction")
32 nx_buglog_add_lineage_z(resolved, "log_function")
33
34 nx_buglog_set_performance_z(resolved,
35 "{\"workload\":\"n=100 lg_k=7\",\"before_mean_err\":48,\"after_mean_err\":5,\"reduction_pct\":89,\"ds_mean_err\":4,\"gap_to_ds_pct\":25,\"max_err_ours\":11,\"max_err_ds\":13,\"max_err_beats_ds\":true,\"seeds\":500,\"verdict\":\"IMPROVEMENT_OPP_HYPOTHESIS_CONFIRMED\"}")
36
37 nx_buglog_emit(resolved)
38
39 // ============================================================
40 // Entry 2: IMPROVEMENT_OPP -- next step toward absolute precision.
41 // The 1-point residual gap (5 vs 4) is partly noise, partly our
42 // linear-interp vs DS's cubic. Path: use DS Java's canonical
43 // CompositeInterpolationXTable + cubic interpolation.
44 // ============================================================
45 let opp: *BugLog = nx_buglog_alloc()
46 nx_buglog_set_kind(opp, NX_PROV_KIND_IMPROVEMENT_OPP)
47 nx_buglog_set_who_z(opp, "sketch_hll")
48 nx_buglog_set_what_z(opp, "use DS canonical bias-table values + cubic interpolation for sub-1 mean error")
49 nx_buglog_set_when_z(opp, "2026-05-12T-bias-ship")
50 nx_buglog_set_axis(opp, NX_BUG_AXIS_ACCURACY)
51 nx_buglog_set_why_z(opp, "our empirical 32-entry table + linear interp leaves a 1-point gap vs DS at 500 seeds; DS uses sparser table (42 entries) but cubic-spline interpolation gives sub-entry precision")
52 nx_buglog_set_how_z(opp, "extract org.apache.datasketches.hll.CompositeInterpolationXTable.xArrs from the DS Java jar via reflection (DumpDsHllBias.java probes this); port to NishiLang const tables; implement cubic interpolation primitive in runtime/cubic_interp.nx")
53
54 nx_buglog_add_genealogy_z(opp, "heule_2013")
55 nx_buglog_add_genealogy_z(opp, "datasketches")
56 nx_buglog_add_lineage_z(opp, "heule_bias_table")
57
58 nx_buglog_set_performance_z(opp,
59 "{\"current_gap\":\"5 vs 4 mean_err (within sampling noise)\",\"expected_after_fix\":\"<=DS or beats\",\"effort_estimate\":\"~1 session: extract tables + port cubic interp\",\"references\":[\"DS Java CompositeInterpolationXTable.class\",\"DS Java CubicInterpolation.class\"]}")
60
61 nx_buglog_emit(opp)
62
63 return 0
64}