sketch_tdigest_v2_vs_v1_bench.nx source
↩ module page · 113 lines · 4006 B
1// sketch_tdigest_v2_vs_v1_bench.nx -- paired measurement, T-Digest v2 vs v1.
2//
3// CLAIM TO VALIDATE:
4// v2 (Dunning arcsin k1) uses fewer centroids than v1 (simplified
5// parabolic 4q(1-q)) at comparable global accuracy. The memory
6// efficiency is the headline T-Digest property; v2 is supposed to
7// honor it; v1 over-allocates centroids near tails.
8//
9// SHARED WORKLOAD:
10// - Stream: integers 1..2000 in order
11// - Both alloc with delta=100
12//
13// MEASUREMENT AXES:
14// ACCURACY: median + p10 + p90 errors; both should hit ~1% rank;
15// v2 may be slightly worse (looser tail) but must stay
16// within tolerance band
17// MEMORY: n_centroids_used. v2 < v1 expected.
18// TIME: INCONCLUSIVE (no in-program clock)
19//
20// HARD-WIN GATE:
21// MEMORY axis must BEAT v1 by >5% (50000 ppm). Accuracy on
22// median must be EQUIVALENT (not LOSES).
23
24import "syscalls.nx"
25import "sketch_tdigest.nx"
26import "sketch_tdigest_v2.nx"
27import "sketch_comparator.nx"
28import "sketch_types.nx"
29
30func main() -> i64 {
31 let delta: i64 = 100
32
33 let v1: *TDigest = nx_tdigest_alloc(delta)
34 let v2: *TDigestV2 = nx_tdv2_alloc(delta)
35 var i: i64 = 1
36 while i <= 2000 {
37 nx_tdigest_add(v1, i)
38 nx_tdv2_add(v2, i)
39 i = i + 1
40 }
41
42 // Force-flush both so n_centroids reflects final state.
43 let p50_v1: i64 = nx_tdigest_quantile(v1, 500)
44 let p50_v2: i64 = nx_tdv2_quantile(v2, 500)
45 let p10_v1: i64 = nx_tdigest_quantile(v1, 100)
46 let p10_v2: i64 = nx_tdv2_quantile(v2, 100)
47 let p90_v1: i64 = nx_tdigest_quantile(v1, 900)
48 let p90_v2: i64 = nx_tdv2_quantile(v2, 900)
49
50 // ---- MEMORY axis: centroids used ----
51 let n_v1: i64 = nx_tdigest_n_centroids(v1)
52 let n_v2: i64 = nx_tdv2_n_centroids(v2)
53 // 5% tolerance band
54 let mem: *ComparisonResult = nx_cmp_memory(n_v2, n_v1, 50000)
55
56 // ---- ACCURACY at median (truth p50 = 1000) ----
57 let acc_p50: *ComparisonResult = nx_cmp_accuracy(p50_v2, p50_v1, 1000, 20000)
58
59 // ---- TIME axis ----
60 let tim_raw: *u8 = sys_mmap(40)
61 let tim: *ComparisonResult = tim_raw as *ComparisonResult
62 tim.verdict = NX_CMP_VERDICT_INCONCLUSIVE
63 tim.delta_ppm = 0
64 tim.conf_ppb = 500000000
65 tim.axis = NX_CMP_AXIS_TIME
66
67 // ---- HARD-WIN GATE: MEMORY must BEAT ----
68 if mem.verdict != NX_CMP_VERDICT_BEATS {
69 return __syscall(93, 10, 0, 0, 0, 0, 0)
70 }
71 if mem.delta_ppm < 50000 {
72 return __syscall(93, 11, 0, 0, 0, 0, 0)
73 }
74
75 // ---- ACCURACY on median: must NOT LOSE (EQUIVALENT or BEATS OK) ----
76 if acc_p50.verdict == NX_CMP_VERDICT_LOSES {
77 return __syscall(93, 20, 0, 0, 0, 0, 0)
78 }
79
80 // ---- COMPOSITE: must be BEATS or EQUIVALENT (not LOSES) ----
81 let composite: i64 = nx_cmp_composite(acc_p50, mem, tim)
82 if composite == NX_CMP_VERDICT_LOSES {
83 return __syscall(93, 30, 0, 0, 0, 0, 0)
84 }
85 if composite == NX_CMP_VERDICT_INCONCLUSIVE {
86 return __syscall(93, 31, 0, 0, 0, 0, 0)
87 }
88
89 // ---- Per-axis tail accuracy: v1 IS supposed to be tighter at tails ----
90 // (simplified 4q(1-q) over-allocates centroids near tails). We
91 // measure honestly: if v2 LOSES on tail accuracy that's an
92 // EXPECTED trade-off, not a failure. But if v2 LOSES by more
93 // than 5% on p10 or p90, the memory win isn't worth it.
94 let acc_p10: *ComparisonResult = nx_cmp_accuracy(p10_v2, p10_v1, 200, 50000)
95 let acc_p90: *ComparisonResult = nx_cmp_accuracy(p90_v2, p90_v1, 1800, 50000)
96 if acc_p10.verdict == NX_CMP_VERDICT_LOSES {
97 if acc_p10.delta_ppm < -50000 {
98 return __syscall(93, 40, 0, 0, 0, 0, 0)
99 }
100 }
101 if acc_p90.verdict == NX_CMP_VERDICT_LOSES {
102 if acc_p90.delta_ppm < -50000 {
103 return __syscall(93, 41, 0, 0, 0, 0, 0)
104 }
105 }
106
107 // ---- Sanity: total weight matches between v1 and v2 ----
108 if v1.total_weight != v2.total_weight {
109 return __syscall(93, 50, 0, 0, 0, 0, 0)
110 }
111
112 return 0
113}