nx_sketch_hll_provenance_v2.nx source
↩ module page · 70 lines · 4104 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
9// nx_safety_envelope:
10// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
11// sil_target: SIL1
12// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
13// verdict: NOT_YET_EVALUATED
14
15import "nx_syscalls.nx"
16import "nx_sketch_buglog.nx"
17import "nx_sketch_types.nx"
18
19func main() -> i64 {
20 // ============================================================
21 // Entry 1: BUG (RESOLVED) -- the prior IMPROVEMENT_OPP's hypothesis
22 // tested and CONFIRMED. This is the system working.
23 // ============================================================
24 let resolved: *BugLog = nx_buglog_alloc()
25 nx_buglog_set_kind(resolved, NX_PROV_KIND_BUG)
26 nx_buglog_set_who_z(resolved, "sketch_hll")
27 nx_buglog_set_what_z(resolved, "RESOLVED: mid-range bias gap closed by shipping bias-correction table")
28 nx_buglog_set_when_z(resolved, "2026-05-12T-bias-ship")
29 nx_buglog_set_axis(resolved, NX_BUG_AXIS_ACCURACY)
30 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")
31 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")
32
33 nx_buglog_add_genealogy_z(resolved, "heule_2013")
34 nx_buglog_add_genealogy_z(resolved, "ours")
35
36 nx_buglog_add_lineage_z(resolved, "heule_bias_table")
37 nx_buglog_add_lineage_z(resolved, "alpha_m_correction")
38 nx_buglog_add_lineage_z(resolved, "log_function")
39
40 nx_buglog_set_performance_z(resolved,
41 "{\"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\"}")
42
43 nx_buglog_emit(resolved)
44
45 // ============================================================
46 // Entry 2: IMPROVEMENT_OPP -- next step toward absolute precision.
47 // The 1-point residual gap (5 vs 4) is partly noise, partly our
48 // linear-interp vs DS's cubic. Path: use DS Java's canonical
49 // CompositeInterpolationXTable + cubic interpolation.
50 // ============================================================
51 let opp: *BugLog = nx_buglog_alloc()
52 nx_buglog_set_kind(opp, NX_PROV_KIND_IMPROVEMENT_OPP)
53 nx_buglog_set_who_z(opp, "sketch_hll")
54 nx_buglog_set_what_z(opp, "use DS canonical bias-table values + cubic interpolation for sub-1 mean error")
55 nx_buglog_set_when_z(opp, "2026-05-12T-bias-ship")
56 nx_buglog_set_axis(opp, NX_BUG_AXIS_ACCURACY)
57 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")
58 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")
59
60 nx_buglog_add_genealogy_z(opp, "heule_2013")
61 nx_buglog_add_genealogy_z(opp, "datasketches")
62 nx_buglog_add_lineage_z(opp, "heule_bias_table")
63
64 nx_buglog_set_performance_z(opp,
65 "{\"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\"]}")
66
67 nx_buglog_emit(opp)
68
69 return 0
70}