nx_bench_stats.nx source
↩ module page · 192 lines · 5245 B
1// nx_bench_stats.nx -- min/max/mean/p50/p95 stats over an i64 sample array.
2//
3// Substrate-honest distribution primitive. Single-point benchmarks
4// hide variance; this primitive computes the standard min/max/p50/p95
5// quartet operators need to claim "Nishi runs in P ms p50 / Q ms p95".
6//
7// V1 ships insertion-sort + linear-pass stats. Designed for small N
8// (10-100 samples); larger N should use a quickselect primitive
9// (queued). The sort is in-place + destructive -- caller-supplied
10// sample array gets sorted.
11
12import "nx_syscalls.nx"
13import "nx_tier.nx"
14
15// ===== Sealed verdict ===========================================
16
17const NX_BST_OK: nx_int = 0
18const NX_BST_NULL_SAMPLES: nx_int = 1
19const NX_BST_NULL_OUT: nx_int = 2
20const NX_BST_EMPTY: nx_int = 3
21const NX_BST_INVALID: nx_int = 4
22const NX_BST_N: nx_int = 5
23
24func nx_bst_v_is_valid(v: nx_int) -> nx_int {
25 if v < 0 { return 0 }
26 if v >= NX_BST_N { return 0 }
27 return 1
28}
29
30// ===== Struct: NxBenchStats =====================================
31
32struct NxBenchStats {
33 n: nx_int,
34 min: i64,
35 max: i64,
36 sum: i64,
37 mean: i64,
38 p50: i64,
39 p95: i64,
40 stddev_q10: i64,
41}
42
43const NX_BST_BYTES: nx_int = 64 // 8 fields * 8
44
45func nx_bst_new() -> *NxBenchStats {
46 let raw: *u8 = sys_mmap(NX_BST_BYTES)
47 let s: *NxBenchStats = raw as *NxBenchStats
48 s.n = 0
49 s.min = 0
50 s.max = 0
51 s.sum = 0
52 s.mean = 0
53 s.p50 = 0
54 s.p95 = 0
55 s.stddev_q10 = 0
56 return s
57}
58
59// ===== In-place insertion sort ==================================
60//
61// O(n^2); fine for n in [10, 100]. Sorts ascending.
62
63func _bst_insertion_sort(samples: *i64, n: nx_int) -> nx_int {
64 var i: nx_int = 1
65 while i < n {
66 let key: i64 = samples[i]
67 var j: nx_int = i - 1
68 // Shift elements >= key one position right
69 var done: nx_int = 0
70 while done == 0 {
71 if j < 0 { done = 1 }
72 if done == 0 {
73 if samples[j] <= key { done = 1 }
74 }
75 if done == 0 {
76 samples[j + 1] = samples[j]
77 j = j - 1
78 }
79 }
80 samples[j + 1] = key
81 i = i + 1
82 }
83 return 0
84}
85
86// ===== Compute stats ============================================
87//
88// MUTATES the samples array (sorts in place). Caller can use sorted
89// samples afterward for additional analysis.
90
91func nx_bench_stats_compute(samples: *i64, n: nx_int,
92 out: *NxBenchStats) -> nx_int {
93 if (samples as i64) == 0 { return NX_BST_NULL_SAMPLES }
94 if (out as i64) == 0 { return NX_BST_NULL_OUT }
95 if n <= 0 { return NX_BST_EMPTY }
96
97 // Sort first; min = samples[0], max = samples[n-1]
98 _bst_insertion_sort(samples, n)
99 out.n = n
100 out.min = samples[0]
101 out.max = samples[n - 1]
102
103 // Sum + mean
104 var sum: i64 = 0
105 var i: nx_int = 0
106 while i < n {
107 sum = sum + samples[i]
108 i = i + 1
109 }
110 out.sum = sum
111 out.mean = sum / (n as i64)
112
113 // p50 (median): index = n/2 in 0-based sorted array
114 out.p50 = samples[n / 2]
115
116 // p95: index = floor(0.95 * (n-1))
117 let p95_idx: nx_int = (95 * (n - 1)) / 100
118 out.p95 = samples[p95_idx]
119
120 // Standard deviation in Q10 (1024 == 1.0). Computed as:
121 // variance = sum((x - mean)^2) / n
122 // stddev_q10 = isqrt(variance) * Q10_factor
123 // V1 ships variance only (stddev_q10 = isqrt of variance, no
124 // Q-scaling) since the absolute number suffices for cross-run
125 // comparison. Future v2 adds Q-scaling.
126 var var_sum: i64 = 0
127 var k: nx_int = 0
128 while k < n {
129 let d: i64 = samples[k] - out.mean
130 var_sum = var_sum + (d * d)
131 k = k + 1
132 }
133 let variance: i64 = var_sum / (n as i64)
134 // Integer sqrt via Newton (16 iters; converges fast for i64)
135 var sq: i64 = variance
136 if sq < 0 { sq = 0 }
137 if sq == 0 {
138 out.stddev_q10 = 0
139 }
140 if sq > 0 {
141 var r: i64 = sq
142 // initial guess
143 if r > 1 { r = r / 2 + 1 }
144 var iter: nx_int = 0
145 while iter < 24 {
146 let next_r: i64 = (r + sq / r) / 2
147 if next_r >= r { iter = 24 }
148 if next_r < r { r = next_r }
149 iter = iter + 1
150 }
151 out.stddev_q10 = r
152 }
153
154 return NX_BST_OK
155}
156
157// ===== Accessors ================================================
158
159func nx_bst_min(s: *NxBenchStats) -> i64 {
160 if (s as i64) == 0 { return 0 }
161 return s.min
162}
163
164func nx_bst_max(s: *NxBenchStats) -> i64 {
165 if (s as i64) == 0 { return 0 }
166 return s.max
167}
168
169func nx_bst_mean(s: *NxBenchStats) -> i64 {
170 if (s as i64) == 0 { return 0 }
171 return s.mean
172}
173
174func nx_bst_p50(s: *NxBenchStats) -> i64 {
175 if (s as i64) == 0 { return 0 }
176 return s.p50
177}
178
179func nx_bst_p95(s: *NxBenchStats) -> i64 {
180 if (s as i64) == 0 { return 0 }
181 return s.p95
182}
183
184func nx_bst_stddev(s: *NxBenchStats) -> i64 {
185 if (s as i64) == 0 { return 0 }
186 return s.stddev_q10
187}
188
189func nx_bst_n(s: *NxBenchStats) -> nx_int {
190 if (s as i64) == 0 { return 0 }
191 return s.n
192}