tiny.profiling.order

1const std = @import("std");2const pretty = @import("pretty");34const host = @import("host/root.zig");5const json = @import("json.zig");6const plan = @import("plan.zig");78const pretty_json = pretty.json;910pub const contrast = @import("contrast.zig");1112pub const max_schedule_entries = plan.max_workloads_per_run * host.process.max_executions;13pub const schedule_algorithm = "xoshiro256_flat_multiset_fisher_yates";14pub const setup_order = "selected_workload_order_before_measurement";15pub const warmup_placement = "before_first_scheduled_measurement";16pub const failure_policy = "skip_failed_workload_remaining_positions";1718pub const Method = enum {19    blocked,20    random_interleaved,2122    pub fn parse(value: []const u8) ?Method {23        return std.meta.stringToEnum(Method, value);24    }2526    pub fn name(self: Method) []const u8 {27        return @tagName(self);28    }2930    pub fn acquisitionName(self: Method) []const u8 {31        return switch (self) {32            .blocked => "fixed_plan_order",33            .random_interleaved => "random_interleaved",34        };35    }36};3738pub const Blocked = struct {39    position: usize = 1,40    workload_count: usize = 1,41    predecessors: []const []const u8 = &.{},4243    pub fn valid(self: Blocked) bool {44        return self.position > 0 and45            self.position == self.predecessors.len + 1 and46            self.workload_count >= self.position and47            self.workload_count <= plan.max_workloads_per_run;48    }49};5051pub const Interleaved = struct {52    seed: u64,53    repeat_count: u32,54    workload_count: usize,55    selected_workloads: []const []const u8,56    positions: []const usize,5758    pub fn valid(self: Interleaved) bool {59        if (validateDesign(self.workload_count, self.repeat_count)) |_| {} else |_| {60            return false;61        }62        if (self.selected_workloads.len != self.workload_count or63            self.positions.len != self.repeat_count)64        {65            return false;66        }67        for (self.selected_workloads, 0..) |name, index| {68            if (name.len == 0) return false;69            for (self.selected_workloads[0..index]) |previous| {70                if (std.mem.eql(u8, name, previous)) return false;71            }72        }73        const schedule_len = self.workload_count * @as(usize, self.repeat_count);74        var previous: usize = 0;75        for (self.positions) |position| {76            if (position <= previous or position > schedule_len) return false;77            previous = position;78        }79        return true;80    }81};8283pub const Context = union(Method) {84    blocked: Blocked,85    random_interleaved: Interleaved,8687    pub fn method(self: Context) Method {88        return std.meta.activeTag(self);89    }9091    pub fn valid(self: Context) bool {92        return switch (self) {93            .blocked => |value| value.valid(),94            .random_interleaved => |value| value.valid(),95        };96    }97};9899pub const Entry = struct {100    workload_index: usize,101    repetition_index: u32,102    position: usize,103};104105pub fn validateDesign(workload_count: usize, repeat_count: u32) !void {106    if (workload_count < 2 or workload_count > plan.max_workloads_per_run) {107        return error.InvalidInterleaveWorkloadCount;108    }109    if (repeat_count < 2 or repeat_count > host.process.max_repeat) {110        return error.InvalidInterleaveRepeat;111    }112    const entry_count = std.math.mul(113        usize,114        workload_count,115        @as(usize, repeat_count),116    ) catch return error.InvalidInterleaveSchedule;117    if (entry_count > max_schedule_entries) return error.InvalidInterleaveSchedule;118}119120pub fn schedule(121    allocator: std.mem.Allocator,122    workload_count: usize,123    repeat_count: u32,124    seed: u64,125) ![]Entry {126    try validateDesign(workload_count, repeat_count);127    const entry_count = workload_count * @as(usize, repeat_count);128    const entries = try allocator.alloc(Entry, entry_count);129    for (0..workload_count) |workload_index| {130        for (0..repeat_count) |repeat_index| {131            const index = workload_index * @as(usize, repeat_count) + repeat_index;132            entries[index] = .{133                .workload_index = workload_index,134                .repetition_index = 0,135                .position = 0,136            };137        }138    }139    var prng = std.Random.Xoshiro256.init(seed);140    const random = prng.random();141    var remaining = entries.len;142    while (remaining > 1) {143        const index = random.uintLessThan(usize, remaining);144        remaining -= 1;145        std.mem.swap(Entry, &entries[index], &entries[remaining]);146    }147    var repetitions: [plan.max_workloads_per_run]u32 = @splat(0);148    for (entries, 0..) |*entry, index| {149        entry.position = index + 1;150        entry.repetition_index = repetitions[entry.workload_index];151        repetitions[entry.workload_index] += 1;152    }153    return entries;154}155156pub fn interleavedContext(157    allocator: std.mem.Allocator,158    selected_workloads: []const []const u8,159    entries: []const Entry,160    workload_index: usize,161    repeat_count: u32,162    seed: u64,163) !Context {164    try validateDesign(selected_workloads.len, repeat_count);165    if (workload_index >= selected_workloads.len or166        entries.len != selected_workloads.len * @as(usize, repeat_count))167    {168        return error.InvalidInterleaveSchedule;169    }170    const positions = try allocator.alloc(usize, repeat_count);171    var position_index: usize = 0;172    for (entries) |entry| {173        if (entry.workload_index != workload_index) continue;174        if (position_index >= positions.len) return error.InvalidInterleaveSchedule;175        positions[position_index] = entry.position;176        position_index += 1;177    }178    if (position_index != positions.len) return error.InvalidInterleaveSchedule;179    const result = Context{ .random_interleaved = .{180        .seed = seed,181        .repeat_count = repeat_count,182        .workload_count = selected_workloads.len,183        .selected_workloads = selected_workloads,184        .positions = positions,185    } };186    if (!result.valid()) return error.InvalidInterleaveSchedule;187    return result;188}189190pub fn sameDesign(baseline: Context, candidate: Context) bool {191    std.debug.assert(baseline.valid());192    std.debug.assert(candidate.valid());193    return switch (baseline) {194        .blocked => |base| switch (candidate) {195            .blocked => |actual| sameBlocked(base, actual),196            .random_interleaved => false,197        },198        .random_interleaved => |base| switch (candidate) {199            .blocked => false,200            .random_interleaved => |actual| sameInterleavedDesign(base, actual),201        },202    };203}204205fn sameBlocked(baseline: Blocked, candidate: Blocked) bool {206    if (baseline.position != candidate.position or207        baseline.predecessors.len != candidate.predecessors.len)208    {209        return false;210    }211    return sameStrings(baseline.predecessors, candidate.predecessors);212}213214fn sameInterleavedDesign(baseline: Interleaved, candidate: Interleaved) bool {215    return baseline.repeat_count == candidate.repeat_count and216        baseline.workload_count == candidate.workload_count and217        sameStrings(baseline.selected_workloads, candidate.selected_workloads);218}219220fn sameStrings(baseline: []const []const u8, candidate: []const []const u8) bool {221    if (baseline.len != candidate.len) return false;222    for (baseline, candidate) |base, actual| {223        if (!std.mem.eql(u8, base, actual)) return false;224    }225    return true;226}227228pub fn parse(allocator: std.mem.Allocator, value: std.json.Value) !Context {229    const object = try json.object(value);230    const method = if (json.string(object.get("method"))) |name| method: {231        if (!std.mem.eql(u8, name, Method.random_interleaved.name())) {232            return error.InvalidProfilingJson;233        }234        break :method Method.random_interleaved;235    } else Method.blocked;236    const result = switch (method) {237        .blocked => Context{ .blocked = .{238            .position = std.math.cast(239                usize,240                json.asU64(object.get("position")) orelse241                    return error.InvalidProfilingJson,242            ) orelse return error.InvalidProfilingJson,243            .workload_count = std.math.cast(244                usize,245                json.asU64(object.get("workload_count")) orelse246                    return error.InvalidProfilingJson,247            ) orelse return error.InvalidProfilingJson,248            .predecessors = try parseStrings(allocator, object, "predecessors"),249        } },250        .random_interleaved => interleaved: {251            try requireToken(object, "schedule_algorithm", schedule_algorithm);252            try requireToken(object, "setup_order", setup_order);253            try requireToken(object, "warmup_placement", warmup_placement);254            try requireToken(object, "failure_policy", failure_policy);255            break :interleaved Context{ .random_interleaved = .{256                .seed = json.asU64(object.get("seed")) orelse257                    return error.InvalidProfilingJson,258                .repeat_count = std.math.cast(259                    u32,260                    json.asU64(object.get("repeat_count")) orelse261                        return error.InvalidProfilingJson,262                ) orelse return error.InvalidProfilingJson,263                .workload_count = std.math.cast(264                    usize,265                    json.asU64(object.get("workload_count")) orelse266                        return error.InvalidProfilingJson,267                ) orelse return error.InvalidProfilingJson,268                .selected_workloads = try parseStrings(269                    allocator,270                    object,271                    "selected_workloads",272                ),273                .positions = try parsePositions(allocator, object),274            } };275        },276    };277    if (!result.valid()) return error.InvalidProfilingJson;278    return result;279}280281fn requireToken(282    object: std.json.ObjectMap,283    field: []const u8,284    expected: []const u8,285) !void {286    const actual = json.string(object.get(field)) orelse287        return error.InvalidProfilingJson;288    if (!std.mem.eql(u8, actual, expected)) return error.InvalidProfilingJson;289}290291fn parseStrings(292    allocator: std.mem.Allocator,293    object: std.json.ObjectMap,294    field: []const u8,295) ![]const []const u8 {296    const value = object.get(field) orelse return error.InvalidProfilingJson;297    const rows = try json.array(value);298    const strings = try json.strings(allocator, value);299    if (strings.len != rows.items.len) return error.InvalidProfilingJson;300    return strings;301}302303fn parsePositions(304    allocator: std.mem.Allocator,305    object: std.json.ObjectMap,306) ![]const usize {307    const rows = try json.array(object.get("positions") orelse308        return error.InvalidProfilingJson);309    if (rows.items.len > host.process.max_executions) {310        return error.InvalidProfilingJson;311    }312    const positions = try allocator.alloc(usize, rows.items.len);313    for (rows.items, 0..) |value, index| {314        positions[index] = std.math.cast(315            usize,316            json.asU64(value) orelse return error.InvalidProfilingJson,317        ) orelse return error.InvalidProfilingJson;318    }319    return positions;320}321322pub fn writeJson(out: *pretty_json.Writer, context: Context) !void {323    std.debug.assert(context.valid());324    try out.beginObject();325    switch (context) {326        .blocked => |value| {327            try out.objectField("position");328            try out.write(value.position);329            try out.objectField("workload_count");330            try out.write(value.workload_count);331            try out.objectField("predecessors");332            try writeStrings(out, value.predecessors);333        },334        .random_interleaved => |value| {335            try out.objectField("method");336            try out.write(Method.random_interleaved.name());337            try out.objectField("schedule_algorithm");338            try out.write(schedule_algorithm);339            try out.objectField("setup_order");340            try out.write(setup_order);341            try out.objectField("warmup_placement");342            try out.write(warmup_placement);343            try out.objectField("failure_policy");344            try out.write(failure_policy);345            try out.objectField("seed");346            try out.write(value.seed);347            try out.objectField("repeat_count");348            try out.write(value.repeat_count);349            try out.objectField("workload_count");350            try out.write(value.workload_count);351            try out.objectField("selected_workloads");352            try writeStrings(out, value.selected_workloads);353            try out.objectField("positions");354            try out.beginArray();355            for (value.positions) |position| try out.write(position);356            try out.endArray();357        },358    }359    try out.endObject();360}361362fn writeStrings(out: *pretty_json.Writer, values: []const []const u8) !void {363    try out.beginArray();364    for (values) |value| try out.write(value);365    try out.endArray();366}367368test "profiling order builds deterministic complete interleavings" {369    const allocator = std.testing.allocator;370    const first = try schedule(allocator, 3, 4, 42);371    defer allocator.free(first);372    const second = try schedule(allocator, 3, 4, 42);373    defer allocator.free(second);374    try std.testing.expectEqual(first.len, second.len);375    var counts: [3]u32 = @splat(0);376    for (first, second, 0..) |left, right, index| {377        try std.testing.expectEqual(left, right);378        try std.testing.expectEqual(index + 1, left.position);379        try std.testing.expectEqual(counts[left.workload_index], left.repetition_index);380        counts[left.workload_index] += 1;381    }382    for (counts) |count| try std.testing.expectEqual(@as(u32, 4), count);383}384385test "profiling order retains per-workload positions" {386    const allocator = std.testing.allocator;387    const entries = try schedule(allocator, 2, 3, 7);388    defer allocator.free(entries);389    const context = try interleavedContext(390        allocator,391        &.{ "a", "b" },392        entries,393        1,394        3,395        7,396    );397    defer allocator.free(context.random_interleaved.positions);398    try std.testing.expect(context.valid());399    try std.testing.expectEqual(@as(usize, 3), context.random_interleaved.positions.len);400    for (context.random_interleaved.positions) |position| {401        try std.testing.expectEqual(@as(usize, 1), entries[position - 1].workload_index);402    }403}404405test "profiling order compares designs without coupling independent seeds" {406    const baseline = Context{ .random_interleaved = .{407        .seed = 1,408        .repeat_count = 2,409        .workload_count = 2,410        .selected_workloads = &.{ "a", "b" },411        .positions = &.{ 1, 4 },412    } };413    const candidate = Context{ .random_interleaved = .{414        .seed = 2,415        .repeat_count = 2,416        .workload_count = 2,417        .selected_workloads = &.{ "a", "b" },418        .positions = &.{ 2, 3 },419    } };420    try std.testing.expect(sameDesign(baseline, candidate));421    try std.testing.expect(!sameDesign(422        baseline,423        .{ .blocked = .{ .position = 1, .workload_count = 2 } },424    ));425}426427test "profiling order parses retained interleaving context" {428    var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);429    defer arena_state.deinit();430    const allocator = arena_state.allocator();431    const value = try std.json.parseFromSliceLeaky(432        std.json.Value,433        allocator,434        \\{"method":"random_interleaved","schedule_algorithm":"xoshiro256_flat_multiset_fisher_yates","setup_order":"selected_workload_order_before_measurement","warmup_placement":"before_first_scheduled_measurement","failure_policy":"skip_failed_workload_remaining_positions","seed":42,"repeat_count":3,"workload_count":2,"selected_workloads":["a","b"],"positions":[1,3,6]}435    ,436        .{},437    );438    const context = try parse(allocator, value);439    try std.testing.expectEqual(Method.random_interleaved, context.method());440    try std.testing.expectEqual(@as(u64, 42), context.random_interleaved.seed);441    try std.testing.expectEqualStrings(442        "b",443        context.random_interleaved.selected_workloads[1],444    );445    try std.testing.expectEqual(@as(usize, 6), context.random_interleaved.positions[2]);446}

1pub const order = @import("order.zig");