lib/bench/src/compare/engine.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const pretty_json = @import("pretty").json;
3 const sys = @import("sys");
4
5 const capacity_mod = @import("capacity.zig");
6 const storage_mod = @import("storage.zig");
7
8 const Allocator = std.mem.Allocator;
9
10 pub const Limits = capacity_mod.Limits;
11 pub const Capacity = capacity_mod.Capacity;
12 pub const CapacityError = capacity_mod.DeriveError;
13 pub const Storage = storage_mod.Storage;
14 pub const StorageStatus = storage_mod.Status;
15 pub const StorageExhaustion = storage_mod.Exhaustion;
16 pub const StorageError = storage_mod.Error;
17
18 pub const max_profile_bytes = 64 * 1024 * 1024;
19 pub const default_threshold = 1.05;
20 pub const default_min_runs: u32 = 10;
21 pub const default_bootstrap_iterations: u32 = 1000;
22 pub const bootstrap_seed: u64 = 0x5449_4e59_434f_4d50;
23 pub const confidence_per_mille: u16 = 950;
24 pub const effect_confidence: f64 =
25 @as(f64, @floatFromInt(confidence_per_mille)) / 1000.0;
26 pub const effect_method =
27 "deterministic_percentile_bootstrap_unpaired_execution_median_percent_change";
28
29 pub const Options = struct {
30 baseline_path: []const u8,
31 candidate_path: []const u8,
32 threshold: f64 = default_threshold,
33 min_runs: u32 = default_min_runs,
34 bootstrap_iterations: u32 = default_bootstrap_iterations,
35 };
36
37 pub const Counts = struct {
38 compared: u64 = 0,
39 regressions: u64 = 0,
40 improvements: u64 = 0,
41 unchanged: u64 = 0,
42 uncertain: u64 = 0,
43 insufficient: u64 = 0,
44 missing_baseline: u64 = 0,
45 missing_candidate: u64 = 0,
46 };
47
48 pub const Classification = enum {
49 regression,
50 improvement,
51 unchanged,
52 uncertain,
53 insufficient,
54
55 pub fn jsonName(self: Classification) []const u8 {
56 return switch (self) {
57 .regression => "regression",
58 .improvement => "improvement",
59 .unchanged => "unchanged",
60 .uncertain => "uncertain",
61 .insufficient => "insufficient",
62 };
63 }
64 };
65
66 pub const EffectInterval = struct {
67 low_percent: f64,
68 high_percent: f64,
69 };
70
71 pub const ExecutionObservation = struct {
72 mean: f64,
73 median: f64,
74 };
75
76 pub const ExecutionStats = struct {
77 runs: usize,
78 mean: f64,
79 median: f64,
80 min: f64,
81 max: f64,
82 };
83
84 pub const ExecutionAnalysisOptions = struct {
85 threshold: f64 = default_threshold,
86 min_runs: u32 = default_min_runs,
87 bootstrap_iterations: u32 = default_bootstrap_iterations,
88 };
89
90 pub const ExecutionComparison = struct {
91 classification: Classification,
92 baseline: ExecutionStats,
93 candidate: ExecutionStats,
94 ratio: ?f64,
95 effect: ?EffectInterval,
96 bootstrap_iterations: u32,
97 evidence: []const u8,
98 };
99
100 pub const U64MedianRatio = struct {
101 baseline_median: u64,
102 candidate_median: u64,
103 ratio: f64,
104 low_ratio: f64,
105 high_ratio: f64,
106 };
107
108 pub const parseArgs = parseComparisonArgs;
109
110 fn parseComparisonArgs(args: []const []const u8) !Options {
111 if (args.len < 2) return error.InvalidArguments;
112 if (args[0].len == 0 or args[0][0] == '-') return error.InvalidArguments;
113 if (args[1].len == 0 or args[1][0] == '-') return error.InvalidArguments;
114 var options = Options{
115 .baseline_path = args[0],
116 .candidate_path = args[1],
117 };
118 var threshold_specified = false;
119 var min_runs_specified = false;
120 var bootstrap_iterations_specified = false;
121 var index: usize = 2;
122 while (index < args.len) : (index += 1) {
123 const arg = args[index];
124 if (std.mem.eql(u8, arg, "--threshold")) {
125 if (threshold_specified) return error.InvalidArguments;
126 index += 1;
127 if (index >= args.len) return error.InvalidArguments;
128 options.threshold = parseThreshold(args[index]) catch return error.InvalidArguments;
129 threshold_specified = true;
130 } else if (std.mem.eql(u8, arg, "--min-runs")) {
131 if (min_runs_specified) return error.InvalidArguments;
132 index += 1;
133 if (index >= args.len) return error.InvalidArguments;
134 options.min_runs = std.fmt.parseUnsigned(u32, args[index], 10) catch
135 return error.InvalidArguments;
136 if (options.min_runs == 0) return error.InvalidArguments;
137 min_runs_specified = true;
138 } else if (std.mem.eql(u8, arg, "--bootstrap-iterations")) {
139 if (bootstrap_iterations_specified) return error.InvalidArguments;
140 index += 1;
141 if (index >= args.len) return error.InvalidArguments;
142 options.bootstrap_iterations = std.fmt.parseUnsigned(u32, args[index], 10) catch
143 return error.InvalidArguments;
144 if (options.bootstrap_iterations == 0) return error.InvalidArguments;
145 bootstrap_iterations_specified = true;
146 } else {
147 return error.InvalidArguments;
148 }
149 }
150 return options;
151 }
152
153 fn parseThreshold(text: []const u8) !f64 {
154 const value = try std.fmt.parseFloat(f64, text);
155 if (!std.math.isFinite(value) or value < 1.0) return error.InvalidThreshold;
156 return value;
157 }
158
159 fn assertOptions(options: Options) void {
160 std.debug.assert(options.baseline_path.len > 0);
161 std.debug.assert(options.candidate_path.len > 0);
162 std.debug.assert(std.math.isFinite(options.threshold));
163 std.debug.assert(options.threshold >= 1.0);
164 std.debug.assert(options.min_runs > 0);
165 std.debug.assert(options.bootstrap_iterations > 0);
166 }
167
168 fn RowGroup(comptime Row: type) type {
169 return struct {
170 row: Row,
171 observations: std.ArrayListUnmanaged(ExecutionObservation) = .empty,
172 last_run: u64,
173
174 fn deinit(self: *@This(), allocator: Allocator) void {
175 self.row.deinit(allocator);
176 self.observations.deinit(allocator);
177 self.* = undefined;
178 }
179 };
180 }
181
182 fn RowMap(comptime Row: type) type {
183 return std.StringHashMapUnmanaged(RowGroup(Row));
184 }
185
186 fn RowOrder(comptime Row: type) type {
187 return struct {
188 fn lessThan(_: void, left: *const RowGroup(Row), right: *const RowGroup(Row)) bool {
189 return std.mem.lessThan(u8, left.row.key, right.row.key);
190 }
191 };
192 }
193
194 pub fn SummaryComparison(comptime Spec: type) type {
195 return struct {
196 pub fn runFiles(
197 allocator: Allocator,
198 out: *std.Io.Writer,
199 args: []const []const u8,
200 ) !u8 {
201 return runComparisonFiles(Spec, allocator, out, args);
202 }
203
204 pub fn parseArgs(args: []const []const u8) !Options {
205 return parseComparisonArgs(args);
206 }
207
208 pub fn compareSources(
209 allocator: Allocator,
210 out: *std.Io.Writer,
211 options: Options,
212 baseline_source: []const u8,
213 candidate_source: []const u8,
214 ) !Counts {
215 return compareSummarySources(
216 Spec,
217 allocator,
218 out,
219 options,
220 baseline_source,
221 candidate_source,
222 );
223 }
224 };
225 }
226
227 fn runComparisonFiles(
228 comptime Spec: type,
229 allocator: Allocator,
230 out: *std.Io.Writer,
231 args: []const []const u8,
232 ) !u8 {
233 const options = try parseComparisonArgs(args);
234 const baseline = try sys.fs.readFileAlloc(
235 allocator,
236 options.baseline_path,
237 max_profile_bytes,
238 );
239 defer allocator.free(baseline);
240 const candidate = try sys.fs.readFileAlloc(
241 allocator,
242 options.candidate_path,
243 max_profile_bytes,
244 );
245 defer allocator.free(candidate);
246 _ = try compareSummarySources(Spec, allocator, out, options, baseline, candidate);
247 return 0;
248 }
249
250 fn compareSummarySources(
251 comptime Spec: type,
252 allocator: Allocator,
253 out: *std.Io.Writer,
254 options: Options,
255 baseline_source: []const u8,
256 candidate_source: []const u8,
257 ) !Counts {
258 assertOptions(options);
259 var baseline = try loadRows(Spec, allocator, baseline_source);
260 defer deinitRows(Spec.Row, allocator, &baseline);
261 var candidate = try loadRows(Spec, allocator, candidate_source);
262 defer deinitRows(Spec.Row, allocator, &candidate);
263 return compareRows(Spec, allocator, out, options, &baseline, &candidate);
264 }
265
266 pub fn compareRows(
267 comptime Spec: type,
268 allocator: Allocator,
269 out: *std.Io.Writer,
270 options: Options,
271 baseline: *RowMap(Spec.Row),
272 candidate: *RowMap(Spec.Row),
273 ) !Counts {
274 var counts = Counts{};
275 try writeStart(Spec, out, options, baseline.count(), candidate.count());
276 const baseline_rows = try sortedRowPointers(Spec.Row, allocator, baseline);
277 defer allocator.free(baseline_rows);
278 const candidate_rows = try sortedRowPointers(Spec.Row, allocator, candidate);
279 defer allocator.free(candidate_rows);
280 const max_samples = @max(
281 maxRowSamples(Spec.Row, baseline_rows),
282 maxRowSamples(Spec.Row, candidate_rows),
283 );
284 var comparison_storage: ?Storage = if (max_samples == 0)
285 null
286 else
287 try Storage.init(allocator, .{
288 .max_samples_per_series = max_samples,
289 .max_bootstrap_iterations = options.bootstrap_iterations,
290 });
291 defer if (comparison_storage) |*storage| storage.deinit(allocator);
292 if (comparison_storage) |*storage| storage.activate();
293
294 for (baseline_rows) |base| {
295 if (candidate.getPtr(base.row.key)) |cand| {
296 if (@hasDecl(Spec, "validatePair")) {
297 try Spec.validatePair(base.row, cand.row);
298 }
299 std.debug.assert(comparison_storage != null);
300 const result = try analyzeExecutions(
301 &comparison_storage.?,
302 base.observations.items,
303 cand.observations.items,
304 .{
305 .threshold = options.threshold,
306 .min_runs = options.min_runs,
307 .bootstrap_iterations = options.bootstrap_iterations,
308 },
309 );
310 recordClassification(&counts, result.classification);
311 try writeComparison(Spec, out, base.row, cand.row, result);
312 } else {
313 counts.missing_candidate += 1;
314 std.debug.assert(comparison_storage != null);
315 try writeMissing(Spec, &comparison_storage.?, out, "candidate", base.*);
316 }
317 }
318 for (candidate_rows) |cand| {
319 if (baseline.contains(cand.row.key)) continue;
320 counts.missing_baseline += 1;
321 std.debug.assert(comparison_storage != null);
322 try writeMissing(Spec, &comparison_storage.?, out, "baseline", cand.*);
323 }
324 try writeEnd(Spec, out, options, counts);
325 return counts;
326 }
327
328 fn maxRowSamples(
329 comptime Row: type,
330 rows: []const *const RowGroup(Row),
331 ) usize {
332 var max_samples: usize = 0;
333 for (rows) |row| max_samples = @max(max_samples, row.observations.items.len);
334 return max_samples;
335 }
336
337 pub fn loadRows(
338 comptime Spec: type,
339 allocator: Allocator,
340 source: []const u8,
341 ) !RowMap(Spec.Row) {
342 var map: RowMap(Spec.Row) = .{};
343 errdefer deinitRows(Spec.Row, allocator, &map);
344 var run_open = false;
345 var run_count: u64 = 0;
346 var run_summaries: u64 = 0;
347 var lines = std.mem.splitScalar(u8, source, '\n');
348 while (lines.next()) |raw_line| {
349 const line = std.mem.trim(u8, raw_line, " \t\r\n");
350 if (line.len == 0) continue;
351 var parsed = parseJsonLine(allocator, line) catch |err| switch (err) {
352 error.OutOfMemory => return err,
353 else => return error.InvalidProfileJsonl,
354 };
355 defer parsed.deinit();
356 const object = switch (parsed.value) {
357 .object => |object| object,
358 else => return error.InvalidProfileJsonl,
359 };
360 const kind = objectStringOptional(object, "kind") orelse continue;
361 const benchmark = objectStringOptional(object, "benchmark") orelse "";
362 if (!std.mem.eql(u8, benchmark, Spec.benchmark_name)) continue;
363 if (std.mem.eql(u8, kind, "run")) {
364 const was_open = run_open;
365 try updateRunState(object, &run_open, &run_count);
366 if (!was_open and run_open) run_summaries = 0;
367 if (was_open and !run_open and run_summaries == 0) {
368 return error.MissingSummaryInRun;
369 }
370 } else if (std.mem.eql(u8, kind, "summary")) {
371 if (!run_open) return error.MissingRunStart;
372 try appendSummary(Spec, allocator, &map, object, run_count);
373 run_summaries = std.math.add(u64, run_summaries, 1) catch
374 return error.TooManySummaries;
375 }
376 }
377 if (run_open) return error.MissingRunEnd;
378 if (run_count == 0) return error.MissingRunStart;
379 std.debug.assert(run_count <= source.len);
380 return map;
381 }
382
383 fn appendSummary(
384 comptime Spec: type,
385 allocator: Allocator,
386 map: *RowMap(Spec.Row),
387 object: std.json.ObjectMap,
388 run: u64,
389 ) !void {
390 var row = try Spec.parseRow(allocator, object);
391 var row_owned = true;
392 defer if (row_owned) row.deinit(allocator);
393 if (map.getPtr(row.key)) |group| {
394 if (group.last_run == run) return error.DuplicateSummaryInRun;
395 std.debug.assert(group.last_run < run);
396 if (@hasDecl(Spec, "validateRepeat")) {
397 try Spec.validateRepeat(group.row, row);
398 }
399 try group.observations.append(allocator, observation(row));
400 group.last_run = run;
401 return;
402 }
403
404 var observations: std.ArrayListUnmanaged(ExecutionObservation) = .empty;
405 errdefer observations.deinit(allocator);
406 try observations.append(allocator, observation(row));
407 try map.put(allocator, row.key, .{
408 .row = row,
409 .observations = observations,
410 .last_run = run,
411 });
412 row_owned = false;
413 }
414
415 fn sortedRowPointers(
416 comptime Row: type,
417 allocator: Allocator,
418 map: *RowMap(Row),
419 ) ![]*const RowGroup(Row) {
420 const rows = try allocator.alloc(*const RowGroup(Row), map.count());
421 var index: usize = 0;
422 var iter = map.valueIterator();
423 while (iter.next()) |row| {
424 rows[index] = row;
425 index += 1;
426 }
427 std.debug.assert(index == rows.len);
428 std.mem.sort(*const RowGroup(Row), rows, {}, RowOrder(Row).lessThan);
429 return rows;
430 }
431
432 pub fn deinitRows(
433 comptime Row: type,
434 allocator: Allocator,
435 map: *RowMap(Row),
436 ) void {
437 var iter = map.valueIterator();
438 while (iter.next()) |row| row.deinit(allocator);
439 map.deinit(allocator);
440 }
441
442 fn writeStart(
443 comptime Spec: type,
444 out: *std.Io.Writer,
445 options: Options,
446 baseline_count: usize,
447 candidate_count: usize,
448 ) !void {
449 var stream = pretty_json.Writer.init(out, .minified);
450 const object = try stream.object();
451 try object.field("kind", "compare");
452 try object.field("benchmark", Spec.benchmark_name);
453 try object.field("protocol", Spec.protocol_name);
454 try object.field("event", "start");
455 try object.field("baseline", options.baseline_path);
456 try object.field("candidate", options.candidate_path);
457 try object.field("threshold", options.threshold);
458 try object.field("minimum_runs", options.min_runs);
459 try object.field("confidence", effect_confidence);
460 try object.field("bootstrap_iterations", options.bootstrap_iterations);
461 try object.field("effect_method", effect_method);
462 try object.field("baseline_summaries", baseline_count);
463 try object.field("candidate_summaries", candidate_count);
464 try object.endLine();
465 }
466
467 fn writeComparison(
468 comptime Spec: type,
469 out: *std.Io.Writer,
470 baseline: Spec.Row,
471 candidate: Spec.Row,
472 result: ExecutionComparison,
473 ) !void {
474 var stream = pretty_json.Writer.init(out, .minified);
475 const object = try stream.object();
476 try object.field("kind", "comparison");
477 try object.field("benchmark", Spec.benchmark_name);
478 try object.field("summary", baseline.summary);
479 try object.field("name", baseline.name);
480 try Spec.writeIdentity(object, baseline);
481 try object.field("classification", result.classification.jsonName());
482 try object.field("evidence", result.evidence);
483 try writeExecutionFields(object, result);
484 if (@hasDecl(Spec, "writeComparisonExtra")) {
485 try Spec.writeComparisonExtra(object, baseline, candidate);
486 }
487 try object.endLine();
488 }
489
490 fn writeExecutionFields(
491 object: pretty_json.Object,
492 result: ExecutionComparison,
493 ) !void {
494 try object.field("baseline_runs", result.baseline.runs);
495 try object.field("candidate_runs", result.candidate.runs);
496 try object.field("baseline_mean", result.baseline.mean);
497 try object.field("candidate_mean", result.candidate.mean);
498 try object.field("delta", result.candidate.mean - result.baseline.mean);
499 try object.field("baseline_median", result.baseline.median);
500 try object.field("candidate_median", result.candidate.median);
501 try object.field(
502 "median_delta",
503 result.candidate.median - result.baseline.median,
504 );
505 try object.field("baseline_min", result.baseline.min);
506 try object.field("candidate_min", result.candidate.min);
507 try object.field("baseline_max", result.baseline.max);
508 try object.field("candidate_max", result.candidate.max);
509 try object.field("ratio", result.ratio);
510 try writeEffect(object, result.effect, result.bootstrap_iterations);
511 }
512
513 fn writeMissing(
514 comptime Spec: type,
515 storage: *Storage,
516 out: *std.Io.Writer,
517 missing: []const u8,
518 group: RowGroup(Spec.Row),
519 ) !void {
520 const execution = try summarizeExecutions(storage, group.observations.items);
521 var stream = pretty_json.Writer.init(out, .minified);
522 const object = try stream.object();
523 try object.field("kind", "missing");
524 try object.field("benchmark", Spec.benchmark_name);
525 try object.field("missing", missing);
526 try object.field("summary", group.row.summary);
527 try object.field("name", group.row.name);
528 try Spec.writeIdentity(object, group.row);
529 if (@hasDecl(Spec, "writeMissingExtra")) {
530 try Spec.writeMissingExtra(object, group.row);
531 }
532 try object.field("runs", execution.runs);
533 try object.field("mean", execution.mean);
534 try object.field("median", execution.median);
535 try object.endLine();
536 }
537
538 fn writeEnd(
539 comptime Spec: type,
540 out: *std.Io.Writer,
541 options: Options,
542 counts: Counts,
543 ) !void {
544 var stream = pretty_json.Writer.init(out, .minified);
545 const object = try stream.object();
546 try object.field("kind", "compare");
547 try object.field("benchmark", Spec.benchmark_name);
548 try object.field("protocol", Spec.protocol_name);
549 try object.field("event", "end");
550 try object.field("baseline", options.baseline_path);
551 try object.field("candidate", options.candidate_path);
552 try object.field("threshold", options.threshold);
553 try object.field("minimum_runs", options.min_runs);
554 try object.field("compared", counts.compared);
555 try object.field("regressions", counts.regressions);
556 try object.field("improvements", counts.improvements);
557 try object.field("unchanged", counts.unchanged);
558 try object.field("uncertain", counts.uncertain);
559 try object.field("insufficient", counts.insufficient);
560 try object.field("missing_baseline", counts.missing_baseline);
561 try object.field("missing_candidate", counts.missing_candidate);
562 try object.endLine();
563 }
564
565 fn parseJsonLine(
566 allocator: Allocator,
567 line: []const u8,
568 ) !std.json.Parsed(std.json.Value) {
569 return std.json.parseFromSlice(std.json.Value, allocator, line, .{});
570 }
571
572 fn updateRunState(
573 object: std.json.ObjectMap,
574 run_open: *bool,
575 run_count: *u64,
576 ) !void {
577 const run_event = objectStringOptional(object, "event") orelse
578 return error.InvalidRunEvent;
579 if (std.mem.eql(u8, run_event, "start")) {
580 if (run_open.*) return error.NestedRun;
581 run_count.* = std.math.add(u64, run_count.*, 1) catch return error.TooManyRuns;
582 run_open.* = true;
583 } else if (std.mem.eql(u8, run_event, "end")) {
584 if (!run_open.*) return error.UnmatchedRunEnd;
585 run_open.* = false;
586 } else {
587 return error.InvalidRunEvent;
588 }
589 }
590
591 fn observation(row: anytype) ExecutionObservation {
592 return .{ .mean = row.mean, .median = row.median };
593 }
594
595 pub fn analyzeExecutions(
596 storage: *Storage,
597 baseline: []const ExecutionObservation,
598 candidate: []const ExecutionObservation,
599 options: ExecutionAnalysisOptions,
600 ) !ExecutionComparison {
601 if (!std.math.isFinite(options.threshold) or options.threshold < 1.0) {
602 return error.InvalidThreshold;
603 }
604 if (options.min_runs == 0) return error.InvalidMinimumRuns;
605 if (options.bootstrap_iterations == 0) return error.InvalidBootstrapIterations;
606 if (baseline.len == 0 or candidate.len == 0) return error.EmptyExecutionSet;
607 const regions = try storage.acquireF64(
608 baseline.len,
609 candidate.len,
610 options.bootstrap_iterations,
611 );
612 defer storage.reset();
613 const baseline_stats = try summarizeExecutionsInScratch(
614 baseline,
615 regions.samples[0..baseline.len],
616 );
617 const candidate_stats = try summarizeExecutionsInScratch(
618 candidate,
619 regions.samples[0..candidate.len],
620 );
621 const ratio = ratioOrNull(baseline_stats.median, candidate_stats.median);
622 const enough = baseline.len >= options.min_runs and candidate.len >= options.min_runs;
623 const effect = if (enough)
624 try bootstrapMedianPercentChange(baseline, candidate, regions)
625 else
626 null;
627 return .{
628 .classification = classifyChange(effect, enough, options.threshold),
629 .baseline = baseline_stats,
630 .candidate = candidate_stats,
631 .ratio = ratio,
632 .effect = effect,
633 .bootstrap_iterations = options.bootstrap_iterations,
634 .evidence = evidenceState(enough, effect),
635 };
636 }
637
638 pub fn analyzeU64Medians(
639 storage: *Storage,
640 baseline: []const u64,
641 candidate: []const u64,
642 bootstrap_iterations: u32,
643 seed: u64,
644 ) StorageError!U64MedianRatio {
645 const regions = try storage.acquireU64(
646 baseline.len,
647 candidate.len,
648 bootstrap_iterations,
649 );
650 defer storage.reset();
651 const baseline_values = canonicalU64(baseline, regions.samples[0..baseline.len]);
652 const baseline_median = upperMedianU64(baseline_values);
653 const candidate_values = canonicalU64(candidate, regions.samples[0..candidate.len]);
654 const candidate_median = upperMedianU64(candidate_values);
655 var prng = std.Random.DefaultPrng.init(seed);
656 const random = prng.random();
657 const bootstrap_baseline = canonicalU64(baseline, regions.samples[0..baseline.len]);
658 fillBootstrapU64Medians(
659 regions.effects,
660 bootstrap_baseline,
661 regions.counts[0..baseline.len],
662 random,
663 );
664 const bootstrap_candidate = canonicalU64(candidate, regions.samples[0..candidate.len]);
665 for (regions.effects) |*ratio| {
666 const candidate_value = bootstrapU64Median(
667 bootstrap_candidate,
668 regions.counts[0..candidate.len],
669 random,
670 );
671 ratio.* = u64RatioFloat(candidate_value, ratio.*);
672 }
673 std.mem.sort(f64, regions.effects, {}, std.sort.asc(f64));
674 const low_index = ratioQuantileIndex(regions.effects.len, 25);
675 const high_index = ratioQuantileIndex(regions.effects.len, 975);
676 return .{
677 .baseline_median = baseline_median,
678 .candidate_median = candidate_median,
679 .ratio = u64Ratio(candidate_median, baseline_median),
680 .low_ratio = regions.effects[@min(low_index, regions.effects.len - 1)],
681 .high_ratio = regions.effects[@min(high_index, regions.effects.len - 1)],
682 };
683 }
684
685 pub fn summarizeExecutions(
686 storage: *Storage,
687 observations: []const ExecutionObservation,
688 ) !ExecutionStats {
689 if (observations.len == 0) return error.EmptyExecutionSet;
690 const scratch = try storage.acquireF64Samples(observations.len);
691 defer storage.reset();
692 return summarizeExecutionsInScratch(observations, scratch);
693 }
694
695 fn summarizeExecutionsInScratch(
696 observations: []const ExecutionObservation,
697 scratch: []f64,
698 ) !ExecutionStats {
699 std.debug.assert(observations.len > 0);
700 std.debug.assert(scratch.len >= observations.len);
701 for (observations) |item| {
702 if (!std.math.isFinite(item.mean) or !std.math.isFinite(item.median) or
703 item.mean < 0 or item.median < 0)
704 {
705 return error.InvalidSummary;
706 }
707 }
708 const values = scratch[0..observations.len];
709 for (observations, values) |item, *value| value.* = canonicalZero(item.mean);
710 std.mem.sort(f64, values, {}, std.sort.asc(f64));
711 var execution_mean: f64 = 0;
712 for (values, 0..) |value, index| {
713 const count: f64 = @floatFromInt(index + 1);
714 execution_mean += (value - execution_mean) / count;
715 }
716 for (observations, values) |item, *value| value.* = canonicalZero(item.median);
717 std.mem.sort(f64, values, {}, std.sort.asc(f64));
718 return .{
719 .runs = observations.len,
720 .mean = execution_mean,
721 .median = medianSorted(values),
722 .min = values[0],
723 .max = values[values.len - 1],
724 };
725 }
726
727 fn canonicalZero(value: f64) f64 {
728 return if (value == 0) 0 else value;
729 }
730
731 pub fn classifyChange(
732 effect: ?EffectInterval,
733 enough: bool,
734 threshold: f64,
735 ) Classification {
736 if (!enough) return .insufficient;
737 const actual_effect = effect orelse return .uncertain;
738 const regression_percent = threshold * 100.0 - 100.0;
739 const improvement_percent = 100.0 / threshold - 100.0;
740 if (threshold == 1.0) {
741 if (actual_effect.low_percent > 0) return .regression;
742 if (actual_effect.high_percent < 0) return .improvement;
743 if (actual_effect.low_percent == 0 and actual_effect.high_percent == 0) {
744 return .unchanged;
745 }
746 return .uncertain;
747 }
748 if (actual_effect.low_percent >= regression_percent) return .regression;
749 if (actual_effect.high_percent <= improvement_percent) return .improvement;
750 if (actual_effect.low_percent > improvement_percent and
751 actual_effect.high_percent < regression_percent)
752 {
753 return .unchanged;
754 }
755 return .uncertain;
756 }
757
758 fn recordClassification(counts: *Counts, classification: Classification) void {
759 counts.compared += 1;
760 switch (classification) {
761 .regression => counts.regressions += 1,
762 .improvement => counts.improvements += 1,
763 .unchanged => counts.unchanged += 1,
764 .uncertain => counts.uncertain += 1,
765 .insufficient => counts.insufficient += 1,
766 }
767 }
768
769 fn evidenceState(enough: bool, effect: ?EffectInterval) []const u8 {
770 if (!enough) return "insufficient_execution_runs";
771 if (effect == null) return "effect_interval_unavailable";
772 return "execution_run_effect_interval";
773 }
774
775 fn ratioOrNull(baseline: f64, candidate: f64) ?f64 {
776 if (baseline == 0) return null;
777 const ratio = candidate / baseline;
778 return if (std.math.isFinite(ratio)) ratio else null;
779 }
780
781 fn bootstrapMedianPercentChange(
782 baseline: []const ExecutionObservation,
783 candidate: []const ExecutionObservation,
784 regions: storage_mod.F64Regions,
785 ) !?EffectInterval {
786 if (baseline.len == 0 or candidate.len == 0) return null;
787 var prng = std.Random.DefaultPrng.init(bootstrap_seed);
788 const random = prng.random();
789 const baseline_values = canonicalMedians(regions.samples, baseline);
790 fillBootstrapMedians(
791 regions.effects,
792 baseline_values,
793 regions.counts[0..baseline.len],
794 random,
795 );
796 const candidate_values = canonicalMedians(regions.samples, candidate);
797 for (regions.effects) |*change| {
798 const baseline_median = change.*;
799 if (baseline_median == 0) return null;
800 const candidate_median = bootstrapMedian(
801 candidate_values,
802 regions.counts[0..candidate.len],
803 random,
804 );
805 const ratio = candidate_median / baseline_median;
806 if (!std.math.isFinite(ratio)) return null;
807 change.* = ratio * 100.0 - 100.0;
808 if (!std.math.isFinite(change.*)) return null;
809 }
810 std.mem.sort(f64, regions.effects, {}, std.sort.asc(f64));
811 const tail: u16 = @intCast((1000 - confidence_per_mille) / 2);
812 return .{
813 .low_percent = quantilePerMille(regions.effects, tail, .lower),
814 .high_percent = quantilePerMille(regions.effects, 1000 - tail, .upper),
815 };
816 }
817
818 fn canonicalMedians(
819 output: []f64,
820 observations: []const ExecutionObservation,
821 ) []const f64 {
822 std.debug.assert(observations.len > 0);
823 std.debug.assert(output.len >= observations.len);
824 const values = output[0..observations.len];
825 for (observations, values) |item, *value| value.* = canonicalZero(item.median);
826 std.mem.sort(f64, values, {}, std.sort.asc(f64));
827 return values;
828 }
829
830 fn fillBootstrapMedians(
831 output: []f64,
832 sorted: []const f64,
833 counts: []u32,
834 random: std.Random,
835 ) void {
836 std.debug.assert(output.len > 0);
837 std.debug.assert(sorted.len == counts.len);
838 for (output) |*value| value.* = bootstrapMedian(sorted, counts, random);
839 }
840
841 fn bootstrapMedian(sorted: []const f64, counts: []u32, random: std.Random) f64 {
842 std.debug.assert(sorted.len > 0);
843 std.debug.assert(sorted.len == counts.len);
844 @memset(counts, 0);
845 for (0..sorted.len) |_| {
846 const index = random.intRangeLessThan(usize, 0, sorted.len);
847 counts[index] += 1;
848 }
849 return weightedMedian(sorted, counts);
850 }
851
852 fn weightedMedian(sorted: []const f64, counts: []const u32) f64 {
853 std.debug.assert(sorted.len > 0);
854 std.debug.assert(sorted.len == counts.len);
855 const low_rank = (sorted.len - 1) / 2;
856 const high_rank = sorted.len / 2;
857 var low: ?f64 = null;
858 var seen: usize = 0;
859 for (sorted, counts) |value, count| {
860 seen += count;
861 if (low == null and seen > low_rank) low = value;
862 if (seen > high_rank) return low.? + (value - low.?) / 2.0;
863 }
864 unreachable;
865 }
866
867 fn canonicalU64(values: []const u64, output: []u64) []const u64 {
868 std.debug.assert(values.len > 0);
869 std.debug.assert(values.len == output.len);
870 @memcpy(output, values);
871 std.mem.sort(u64, output, {}, std.sort.asc(u64));
872 return output;
873 }
874
875 fn upperMedianU64(sorted: []const u64) u64 {
876 std.debug.assert(sorted.len > 0);
877 return sorted[sorted.len / 2];
878 }
879
880 fn fillBootstrapU64Medians(
881 output: []f64,
882 sorted: []const u64,
883 counts: []u32,
884 random: std.Random,
885 ) void {
886 std.debug.assert(output.len > 0);
887 std.debug.assert(sorted.len == counts.len);
888 for (output) |*value| {
889 value.* = @floatFromInt(bootstrapU64Median(sorted, counts, random));
890 }
891 }
892
893 fn bootstrapU64Median(
894 sorted: []const u64,
895 counts: []u32,
896 random: std.Random,
897 ) u64 {
898 std.debug.assert(sorted.len > 0);
899 std.debug.assert(sorted.len == counts.len);
900 @memset(counts, 0);
901 for (0..sorted.len) |_| {
902 const index = random.intRangeLessThan(usize, 0, sorted.len);
903 counts[index] += 1;
904 }
905 const target = sorted.len / 2;
906 var seen: usize = 0;
907 for (sorted, counts) |value, count| {
908 seen += count;
909 if (seen > target) return value;
910 }
911 unreachable;
912 }
913
914 fn u64Ratio(candidate_median: u64, baseline_median: u64) f64 {
915 if (baseline_median == 0) return std.math.inf(f64);
916 return @as(f64, @floatFromInt(candidate_median)) /
917 @as(f64, @floatFromInt(baseline_median));
918 }
919
920 fn u64RatioFloat(candidate_median: u64, baseline_median: f64) f64 {
921 if (baseline_median == 0) return std.math.inf(f64);
922 return @as(f64, @floatFromInt(candidate_median)) / baseline_median;
923 }
924
925 const QuantileSide = enum {
926 lower,
927 upper,
928 };
929
930 fn quantilePerMille(sorted: []const f64, per_mille: u16, side: QuantileSide) f64 {
931 std.debug.assert(sorted.len > 0);
932 const numerator = @as(u128, sorted.len - 1) * per_mille;
933 const index: u128 = switch (side) {
934 .lower => numerator / 1000,
935 .upper => (numerator + 999) / 1000,
936 };
937 return sorted[@intCast(@min(index, sorted.len - 1))];
938 }
939
940 fn ratioQuantileIndex(len: usize, per_mille: u16) usize {
941 std.debug.assert(len > 0);
942 std.debug.assert(per_mille < 1000);
943 return @intCast((@as(u128, len) * per_mille) / 1000);
944 }
945
946 fn medianSorted(sorted: []const f64) f64 {
947 std.debug.assert(sorted.len > 0);
948 const middle = sorted.len / 2;
949 if (sorted.len % 2 == 1) return sorted[middle];
950 return sorted[middle - 1] + (sorted[middle] - sorted[middle - 1]) / 2.0;
951 }
952
953 fn writeEffect(
954 object: pretty_json.Object,
955 effect: ?EffectInterval,
956 bootstrap_iterations: u32,
957 ) !void {
958 try object.field(
959 "effect_low_percent",
960 if (effect) |value| value.low_percent else null,
961 );
962 try object.field(
963 "effect_high_percent",
964 if (effect) |value| value.high_percent else null,
965 );
966 try object.field("effect_confidence", effect_confidence);
967 try object.field("effect_bootstrap_iterations", bootstrap_iterations);
968 try object.field("effect_method", effect_method);
969 }
970
971 pub fn duplicateObjectString(
972 allocator: Allocator,
973 object: std.json.ObjectMap,
974 key: []const u8,
975 ) ![]u8 {
976 const text = objectStringOptional(object, key) orelse return error.InvalidSummary;
977 return try allocator.dupe(u8, text);
978 }
979
980 pub fn objectStringOptional(object: std.json.ObjectMap, key: []const u8) ?[]const u8 {
981 const value = object.get(key) orelse return null;
982 return switch (value) {
983 .string => |text| text,
984 else => null,
985 };
986 }
987
988 pub fn objectU64(object: std.json.ObjectMap, key: []const u8) !u64 {
989 const value = object.get(key) orelse return error.InvalidSummary;
990 return switch (value) {
991 .integer => |integer| if (integer < 0) error.InvalidSummary else @intCast(integer),
992 .number_string => |text| std.fmt.parseUnsigned(u64, text, 10) catch
993 return error.InvalidSummary,
994 else => error.InvalidSummary,
995 };
996 }
997
998 pub fn objectNumberOptional(object: std.json.ObjectMap, key: []const u8) ?f64 {
999 const value = object.get(key) orelse return null;
1000 const number: f64 = switch (value) {
1001 .integer => |integer| @floatFromInt(integer),
1002 .float => |float| float,
1003 .number_string => |text| std.fmt.parseFloat(f64, text) catch return null,
1004 else => return null,
1005 };
1006 return if (std.math.isFinite(number)) number else null;
1007 }
1008
1009 pub fn objectBoolDefault(
1010 object: std.json.ObjectMap,
1011 key: []const u8,
1012 default: bool,
1013 ) !bool {
1014 const value = object.get(key) orelse return default;
1015 return switch (value) {
1016 .bool => |actual| actual,
1017 else => error.InvalidSummary,
1018 };
1019 }