lib/bench/src/stats/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 pub const storage_alignment: usize = @max(@alignOf(u64), @alignOf(f64));
4
5 pub const Limits = struct {
6 samples: usize,
7 bootstrap_iterations: u32 = @import("model.zig").default_bootstrap_iterations,
8 };
9
10 pub const DeriveError = error{
11 InvalidSampleLimit,
12 SampleLimitTooLarge,
13 CapacityOverflow,
14 };
15
16 pub const Capacity = struct {
17 limits: Limits,
18 sorted_offset: usize,
19 means_offset: usize,
20 medians_offset: usize,
21 p75s_offset: usize,
22 p95s_offset: usize,
23 p99s_offset: usize,
24 counts_offset: usize,
25 storage_bytes: usize,
26
27 pub fn derive(limits: Limits) DeriveError!Capacity {
28 if (limits.samples == 0) return error.InvalidSampleLimit;
29 if (limits.samples > std.math.maxInt(u32)) return error.SampleLimitTooLarge;
30
31 const sorted = try placed(u64, 0, limits.samples);
32 const means = try placed(f64, sorted.end, limits.bootstrap_iterations);
33 const medians = try placed(f64, means.end, limits.bootstrap_iterations);
34 const p75s = try placed(f64, medians.end, limits.bootstrap_iterations);
35 const p95s = try placed(f64, p75s.end, limits.bootstrap_iterations);
36 const p99s = try placed(f64, p95s.end, limits.bootstrap_iterations);
37 const counts = try placed(u32, p99s.end, limits.samples);
38 std.debug.assert(sorted.start == 0);
39 std.debug.assert(sorted.end <= means.start);
40 std.debug.assert(means.end <= medians.start);
41 std.debug.assert(medians.end <= p75s.start);
42 std.debug.assert(p75s.end <= p95s.start);
43 std.debug.assert(p95s.end <= p99s.start);
44 std.debug.assert(p99s.end <= counts.start);
45 return .{
46 .limits = limits,
47 .sorted_offset = sorted.start,
48 .means_offset = means.start,
49 .medians_offset = medians.start,
50 .p75s_offset = p75s.start,
51 .p95s_offset = p95s.start,
52 .p99s_offset = p99s.start,
53 .counts_offset = counts.start,
54 .storage_bytes = counts.end,
55 };
56 }
57 };
58
59 const Region = struct {
60 start: usize,
61 end: usize,
62 };
63
64 fn placed(comptime T: type, offset: usize, count: usize) DeriveError!Region {
65 const mask: usize = @alignOf(T) - 1;
66 const padded = std.math.add(usize, offset, mask) catch return error.CapacityOverflow;
67 const start = padded & ~mask;
68 const bytes = std.math.mul(usize, count, @sizeOf(T)) catch return error.CapacityOverflow;
69 return .{
70 .start = start,
71 .end = std.math.add(usize, start, bytes) catch return error.CapacityOverflow,
72 };
73 }
74
75 fn modelCapacity(limits: Limits) DeriveError!Capacity {
76 if (limits.samples == 0) return error.InvalidSampleLimit;
77 if (limits.samples > std.math.maxInt(u32)) return error.SampleLimitTooLarge;
78 const samples: u128 = limits.samples;
79 const iterations: u128 = limits.bootstrap_iterations;
80 const sorted_offset: u128 = 0;
81 const means_offset = sorted_offset + samples * @sizeOf(u64);
82 const medians_offset = means_offset + iterations * @sizeOf(f64);
83 const p75s_offset = medians_offset + iterations * @sizeOf(f64);
84 const p95s_offset = p75s_offset + iterations * @sizeOf(f64);
85 const p99s_offset = p95s_offset + iterations * @sizeOf(f64);
86 const counts_offset = p99s_offset + iterations * @sizeOf(f64);
87 const storage_bytes = counts_offset + samples * @sizeOf(u32);
88 const values = [_]u128{
89 means_offset,
90 medians_offset,
91 p75s_offset,
92 p95s_offset,
93 p99s_offset,
94 counts_offset,
95 storage_bytes,
96 };
97 for (values) |value| {
98 if (value > std.math.maxInt(usize)) return error.CapacityOverflow;
99 }
100 return .{
101 .limits = limits,
102 .sorted_offset = @intCast(sorted_offset),
103 .means_offset = @intCast(means_offset),
104 .medians_offset = @intCast(medians_offset),
105 .p75s_offset = @intCast(p75s_offset),
106 .p95s_offset = @intCast(p95s_offset),
107 .p99s_offset = @intCast(p99s_offset),
108 .counts_offset = @intCast(counts_offset),
109 .storage_bytes = @intCast(storage_bytes),
110 };
111 }
112
113 test "statistics capacity matches an independent byte model" {
114 comptime {
115 @stardustClaim(
116 @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "bench_statistics_capacity"),
117 null,
118 null,
119 null,
120 null,
121 null,
122 null,
123 );
124 }
125
126 const limits = Limits{ .samples = 13, .bootstrap_iterations = 1000 };
127 try std.testing.expectEqual(try modelCapacity(limits), try Capacity.derive(limits));
128 try std.testing.expectEqual(@as(usize, 40_156), (try Capacity.derive(limits)).storage_bytes);
129 }
130
131 test "statistics capacity rejects invalid and overflowing limits" {
132 try std.testing.expectError(error.InvalidSampleLimit, Capacity.derive(.{ .samples = 0 }));
133 if (std.math.maxInt(usize) > std.math.maxInt(u32)) {
134 try std.testing.expectError(
135 error.SampleLimitTooLarge,
136 Capacity.derive(.{ .samples = @as(usize, std.math.maxInt(u32)) + 1 }),
137 );
138 }
139 if (@bitSizeOf(usize) == 32) {
140 try std.testing.expectError(
141 error.CapacityOverflow,
142 Capacity.derive(.{
143 .samples = std.math.maxInt(u32),
144 .bootstrap_iterations = std.math.maxInt(u32),
145 }),
146 );
147 }
148 }