Skip to content
zit Artifact [4b1e9d0c5a]
Login

Artifact [4b1e9d0c5a]

Artifact 4b1e9d0c5a1c4362fafb0e4cc0ae2cdf30285b754896d44cb47727d23394acff:


//! 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);
}