sketch_comparator.nx source
↩ module page · 211 lines · 7908 B
1// sketch_comparator.nx -- sealed-verdict comparator for head-to-head stomp claims.
2//
3// THE VALIDATION PRIMITIVE. Every claim of the form "our primitive
4// beats incumbent X on axis Y" must pass through this. Sealed verdicts:
5//
6// NX_CMP_VERDICT_BEATS our primitive measurably better
7// NX_CMP_VERDICT_EQUIVALENT within tolerance band; can't distinguish
8// NX_CMP_VERDICT_LOSES incumbent measurably better
9// NX_CMP_VERDICT_INCONCLUSIVE missing data or degenerate inputs
10//
11// THREE INDEPENDENT AXES:
12// ACCURACY -- whoever's closer to ground truth wins
13// MEMORY -- smaller bytes wins
14// TIME -- faster wall-time wins
15//
16// COMPOSITE verdict aggregates 3 axis verdicts via majority vote with
17// inconclusive-axis discounting. A 2/3 majority with one INCONCLUSIVE
18// is enough to call. A 1/1/1 tie returns EQUIVALENT.
19//
20// All inputs are i64; caller supplies measurements from external runs.
21// This primitive does NOT itself run benchmarks -- it normalizes the
22// VERDICT against typed tolerance, so claims become falsifiable.
23//
24// LOSSLESS-LANGUAGE DISCIPLINE: result struct carries verdict + signed
25// delta in PPM (positive = our wins) + ppb confidence.
26
27import "syscalls.nx"
28import "sketch_types.nx"
29
30const NX_CMP_VERDICT_BEATS: i64 = 0
31const NX_CMP_VERDICT_EQUIVALENT: i64 = 1
32const NX_CMP_VERDICT_LOSES: i64 = 2
33const NX_CMP_VERDICT_INCONCLUSIVE: i64 = 3
34
35const NX_CMP_AXIS_ACCURACY: i64 = 0
36const NX_CMP_AXIS_MEMORY: i64 = 1
37const NX_CMP_AXIS_TIME: i64 = 2
38
39struct ComparisonResult {
40 verdict: i64, // sealed enum
41 delta_ppm: i64, // signed: positive = ours wins (by this amount in PPM)
42 conf_ppb: i64, // confidence (degenerate inputs lower this)
43 axis: i64, // which axis was compared
44}
45
46// === abs ==========================================================
47
48func nx_cmp_iabs(x: i64) -> i64 {
49 if x < 0 { return -x }
50 return x
51}
52
53// === ACCURACY axis ================================================
54//
55// Inputs: our_value, their_value, ground_truth, tolerance_ppm.
56// Closer to truth wins; tie if both within tolerance of equal distance.
57//
58// delta_ppm = (their_error - our_error) * 1_000_000 / |truth|
59// positive = our is closer (ours wins)
60// negative = their is closer (we lose)
61
62func nx_cmp_accuracy(our: i64, theirs: i64, truth: i64, tolerance_ppm: i64) -> *ComparisonResult {
63 let raw: *u8 = sys_mmap(40)
64 let r: *ComparisonResult = raw as *ComparisonResult
65 r.axis = NX_CMP_AXIS_ACCURACY
66 r.conf_ppb = 1000000000
67 if truth == 0 {
68 // Cannot normalize relative error.
69 r.verdict = NX_CMP_VERDICT_INCONCLUSIVE
70 r.delta_ppm = 0
71 r.conf_ppb = 500000000 // half-confidence (degenerate)
72 return r
73 }
74 let our_err: i64 = nx_cmp_iabs(our - truth)
75 let their_err: i64 = nx_cmp_iabs(theirs - truth)
76 let truth_abs: i64 = nx_cmp_iabs(truth)
77 // delta = (their_err - our_err) / truth, in PPM
78 let delta_ppm: i64 = ((their_err - our_err) * 1000000) / truth_abs
79 r.delta_ppm = delta_ppm
80 if delta_ppm > tolerance_ppm {
81 r.verdict = NX_CMP_VERDICT_BEATS
82 }
83 if delta_ppm < -tolerance_ppm {
84 r.verdict = NX_CMP_VERDICT_LOSES
85 }
86 if delta_ppm <= tolerance_ppm {
87 if delta_ppm >= -tolerance_ppm {
88 r.verdict = NX_CMP_VERDICT_EQUIVALENT
89 }
90 }
91 return r
92}
93
94// === MEMORY axis ==================================================
95//
96// Inputs: our_bytes, their_bytes, tolerance_ppm.
97// Smaller wins. delta_ppm = (their - our) * 1_000_000 / their.
98
99func nx_cmp_memory(our_bytes: i64, their_bytes: i64, tolerance_ppm: i64) -> *ComparisonResult {
100 let raw: *u8 = sys_mmap(40)
101 let r: *ComparisonResult = raw as *ComparisonResult
102 r.axis = NX_CMP_AXIS_MEMORY
103 r.conf_ppb = 1000000000
104 if their_bytes <= 0 {
105 r.verdict = NX_CMP_VERDICT_INCONCLUSIVE
106 r.delta_ppm = 0
107 r.conf_ppb = 500000000
108 return r
109 }
110 let delta_ppm: i64 = ((their_bytes - our_bytes) * 1000000) / their_bytes
111 r.delta_ppm = delta_ppm
112 if delta_ppm > tolerance_ppm {
113 r.verdict = NX_CMP_VERDICT_BEATS
114 }
115 if delta_ppm < -tolerance_ppm {
116 r.verdict = NX_CMP_VERDICT_LOSES
117 }
118 if delta_ppm <= tolerance_ppm {
119 if delta_ppm >= -tolerance_ppm {
120 r.verdict = NX_CMP_VERDICT_EQUIVALENT
121 }
122 }
123 return r
124}
125
126// === TIME axis ====================================================
127//
128// Inputs: our_us, their_us, tolerance_ppm. Faster wins.
129// delta_ppm = (their - our) * 1_000_000 / their.
130
131func nx_cmp_time(our_us: i64, their_us: i64, tolerance_ppm: i64) -> *ComparisonResult {
132 let raw: *u8 = sys_mmap(40)
133 let r: *ComparisonResult = raw as *ComparisonResult
134 r.axis = NX_CMP_AXIS_TIME
135 r.conf_ppb = 1000000000
136 if their_us <= 0 {
137 r.verdict = NX_CMP_VERDICT_INCONCLUSIVE
138 r.delta_ppm = 0
139 r.conf_ppb = 500000000
140 return r
141 }
142 let delta_ppm: i64 = ((their_us - our_us) * 1000000) / their_us
143 r.delta_ppm = delta_ppm
144 if delta_ppm > tolerance_ppm {
145 r.verdict = NX_CMP_VERDICT_BEATS
146 }
147 if delta_ppm < -tolerance_ppm {
148 r.verdict = NX_CMP_VERDICT_LOSES
149 }
150 if delta_ppm <= tolerance_ppm {
151 if delta_ppm >= -tolerance_ppm {
152 r.verdict = NX_CMP_VERDICT_EQUIVALENT
153 }
154 }
155 return r
156}
157
158// === COMPOSITE verdict ============================================
159//
160// Aggregate three axis verdicts. Rules (sealed):
161// - All three BEATS -> COMPOSITE BEATS (high confidence)
162// - 2 BEATS + 1 EQUIVALENT -> BEATS
163// - 2 BEATS + 1 LOSES -> BEATS but lower confidence (mixed)
164// - 1 BEATS + 2 EQUIVALENT -> BEATS (one clear win)
165// - All EQUIVALENT -> EQUIVALENT
166// - 1+ LOSES outweighs equal-count BEATS -> LOSES (loss-averse)
167// - Any 2+ INCONCLUSIVE -> INCONCLUSIVE
168//
169// This is a deliberate LOSS-AVERSE policy: tied verdicts default to
170// EQUIVALENT, not BEATS. We don't claim wins unless they're clear.
171
172func nx_cmp_composite(acc: *ComparisonResult, mem: *ComparisonResult,
173 tim: *ComparisonResult) -> i64 {
174 // Count INCONCLUSIVE results -- if 2+, refuse.
175 var n_inc: i64 = 0
176 if acc.verdict == NX_CMP_VERDICT_INCONCLUSIVE { n_inc = n_inc + 1 }
177 if mem.verdict == NX_CMP_VERDICT_INCONCLUSIVE { n_inc = n_inc + 1 }
178 if tim.verdict == NX_CMP_VERDICT_INCONCLUSIVE { n_inc = n_inc + 1 }
179 if n_inc >= 2 { return NX_CMP_VERDICT_INCONCLUSIVE }
180
181 var n_beats: i64 = 0
182 var n_loses: i64 = 0
183 if acc.verdict == NX_CMP_VERDICT_BEATS { n_beats = n_beats + 1 }
184 if mem.verdict == NX_CMP_VERDICT_BEATS { n_beats = n_beats + 1 }
185 if tim.verdict == NX_CMP_VERDICT_BEATS { n_beats = n_beats + 1 }
186 if acc.verdict == NX_CMP_VERDICT_LOSES { n_loses = n_loses + 1 }
187 if mem.verdict == NX_CMP_VERDICT_LOSES { n_loses = n_loses + 1 }
188 if tim.verdict == NX_CMP_VERDICT_LOSES { n_loses = n_loses + 1 }
189
190 // Loss-averse: any loss beats equal beats.
191 if n_loses > n_beats { return NX_CMP_VERDICT_LOSES }
192 if n_loses == n_beats {
193 if n_beats == 0 { return NX_CMP_VERDICT_EQUIVALENT }
194 return NX_CMP_VERDICT_EQUIVALENT // tie -> equivalent
195 }
196 // n_beats > n_loses
197 return NX_CMP_VERDICT_BEATS
198}
199
200// === query (typed envelope) =======================================
201
202func nx_cmp_query(r: *ComparisonResult) -> *ApproxI64 {
203 return nx_approx_new(r.verdict, NX_ENV_ABS, 0,
204 r.conf_ppb,
205 NX_MATURITY_PRODUCTION,
206 NX_ADV_HONEST)
207}
208
209func nx_cmp_memory_bytes(r: *ComparisonResult) -> i64 {
210 return 40
211}