//! Which shard serves which test, for src/test_runner.zig's `--shard=K/N`.
//!
//! By index alone (test i to shard i mod N) the heaviest tests can land in
//! one shard, and a step's wall time is its slowest shard's: two tests of
//! several minutes each once made one e2e shard run 937 s while the others
//! ran 321-417 s. So the tests src/testing/test_weights.txt names are
//! packed first, heaviest onto the least-loaded shard, and every other test
//! keeps its index assignment.
//!
//! Every shard process computes the whole assignment and serves its own
//! part, so the assignment must be a pure function of the test names, the
//! weights and N: then each test is served by exactly one shard. A name the
//! weights list that no test has, a repeated name, or a malformed line
//! changes nothing; the weights only ever move a test between shards.
const std = @import("std");
/// The shard, below `count`, that serves each test, indexed like `names`.
/// The caller frees it.
pub fn assign(gpa: std.mem.Allocator, names: []const []const u8, weights: []const u8, count: u32) error{ OutOfMemory, NoShards }![]u32 {
if (count == 0) return error.NoShards;
const shard_of = try gpa.alloc(u32, names.len);
errdefer gpa.free(shard_of);
for (shard_of, 0..) |*shard, i| shard.* = @intCast(i % count);
if (count == 1) return shard_of;
const Heavy = struct { index: u32, millis: u64 };
var heavy: std.ArrayList(Heavy) = .empty;
defer heavy.deinit(gpa);
const listed = try gpa.alloc(bool, names.len);
defer gpa.free(listed);
@memset(listed, false);
var lines = std.mem.splitScalar(u8, weights, '\n');
while (lines.next()) |line| {
const tab = std.mem.indexOfScalar(u8, line, '\t') orelse continue;
const seconds = std.fmt.parseFloat(f64, std.mem.trim(u8, line[tab + 1 ..], " \r")) catch continue;
// Also refuses NaN; a day caps an absurd figure.
if (!(seconds > 0)) continue;
const millis: u64 = @intFromFloat(@min(seconds, 86_400) * 1000);
for (names, 0..) |name, i| {
if (listed[i] or !std.mem.eql(u8, name, line[0..tab])) continue;
listed[i] = true;
try heavy.append(gpa, .{ .index = @intCast(i), .millis = millis });
break;
}
}
std.mem.sort(Heavy, heavy.items, {}, struct {
fn heavier(_: void, a: Heavy, b: Heavy) bool {
return a.millis > b.millis or (a.millis == b.millis and a.index < b.index);
}
}.heavier);
const load = try gpa.alloc(u64, count);
defer gpa.free(load);
@memset(load, 0);
for (heavy.items) |h| {
var lightest: u32 = 0;
for (load, 0..) |l, shard| {
if (l < load[lightest]) lightest = @intCast(shard);
}
shard_of[h.index] = lightest;
load[lightest] += h.millis;
}
return shard_of;
}
const testing = std.testing;
/// What each of `count` shard processes would serve, computed separately as
/// the runner does, must cover every test exactly once.
fn expectPartition(names: []const []const u8, weights: []const u8, count: u32) !void {
const served = try testing.allocator.alloc(u32, names.len);
defer testing.allocator.free(served);
@memset(served, 0);
for (0..count) |k| {
const shard_of = try assign(testing.allocator, names, weights, count);
defer testing.allocator.free(shard_of);
try testing.expectEqual(names.len, shard_of.len);
for (shard_of, 0..) |shard, i| {
try testing.expect(shard < count);
if (shard == k) served[i] += 1;
}
}
for (served) |n| try testing.expectEqual(@as(u32, 1), n);
}
const sample_names = [_][]const u8{
"a.test.one", "a.test.two", "a.test.three", "b.test.four", "b.test.five", "b.test.six",
"c.test.seven", "c.test.eight", "c.test.nine", "c.test.ten", "d.test.eleven",
};
test "shards: every test is served exactly once, with stale, repeated and malformed weights" {
const weights =
"a.test.two\t300\n" ++
"gone.test.stale\t900\n" ++
"c.test.nine\t250.5\n" ++
"a.test.two\t5\n" ++
"b.test.five\tnot a number\n" ++
"no tab here\n" ++
"d.test.eleven\tnan\n" ++
"c.test.seven\tinf\n" ++
"b.test.four\t-3\n" ++
"\n" ++
"c.test.ten\t2.5\r\n";
for ([_]u32{ 1, 2, 3, 4, 5, 7, 11, 16 }) |count| {
try expectPartition(&sample_names, weights, count);
try expectPartition(&sample_names, "", count);
}
try expectPartition(&.{}, weights, 4);
}
test "shards: the heaviest tests go to different shards, and the rest keep their index" {
// Indices 0 and 4 share a shard by index (0 mod 4 == 4 mod 4).
const weights = "a.test.one\t435\nb.test.five\t236\n";
const shard_of = try assign(testing.allocator, &sample_names, weights, 4);
defer testing.allocator.free(shard_of);
try testing.expect(shard_of[0] != shard_of[4]);
for (shard_of, 0..) |shard, i| {
if (i == 0 or i == 4) continue;
try testing.expectEqual(@as(u32, @intCast(i % 4)), shard);
}
// Pure: the same inputs give the same assignment.
const again = try assign(testing.allocator, &sample_names, weights, 4);
defer testing.allocator.free(again);
try testing.expectEqualSlices(u32, shard_of, again);
}
test "shards: no shards is refused" {
try testing.expectError(error.NoShards, assign(testing.allocator, &sample_names, "", 0));
}
test "shards: no weights is the index assignment" {
const shard_of = try assign(testing.allocator, &sample_names, "", 3);
defer testing.allocator.free(shard_of);
for (shard_of, 0..) |shard, i| try testing.expectEqual(@as(u32, @intCast(i % 3)), shard);
}