Artifact 962c091da767a9b6b57572af425b66ef823cbb82f7c6ae4ba69ae738972c9092:
- File
src/git/git_import_benchmark.zig
— part of check-in
[d6cf7bf59c]
at
2026-09-28 11:59:39
on branch trunk
— Lock the store with exclusive-create lock files instead of flock
Writers create .zit.lock with O_CREAT|O_EXCL before opening the store. A waiter names the holder and gives up after a minute; a dead holder's lock is broken; pack and shun --force hold the writer lock across their final check and rename. Release 0.3.33. (user: dmestas, size: 63142) [annotate] [blame] [check-ins using]
const std = @import("std"); const builtin = @import("builtin"); const zit = @import("zit"); const artifact = zit.artifact; const editor = zit.submanifest_editor; const fast_export = zit.git_fast_export; const git_import = zit.git_import; const logstore = zit.logstore; const storage = zit.storage; const import_support = zit.git_import_benchmark_support; const max_f_cards: u64 = 10_000_000; const max_new_store_bytes: u64 = 2 * 1024 * 1024 * 1024; const max_wall_ns: u64 = 15 * 60 * std.time.ns_per_s; const max_width: u64 = 10_000_000; const max_commits: u64 = 190_000; const default_cache_bytes: usize = 1 << 20; const default_max_rss_bytes: u64 = 2 * 1024 * 1024 * 1024; // A corpus is retained as one contiguous stream; cap its preallocation below // the store ceiling so parameter products cannot turn validation into an OOM. const max_stream_bytes: u64 = 64 * 1024 * 1024; const max_blob_bytes: u64 = 80; const max_commit_bytes: u64 = 256; const max_command_bytes: u64 = 64; const stream_fixed_bytes: u64 = "feature done\n".len + "done\n".len; const Error = error{ BadArgs, BoundExceeded, SemanticMismatch, GateFailed, ProvenanceUnavailable, Io, OutOfMemory }; const Config = struct { seed: u64 = 1, width: u64 = 20_000, commits: u64 = 1_000, changed: u64 = 1, branch_every: u64 = 97, merge_every: u64 = 389, revision: []const u8 = "", k: u4 = 5, reps: usize = 3, cache_bytes: usize = default_cache_bytes, full: bool = false, max_rss_bytes: u64 = default_max_rss_bytes, }; const Arm = enum { flat_reference, incremental_tree }; const Bound = enum { none, f_cards, store_bytes, wall_time }; const CorpusBounds = struct { records: u64, bytes: u64, bound: Bound, }; const CommonPrefix = struct { commits: u64, expected_control_bound: ?Bound, }; const PhaseTimes = struct { corpus_ns: u64, import_ns: u64, finalize_ns: u64, semantic_ns: u64, finalize_cpu_ns: u64, wall_ns: u64, cpu_ns: u64, }; const RunRecord = struct { arm: Arm, effective_commits: u64, semantic_prefix_commits: u64 = 0, expected_control_bound: ?Bound = null, phase: PhaseTimes, counters: git_import.WorkCounters, store_bytes: u64, f_cards: u64, bound: Bound, semantic: [32]u8, sampled: [32]u8, equal_sampled_trees: ?bool = null, process_peak_rss_bytes: u64, retained_state_entries: usize, wall_scale_ratio: f64 = 0, cpu_scale_ratio: f64 = 0, }; const RssAccumulator = struct { peak_bytes: u64 = 0, fn observe(self: *RssAccumulator, bytes: u64) void { self.peak_bytes = @max(self.peak_bytes, bytes); } }; const CapturedRun = struct { record: RunRecord, store: Store, root_checkin: []u8, mid_checkin: []u8, side_checkin: ?[]u8, merge_checkin: ?[]u8, sampled_checkin: []u8, final_checkin: []u8, fn deinit(self: *CapturedRun, gpa: std.mem.Allocator) void { gpa.free(self.sampled_checkin); gpa.free(self.final_checkin); gpa.free(self.root_checkin); gpa.free(self.mid_checkin); if (self.side_checkin) |checkin| gpa.free(checkin); if (self.merge_checkin) |checkin| gpa.free(checkin); self.store.deinit(gpa); self.* = undefined; } }; const SampleComparison = struct { flat_digest: [32]u8, tree_digest: [32]u8, equal: bool, }; const MemoryFile = struct { gpa: std.mem.Allocator, bytes: std.ArrayList(u8) = .empty, max_bytes: u64 = max_new_store_bytes, limit_reached: bool = false, fn init(gpa: std.mem.Allocator) MemoryFile { return .{ .gpa = gpa }; } fn deinit(self: *MemoryFile) void { self.bytes.deinit(self.gpa); self.* = undefined; } fn storageFile(self: *MemoryFile) storage.StorageFile { return .{ .context = self, .vtable = &vtable }; } const vtable: storage.StorageFile.VTable = .{ .append = append, .pread = pread, .sync = sync, .size = size, .truncate = truncate, .refresh_end = refreshEnd, }; /// One writer by construction, so there is no other writer to exclude and /// no other writer's appends to re-read the length for. fn refreshEnd(_: *anyopaque) storage.StorageError!void {} fn append(context: *anyopaque, data: []const u8) storage.StorageError!void { const self: *MemoryFile = @ptrCast(@alignCast(context)); const data_len: u64 = @intCast(data.len); const current_len: u64 = @intCast(self.bytes.items.len); if (data_len > self.max_bytes -| current_len) { self.limit_reached = true; return error.Io; } self.bytes.appendSlice(self.gpa, data) catch return error.Io; } fn pread(context: *anyopaque, offset: u64, out: []u8) storage.StorageError!usize { const self: *MemoryFile = @ptrCast(@alignCast(context)); if (offset >= self.bytes.items.len) return 0; const begin: usize = @intCast(offset); const len = @min(out.len, self.bytes.items.len - begin); @memcpy(out[0..len], self.bytes.items[begin..][0..len]); return len; } fn sync(_: *anyopaque) storage.StorageError!void {} fn size(context: *anyopaque) storage.StorageError!u64 { const self: *MemoryFile = @ptrCast(@alignCast(context)); return self.bytes.items.len; } fn truncate(context: *anyopaque, length: u64) storage.StorageError!void { const self: *MemoryFile = @ptrCast(@alignCast(context)); const end: usize = @intCast(length); if (end > self.bytes.items.len) return error.Io; self.bytes.shrinkRetainingCapacity(end); } }; const Store = struct { gpa: std.mem.Allocator, log: logstore.LogStore, file: *MemoryFile, fn init(gpa: std.mem.Allocator) !Store { const file = try gpa.create(MemoryFile); errdefer gpa.destroy(file); file.* = MemoryFile.init(gpa); errdefer file.deinit(); return .{ .gpa = gpa, .file = file, .log = try logstore.LogStore.open(gpa, file.storageFile(), @intFromEnum(artifact.defaultPolicy(true, false))) }; } fn deinit(self: *Store, gpa: std.mem.Allocator) void { self.log.deinit(gpa); self.file.deinit(); gpa.destroy(self.file); self.* = undefined; } fn treeStore(self: *Store) git_import.TreeStore { return .{ .ctx = self, .load_fn = load, .put_fn = put, .put_batch_fn = putBatch }; } fn load(context: *anyopaque, allocator: std.mem.Allocator, name: []const u8) git_import.TreeStoreError!git_import.LoadedBytes { const self: *Store = @ptrCast(@alignCast(context)); var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.MissingNode; const rid = self.log.lookup(digest) orelse return error.MissingNode; const bytes = self.log.content(allocator, rid) catch return error.StorageFailure; return .{ .bytes = bytes orelse return error.MissingNode, .allocator = allocator }; } fn put(context: *anyopaque, name: []const u8, bytes: []const u8) git_import.TreeStoreError!void { const self: *Store = @ptrCast(@alignCast(context)); // Algorithm-agnostic: `verify` picks the digest from the name width. if (!artifact.verify(name, bytes)) return error.StorageFailure; var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.StorageFailure; _ = self.log.putArtifact(digest, bytes, null) catch return error.StorageFailure; } fn putBatch(context: *anyopaque, nodes: []const editor.StoreBatchNode) git_import.TreeStoreError!void { const self: *Store = @ptrCast(@alignCast(context)); var digests: std.ArrayList([32]u8) = .empty; defer digests.deinit(self.gpa); var items: std.ArrayList(logstore.LogStore.ArtifactBatchItem) = .empty; defer items.deinit(self.gpa); digests.ensureTotalCapacity(self.gpa, nodes.len) catch return error.OutOfMemory; items.ensureTotalCapacity(self.gpa, nodes.len) catch return error.OutOfMemory; for (nodes) |node| { var expected: [64]u8 = undefined; if (!std.mem.eql(u8, node.name, artifact.artifactName(git_import.import_hash_algo, node.bytes, &expected))) { return error.StorageFailure; } var digest: [32]u8 = undefined; const raw = rawHashName(node.name, &digest) orelse return error.StorageFailure; digests.appendAssumeCapacity(digest); items.appendAssumeCapacity(.{ .hash = digests.items[digests.items.len - 1][0..raw.len], .bytes = node.bytes, }); } self.log.putArtifactBatch(items.items) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => return error.StorageFailure, }; } }; /// The benchmark's test-only baseline. It deliberately flattens an inherited /// S-tree before applying each change; production never instantiates it. const FlatReferencePolicy = struct { pub fn apply( _: *editor.TreeEditor, gpa: std.mem.Allocator, tree_store: git_import.TreeStore, parent: git_import.RootView, commands: []const git_import.TreeCommand, result: *git_import.BuildResult, cache_high_water: *usize, ) git_import.TreeError!void { var arena_state = std.heap.ArenaAllocator.init(gpa); errdefer arena_state.deinit(); const arena = arena_state.allocator(); var cards = std.ArrayList(artifact.FCard).empty; const root: SemanticRoot = switch (parent) { .flat => |flat| .{ .flat = flat }, .tree => |tree| .{ .tree = tree }, }; try flattenRoot(&cards, arena, tree_store, root); for (commands) |command| try applyFlatCommand(&cards, arena, command); std.mem.sort(artifact.FCard, cards.items, {}, lessCard); result.* = .{ .root = .{ .flat = try cards.toOwnedSlice(arena) }, .tree_height = 0, .changed_paths = commands.len, .reused_nodes = 0, .emitted_nodes = cards.items.len, .arena_state = arena_state, }; cache_high_water.* = 0; } pub fn inheritedFullTreeMaterialization(parent: git_import.RootView) bool { return switch (parent) { .flat => |cards| cards.len != 0, .tree => |cards| cards.len != 0, }; } }; /// Compile-time production policy used only by the private benchmark seam. const IncrementalTreePolicy = import_support.IncrementalTreePolicy; const BoundsContext = struct { io: std.Io, store: *Store, start_ns: u64, f_cards: u64 = 0, total_commits: u64, replay_start_ns: ?u64 = null, replay_start_cpu_ns: ?u64 = null, replay_ns: u64 = 0, replay_cpu_ns: u64 = 0, fired: ?Bound = null, fn fail(self: *BoundsContext, bound: Bound) error{BoundExceeded} { self.fired = bound; return error.BoundExceeded; } fn beforeCommit(self: *BoundsContext) !void { if (self.store.file.bytes.items.len >= max_new_store_bytes) return self.fail(.store_bytes); if (nowNs(self.io) - self.start_ns >= max_wall_ns) return self.fail(.wall_time); } fn beforeCommitFlush(self: *BoundsContext, observation: anytype) !void { if (observation.serialized_f_cards >= max_f_cards - self.f_cards) return self.fail(.f_cards); if (self.store.file.bytes.items.len >= max_new_store_bytes or observation.staged_artifact_bytes > max_new_store_bytes - self.store.file.bytes.items.len) return self.fail(.store_bytes); if (nowNs(self.io) - self.start_ns >= max_wall_ns) return self.fail(.wall_time); } fn afterCommitFlush(self: *BoundsContext, observation: anytype) void { self.f_cards += observation.serialized_f_cards; } fn finish(self: *BoundsContext) void { if (self.fired == null) return; if (self.replay_start_ns) |replay_start_ns| { self.replay_ns = nowNs(self.io) - replay_start_ns; self.replay_cpu_ns = selfCpuNs() - self.replay_start_cpu_ns.?; } } fn afterCommit(self: *BoundsContext, counters: *const git_import.WorkCounters) void { if (counters.commits == 1) { self.replay_start_ns = nowNs(self.io); self.replay_start_cpu_ns = selfCpuNs(); } else if (counters.commits == self.total_commits) { self.replay_ns = nowNs(self.io) - self.replay_start_ns.?; self.replay_cpu_ns = selfCpuNs() - self.replay_start_cpu_ns.?; } } }; const BoundsObserver = struct { bounds: *BoundsContext, pub fn beforeEvent(self: *BoundsObserver, _: *const git_import.WorkCounters, event: zit.git_fast_export.Event) !void { switch (event) { .blob, .commit => try self.bounds.beforeCommit(), else => {}, } } pub fn beforeCommitFlush(self: *BoundsObserver, _: *const git_import.WorkCounters, observation: anytype) !void { try self.bounds.beforeCommitFlush(observation); } pub fn afterCommitFlush(self: *BoundsObserver, _: *const git_import.WorkCounters, observation: anytype) void { self.bounds.afterCommitFlush(observation); } pub fn stopOnError(self: *BoundsObserver, err: anyerror) bool { if (self.bounds.store.file.limit_reached) { self.bounds.fired = .store_bytes; return true; } return err == error.BoundExceeded and self.bounds.fired != null; } pub fn afterEvent(self: *BoundsObserver, counters: *const git_import.WorkCounters, event: zit.git_fast_export.Event) !void { switch (event) { .commit => self.bounds.afterCommit(counters), else => {}, } } }; const FlatImporter = import_support.Importer(FlatReferencePolicy, BoundsObserver); const IncrementalImporter = import_support.Importer(IncrementalTreePolicy, BoundsObserver); fn lessCard(_: void, a: artifact.FCard, b: artifact.FCard) bool { return std.mem.order(u8, a.filename, b.filename) == .lt; } fn flattenRoot(cards: *std.ArrayList(artifact.FCard), arena: std.mem.Allocator, tree_store: git_import.TreeStore, root: SemanticRoot) !void { switch (root) { .flat => |flat| for (flat) |card| try cards.append(arena, try cloneCard(arena, card)), .tree => |tree| for (tree) |sub| { var loaded = try tree_store.load_fn(tree_store.ctx, arena, sub.hash); defer loaded.deinit(); var manifest = artifact.parse(arena, loaded.bytes) catch |err| { std.debug.print("flat node parse name={s} error={s}\n", .{ sub.hash, @errorName(err) }); return error.MalformedNode; }; defer manifest.deinit(); const child: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try flattenRoot(cards, arena, tree_store, child); }, } } fn cloneCard(allocator: std.mem.Allocator, card: artifact.FCard) !artifact.FCard { return .{ .filename = try allocator.dupe(u8, card.filename), .hash = if (card.hash) |hash| try allocator.dupe(u8, hash) else null, .perm = if (card.perm) |perm| try allocator.dupe(u8, perm) else null, .old_name = if (card.old_name) |name| try allocator.dupe(u8, name) else null, .mode = card.mode, }; } fn applyFlatCommand(cards: *std.ArrayList(artifact.FCard), arena: std.mem.Allocator, command: anytype) !void { switch (command) { .upsert => |card| { const owned = try cloneCard(arena, card); if (findCard(cards.items, card.filename)) |index| cards.items[index] = owned else try cards.append(arena, owned); }, .delete => |path| { const index = findCard(cards.items, path) orelse return error.MissingPath; _ = cards.orderedRemove(index); }, .rename => |rename| { const index = findCard(cards.items, rename.old) orelse return error.MissingPath; var card = cards.orderedRemove(index); card.filename = try arena.dupe(u8, rename.new); if (findCard(cards.items, rename.new)) |existing| cards.items[existing] = card else try cards.append(arena, card); }, .copy => |copy| { const index = findCard(cards.items, copy.old) orelse return error.MissingPath; var card = try cloneCard(arena, cards.items[index]); card.filename = try arena.dupe(u8, copy.new); if (findCard(cards.items, copy.new)) |existing| cards.items[existing] = card else try cards.append(arena, card); }, .delete_all => cards.clearRetainingCapacity(), } } fn findCard(cards: []const artifact.FCard, path: []const u8) ?usize { for (cards, 0..) |card, index| if (std.mem.eql(u8, card.filename, path)) return index; return null; } pub fn main(init: std.process.Init) !void { const args = try init.minimal.args.toSlice(init.arena.allocator()); var output_buffer: [64 * 1024]u8 = undefined; var output = std.Io.File.Writer.init(.stdout(), init.io, &output_buffer); run(init.gpa, init.io, args, &output.interface) catch |err| { std.debug.print("import-git-bench: {s}\n", .{@errorName(err)}); return err; }; try output.interface.flush(); } fn run(gpa: std.mem.Allocator, io: std.Io, args: []const []const u8, out: *std.Io.Writer) !void { var cfg = try parseArgs(args); const revision = try checkoutRevision(gpa, io); cfg.revision = &revision; if (corpusBounds(cfg, cfg.commits).bound != .none) return error.BoundExceeded; const prefix = commonPrefix(cfg); const fingerprint_stream = try buildStream(gpa, cfg, cfg.commits); defer gpa.free(fingerprint_stream); const fingerprint = corpusFingerprint(fingerprint_stream); const executable_hash = try executableHash(io, gpa, args[0]); if (cfg.full) return runProductionCorpus(gpa, io, cfg, out, fingerprint, executable_hash); const small = @max(@as(u64, 1), prefix.commits / 2); // Paired, untimed qualification establishes the intermediate sampled and // final output oracles before the fixed-corpus timing matrix. var rss = RssAccumulator{}; const warm_small = try runPaired(gpa, io, cfg, small, &rss); var warm_big = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&warm_big, prefix); if (!warm_small.equal or !warm_big.equal) return error.GateFailed; const width_ratio = try widthDoublingRatio(gpa, io, cfg, &rss); var flat_records: [7]RunRecord = undefined; var tree_records: [7]RunRecord = undefined; if (cfg.reps > flat_records.len) return error.BadArgs; var equal_sampled_trees = true; var bounds_clear = pairedBoundsAccepted(warm_small.flat.bound, warm_small.tree.bound, null) and pairedBoundsAccepted(warm_big.flat.bound, warm_big.tree.bound, prefix.expected_control_bound); var retained_state_clear = retainedStateConstant(cfg, warm_small.flat) and retainedStateConstant(cfg, warm_small.tree) and retainedStateConstant(cfg, warm_big.flat) and retainedStateConstant(cfg, warm_big.tree); for (0..cfg.reps) |rep| { const small_pair = try runPaired(gpa, io, cfg, small, &rss); var big_pair = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&big_pair, prefix); try expectSameSemantics(small_pair.flat, small_pair.tree); try expectSameSemantics(big_pair.flat, big_pair.tree); equal_sampled_trees = equal_sampled_trees and small_pair.equal and big_pair.equal; bounds_clear = bounds_clear and pairedBoundsAccepted(small_pair.flat.bound, small_pair.tree.bound, null) and pairedBoundsAccepted(big_pair.flat.bound, big_pair.tree.bound, prefix.expected_control_bound); retained_state_clear = retained_state_clear and retainedStateConstant(cfg, small_pair.flat) and retainedStateConstant(cfg, small_pair.tree) and retainedStateConstant(cfg, big_pair.flat) and retainedStateConstant(cfg, big_pair.tree); flat_records[rep] = big_pair.flat; tree_records[rep] = big_pair.tree; flat_records[rep].wall_scale_ratio = ratio(big_pair.flat.phase.wall_ns, small_pair.flat.phase.wall_ns); flat_records[rep].cpu_scale_ratio = ratio(big_pair.flat.phase.cpu_ns, small_pair.flat.phase.cpu_ns); tree_records[rep].wall_scale_ratio = ratio(big_pair.tree.phase.wall_ns, small_pair.tree.phase.wall_ns); tree_records[rep].cpu_scale_ratio = ratio(big_pair.tree.phase.cpu_ns, small_pair.tree.phase.cpu_ns); } const flat_wall = medianRatio(flat_records[0..cfg.reps], true); const tree_wall = medianRatio(tree_records[0..cfg.reps], true); const flat_cpu = medianRatio(flat_records[0..cfg.reps], false); const tree_cpu = medianRatio(tree_records[0..cfg.reps], false); const rss_clear = rss.peak_bytes <= cfg.max_rss_bytes; const failed_gate = gateFailure(flat_wall, tree_wall, flat_cpu, tree_cpu, width_ratio, equal_sampled_trees, bounds_clear, retained_state_clear, rss_clear); for (flat_records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, flat_wall, flat_cpu, width_ratio, rss.peak_bytes, true, failed_gate); for (tree_records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, tree_wall, tree_cpu, width_ratio, rss.peak_bytes, true, failed_gate); try out.flush(); if (!std.mem.eql(u8, failed_gate, "none")) return error.GateFailed; } fn runProductionCorpus(gpa: std.mem.Allocator, io: std.Io, cfg: Config, out: *std.Io.Writer, fingerprint: [32]u8, executable_hash: [32]u8) !void { const prefix = commonPrefix(cfg); const small = cfg.commits / 2; var rss = RssAccumulator{}; // This untimed pair is the independent flat/tree oracle over the explicit // safe prefix; all warm and timed qualification remains at full input size. var semantic_pair = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&semantic_pair, prefix); const full_semantic_clear = semantic_pair.equal; const warm = try runOne(IncrementalTreePolicy, gpa, io, cfg, cfg.commits, .incremental_tree, &rss); const width_ratio = try widthDoublingRatio(gpa, io, cfg, &rss); var records: [7]RunRecord = undefined; var bounds_clear = pairedBoundsAccepted(semantic_pair.flat.bound, semantic_pair.tree.bound, prefix.expected_control_bound) and warm.bound == .none; var retained_state_clear = retainedStateConstant(cfg, semantic_pair.flat) and retainedStateConstant(cfg, semantic_pair.tree) and retainedStateConstant(cfg, warm); for (0..cfg.reps) |rep| { const before = try runOne(IncrementalTreePolicy, gpa, io, cfg, small, .incremental_tree, &rss); var after = try runOne(IncrementalTreePolicy, gpa, io, cfg, cfg.commits, .incremental_tree, &rss); after.semantic_prefix_commits = prefix.commits; after.expected_control_bound = prefix.expected_control_bound; after.wall_scale_ratio = ratio(after.phase.wall_ns, before.phase.wall_ns); after.cpu_scale_ratio = ratio(after.phase.cpu_ns, before.phase.cpu_ns); records[rep] = after; bounds_clear = bounds_clear and before.bound == .none and after.bound == .none; retained_state_clear = retained_state_clear and retainedStateConstant(cfg, before) and retainedStateConstant(cfg, after); } const wall = medianRatio(records[0..cfg.reps], true); const cpu = medianRatio(records[0..cfg.reps], false); const rss_clear = rss.peak_bytes <= cfg.max_rss_bytes; const failed_gate = productionGateFailure(bounds_clear, full_semantic_clear, retained_state_clear, rss_clear, wall, cpu, width_ratio); for (records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, wall, cpu, width_ratio, rss.peak_bytes, full_semantic_clear, failed_gate); try out.flush(); if (!std.mem.eql(u8, failed_gate, "none")) return error.GateFailed; } fn parseArgs(args: []const []const u8) !Config { var cfg = Config{}; var index: usize = 1; while (index < args.len) { const flag = args[index]; if (std.mem.eql(u8, flag, "--full")) { cfg.full = true; index += 1; continue; } if (index + 1 >= args.len) return error.BadArgs; const value = args[index + 1]; if (std.mem.eql(u8, flag, "--width")) cfg.width = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--commits")) cfg.commits = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--changed")) cfg.changed = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--seed")) cfg.seed = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--reps")) cfg.reps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, flag, "--branch-every")) cfg.branch_every = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--merge-every")) cfg.merge_every = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--k")) cfg.k = try std.fmt.parseInt(u4, value, 10) else if (std.mem.eql(u8, flag, "--cache-bytes")) cfg.cache_bytes = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, flag, "--max-rss-bytes")) cfg.max_rss_bytes = try std.fmt.parseInt(u64, value, 10) else return error.BadArgs; index += 2; } if (cfg.width == 0 or cfg.width > max_width / 2 or cfg.commits == 0 or cfg.commits > max_commits or cfg.changed == 0 or cfg.changed > cfg.width or cfg.reps == 0 or cfg.reps > 7 or cfg.reps % 2 == 0 or cfg.cache_bytes == 0 or cfg.max_rss_bytes == 0) return error.BadArgs; if (cfg.seed > std.math.maxInt(u64) - (cfg.changed - 1)) return error.BadArgs; if (cfg.k < artifact.min_k or cfg.k > artifact.max_k) return error.BadArgs; if (cfg.full and (cfg.width < 100_000 or cfg.commits < 100_000)) return error.BadArgs; return cfg; } fn commonPrefix(cfg: Config) CommonPrefix { const commits = @max(@as(u64, 1), @min(cfg.commits, (max_f_cards - 1) / cfg.width)); return .{ .commits = commits, .expected_control_bound = if (commits < cfg.commits) .f_cards else null, }; } fn pairedBoundsAccepted(flat: Bound, tree: Bound, expected_control_bound: ?Bound) bool { return flat == (expected_control_bound orelse .none) and tree == .none; } fn runOne(comptime policy: type, gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, arm: Arm, rss: *RssAccumulator) !RunRecord { var captured = try runCaptured(policy, gpa, io, cfg, commits, arm, rss); defer captured.deinit(gpa); return captured.record; } const PairedRun = struct { flat: RunRecord, tree: RunRecord, equal: bool, }; fn annotateCommonPrefix(pair: *PairedRun, prefix: CommonPrefix) void { pair.flat.semantic_prefix_commits = prefix.commits; pair.flat.expected_control_bound = prefix.expected_control_bound; pair.tree.semantic_prefix_commits = prefix.commits; pair.tree.expected_control_bound = prefix.expected_control_bound; if (prefix.expected_control_bound) |bound| { if (pair.flat.bound == .none) pair.flat.bound = bound; } } fn runPaired(gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, rss: *RssAccumulator) !PairedRun { var flat = try runCaptured(FlatReferencePolicy, gpa, io, cfg, commits, .flat_reference, rss); defer flat.deinit(gpa); var tree = try runCaptured(IncrementalTreePolicy, gpa, io, cfg, commits, .incremental_tree, rss); defer tree.deinit(gpa); if (flat.record.effective_commits != tree.record.effective_commits) { const safe_commits = @min(flat.record.effective_commits, tree.record.effective_commits); const flat_bound = if (flat.record.effective_commits == safe_commits) flat.record.bound else .none; const tree_bound = if (tree.record.effective_commits == safe_commits) tree.record.bound else .none; return runCommonSafePair(gpa, io, cfg, safe_commits, flat_bound, tree_bound, rss); } return compareCapturedRuns(gpa, &flat, &tree); } fn runCommonSafePair(gpa: std.mem.Allocator, io: std.Io, cfg: Config, safe_commits: u64, flat_bound: Bound, tree_bound: Bound, rss: *RssAccumulator) !PairedRun { var flat = try runCaptured(FlatReferencePolicy, gpa, io, cfg, safe_commits, .flat_reference, rss); defer flat.deinit(gpa); var tree = try runCaptured(IncrementalTreePolicy, gpa, io, cfg, safe_commits, .incremental_tree, rss); defer tree.deinit(gpa); flat.record.bound = flat_bound; tree.record.bound = tree_bound; return compareCapturedRuns(gpa, &flat, &tree); } fn compareCapturedRuns(gpa: std.mem.Allocator, flat: *CapturedRun, tree: *CapturedRun) !PairedRun { const root = try compareSampledTrees(gpa, &flat.store, flat.root_checkin, &tree.store, tree.root_checkin); const mid = try compareSampledTrees(gpa, &flat.store, flat.mid_checkin, &tree.store, tree.mid_checkin); const sampled = try compareSampledTrees(gpa, &flat.store, flat.sampled_checkin, &tree.store, tree.sampled_checkin); const final = try compareSampledTrees(gpa, &flat.store, flat.final_checkin, &tree.store, tree.final_checkin); const side_equal = if (flat.side_checkin) |checkin| blk: { const peer = tree.side_checkin orelse break :blk false; break :blk (try compareSampledTrees(gpa, &flat.store, checkin, &tree.store, peer)).equal; } else tree.side_checkin == null; const merge_equal = if (flat.merge_checkin) |checkin| blk: { const peer = tree.merge_checkin orelse break :blk false; break :blk (try compareSampledTrees(gpa, &flat.store, checkin, &tree.store, peer)).equal; } else tree.merge_checkin == null; const equal = root.equal and mid.equal and sampled.equal and final.equal and side_equal and merge_equal and flat.record.effective_commits == tree.record.effective_commits; flat.record.sampled = sampled.flat_digest; flat.record.equal_sampled_trees = equal; tree.record.sampled = sampled.tree_digest; tree.record.equal_sampled_trees = equal; return .{ .flat = flat.record, .tree = tree.record, .equal = equal }; } fn runCaptured(comptime policy: type, gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, arm: Arm, rss: *RssAccumulator) !CapturedRun { if (corpusBounds(cfg, commits).bound != .none) return error.BoundExceeded; var store = try Store.init(gpa); errdefer store.deinit(gpa); const corpus_start = nowNs(io); const stream = try buildStream(gpa, cfg, commits); defer gpa.free(stream); const corpus_ns = nowNs(io) - corpus_start; var bounds = BoundsContext{ .io = io, .store = &store, .start_ns = nowNs(io), .total_commits = commits, }; var importer = if (comptime policy == IncrementalTreePolicy) try IncrementalImporter.initObserved(gpa, &store.log, store.treeStore(), .{ .submanifest = .{ .tree = cfg.k }, .tree_cache_bytes = cfg.cache_bytes }, .{ .bounds = &bounds }) else try FlatImporter.initObserved(gpa, &store.log, store.treeStore(), .{ .submanifest = .{ .tree = cfg.k }, .tree_cache_bytes = cfg.cache_bytes }, .{ .bounds = &bounds }); defer importer.deinit(); const cpu_start = selfCpuNs(); const import_start = nowNs(io); // No per-commit command ceiling is pinned here. The parser derives it from // the payload budget, so the root commit's `width` files sit orders of // magnitude below it instead of exactly at it; the assertion states the // headroom rather than trusting it. const export_limits: fast_export.Limits = .{ .max_line = 1024 * 1024, .max_data = 1024 * 1024 * 1024, .max_path = 4096, // The benchmark drives synthetic streams whose event count is the // dimension under test; a ceiling here would cap the measurement. .max_events = std.math.maxInt(u64), }; if (fast_export.fileCommandCeiling(export_limits) <= cfg.width) return error.BoundExceeded; try importer.ingestFastExport(stream, export_limits); bounds.finish(); const counters = importer.workCounters(); const retained_state_entries = importer.retainedStateEntries(); const effective_commits = counters.commits; if (effective_commits == 0) return error.GateFailed; const total_import_ns = nowNs(io) - import_start; const total_cpu_ns = selfCpuNs() - cpu_start; const import_ns = if (effective_commits > 1) bounds.replay_ns else total_import_ns; const cpu_ns = if (effective_commits > 1) bounds.replay_cpu_ns else total_cpu_ns; const finalize_cpu_start = selfCpuNs(); const finalize_start = nowNs(io); var refs = try importer.finalizeRefs(.{}); defer refs.deinit(gpa); const finalize_ns = nowNs(io) - finalize_start; const finalize_cpu_ns = selfCpuNs() - finalize_cpu_start; const semantic_start = nowNs(io); const root_mark = cfg.width + 1; const mid_commit = if (effective_commits == 1) 1 else (effective_commits + 1) / 2; const mid_mark = cfg.width + 1 + (mid_commit - 1) * (cfg.changed + 1); const sampled_commit = if (effective_commits == 1) 1 else 1 + (cfg.seed % (effective_commits - 1)); const sampled_mark = cfg.width + 1 + (sampled_commit - 1) * (cfg.changed + 1); const final_mark = cfg.width + 1 + (effective_commits - 1) * (cfg.changed + 1); const root_checkin = try gpa.dupe(u8, try importer.objectForMark(root_mark)); errdefer gpa.free(root_checkin); const mid_checkin = try gpa.dupe(u8, try importer.objectForMark(mid_mark)); errdefer gpa.free(mid_checkin); const sampled_checkin = try gpa.dupe(u8, try importer.objectForMark(sampled_mark)); errdefer gpa.free(sampled_checkin); const final_checkin = try gpa.dupe(u8, try importer.objectForMark(final_mark)); errdefer gpa.free(final_checkin); const side_checkin = if (cfg.branch_every != 0 and cfg.branch_every < effective_commits) try gpa.dupe(u8, try importer.objectForMark(cfg.width + 1 + cfg.branch_every * (cfg.changed + 1))) else null; errdefer if (side_checkin) |checkin| gpa.free(checkin); var merge_index = cfg.merge_every; while (cfg.merge_every != 0 and merge_index < effective_commits) : (merge_index += cfg.merge_every) { if (cfg.branch_every != 0 and merge_index >= cfg.branch_every and merge_index % cfg.branch_every != 0) break; } const merge_checkin = if (cfg.merge_every != 0 and cfg.branch_every != 0 and merge_index < effective_commits) try gpa.dupe(u8, try importer.objectForMark(cfg.width + 1 + merge_index * (cfg.changed + 1))) else null; errdefer if (merge_checkin) |checkin| gpa.free(checkin); const semantic = try rootSemanticDigest(gpa, &store, final_checkin); const semantic_ns = nowNs(io) - semantic_start; const total_wall = corpus_ns + total_import_ns + finalize_ns + semantic_ns; const timed_wall = combinedPhaseNs(import_ns, finalize_ns); const f_cards = bounds.f_cards; // This is reported by the actual policy result root, not selected by arm. const bound: Bound = bounds.fired orelse if (f_cards >= max_f_cards) .f_cards else if (store.file.bytes.items.len >= max_new_store_bytes) .store_bytes else if (total_wall >= max_wall_ns) .wall_time else .none; if (arm == .incremental_tree and counters.inherited_full_tree_materializations != 0) return error.GateFailed; const process_peak_rss_bytes = peakRssBytes(); rss.observe(process_peak_rss_bytes); return .{ .record = .{ .arm = arm, .effective_commits = effective_commits, .phase = .{ .corpus_ns = corpus_ns, .import_ns = import_ns, .finalize_ns = finalize_ns, .semantic_ns = semantic_ns, .finalize_cpu_ns = finalize_cpu_ns, .wall_ns = timed_wall, .cpu_ns = combinedPhaseNs(cpu_ns, finalize_cpu_ns) }, .counters = counters, .store_bytes = store.file.bytes.items.len, .f_cards = f_cards, .bound = bound, .semantic = semantic, .sampled = semantic, .process_peak_rss_bytes = process_peak_rss_bytes, .retained_state_entries = retained_state_entries, }, .store = store, .root_checkin = root_checkin, .mid_checkin = mid_checkin, .side_checkin = side_checkin, .merge_checkin = merge_checkin, .sampled_checkin = sampled_checkin, .final_checkin = final_checkin, }; } fn widthDoublingRatio(gpa: std.mem.Allocator, io: std.Io, cfg: Config, rss: *RssAccumulator) !f64 { const post_seed_commits: u64 = 128; const measured_commits = 1 + post_seed_commits; var samples: [3]f64 = undefined; for (&samples) |*sample| { const one = try runOne(IncrementalTreePolicy, gpa, io, cfg, measured_commits, .incremental_tree, rss); var doubled = cfg; doubled.width *= 2; const two = try runOne(IncrementalTreePolicy, gpa, io, doubled, measured_commits, .incremental_tree, rss); const one_edits = one.counters.changed_paths -| cfg.width; const two_edits = two.counters.changed_paths -| doubled.width; const expected_edits = post_seed_commits * cfg.changed; if (one_edits != expected_edits or two_edits != expected_edits or one.counters.tree_apply_count != post_seed_commits or two.counters.tree_apply_count != post_seed_commits or one.counters.tree_apply_cpu_ns == 0 or two.counters.tree_apply_cpu_ns == 0) return error.GateFailed; sample.* = @as(f64, @floatFromInt(two.counters.tree_apply_cpu_ns)) / @as(f64, @floatFromInt(one.counters.tree_apply_cpu_ns)); } std.sort.pdq(f64, &samples, {}, std.sort.asc(f64)); return samples[1]; } fn corpusBounds(cfg: Config, commits: u64) CorpusBounds { const post_first_commits = commits -| 1; const changed_blobs = std.math.mul(u64, post_first_commits, cfg.changed) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; const blobs = std.math.add(u64, cfg.width, changed_blobs) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; const records = std.math.add(u64, blobs, commits) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; if (records >= max_f_cards) return .{ .records = records, .bytes = max_stream_bytes, .bound = .f_cards }; const blob_bytes = std.math.mul(u64, blobs, max_blob_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const commit_bytes = std.math.mul(u64, commits, max_commit_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const command_bytes = std.math.mul(u64, blobs, max_command_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const bytes = std.math.add(u64, stream_fixed_bytes, blob_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const after_commits = std.math.add(u64, bytes, commit_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const total_bytes = std.math.add(u64, after_commits, command_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; if (total_bytes >= max_stream_bytes) return .{ .records = records, .bytes = total_bytes, .bound = .store_bytes }; return .{ .records = records, .bytes = total_bytes, .bound = .none }; } fn productionGateFailure(bounds_clear: bool, full_semantic_clear: bool, retained_state_clear: bool, rss_clear: bool, wall: f64, cpu: f64, width_ratio: f64) []const u8 { if (!bounds_clear) return "bound_exceeded"; if (!full_semantic_clear) return "full_semantic_mismatch"; if (!retained_state_clear) return "retained_state"; if (!rss_clear) return "peak_rss"; if (!scalePass(wall)) return "scale_wall"; if (!scalePass(cpu)) return "scale_cpu"; if (width_ratio > 1.5) return "width_doubling_cpu"; return "none"; } fn secondCommitOffset(stream: []const u8) ?usize { const first = std.mem.indexOf(u8, stream, "\ncommit ") orelse return null; return std.mem.indexOfPos(u8, stream, first + 1, "\ncommit "); } fn expectSameSemantics(flat: RunRecord, tree: RunRecord) !void { if (!std.mem.eql(u8, &flat.semantic, &tree.semantic)) return error.SemanticMismatch; } fn buildStream(gpa: std.mem.Allocator, cfg: Config, commits: u64) ![]u8 { const bounds = corpusBounds(cfg, commits); if (bounds.bound != .none) return error.BoundExceeded; var out = std.ArrayList(u8).empty; errdefer out.deinit(gpa); try out.ensureTotalCapacity(gpa, @intCast(bounds.bytes)); try out.appendSlice(gpa, "feature done\n"); var mark: u64 = 0; var file: u64 = 0; while (file < cfg.width) : (file += 1) { mark += 1; try appendBlob(&out, gpa, mark, cfg.seed, file, 0); } var main_head: u64 = 0; var side_head: u64 = 0; var commit: u64 = 0; while (commit < commits) : (commit += 1) { var changed: u64 = 0; const command_count = if (commit == 0) cfg.width else cfg.changed; const first_blob = if (commit == 0) @as(u64, 1) else mark + 1; if (commit != 0) while (changed < cfg.changed) : (changed += 1) { mark += 1; try appendBlob(&out, gpa, mark, cfg.seed, try churnIndex(cfg, commit, changed), commit + 1); }; const commit_mark = mark + 1; mark = commit_mark; const on_side = cfg.branch_every != 0 and commit != 0 and commit % cfg.branch_every == 0; const ref = if (on_side) "refs/heads/side" else "refs/heads/main"; const first_parent = if (on_side) if (side_head != 0) side_head else main_head else main_head; try appendFormat(&out, gpa, "commit {s}\nmark :{d}\nauthor Bench <[email protected]> {d} +0000\ncommitter Bench <[email protected]> {d} +0000\ndata 5\nbench\n", .{ ref, mark, 1_700_000_000 + commit, 1_700_000_000 + commit }); if (first_parent != 0) try appendFormat(&out, gpa, "from :{d}\n", .{first_parent}); if (!on_side and side_head != 0 and cfg.merge_every != 0 and commit % cfg.merge_every == 0) try appendFormat(&out, gpa, "merge :{d}\n", .{side_head}); changed = 0; while (changed < command_count) : (changed += 1) try appendFormat(&out, gpa, "M 100644 :{d} file-{d:0>8}\n", .{ first_blob + changed, if (commit == 0) changed else try churnIndex(cfg, commit, changed) }); out.append(gpa, '\n') catch return error.OutOfMemory; if (on_side) side_head = mark else main_head = mark; } try out.appendSlice(gpa, "done\n"); return out.toOwnedSlice(gpa); } fn appendBlob(out: *std.ArrayList(u8), gpa: std.mem.Allocator, mark: u64, seed: u64, file: u64, version: u64) !void { var body: [32]u8 = undefined; std.mem.writeInt(u64, body[0..8], seed, .little); std.mem.writeInt(u64, body[8..16], file, .little); std.mem.writeInt(u64, body[16..24], version, .little); std.mem.writeInt(u64, body[24..32], std.hash.Wyhash.hash(seed, std.mem.asBytes(&file)), .little); try appendFormat(out, gpa, "blob\nmark :{d}\ndata {d}\n", .{ mark, body.len }); try out.appendSlice(gpa, &body); try out.append(gpa, '\n'); } fn appendFormat(out: *std.ArrayList(u8), gpa: std.mem.Allocator, comptime format: []const u8, args: anytype) !void { var buffer: [512]u8 = undefined; const line = std.fmt.bufPrint(&buffer, format, args) catch return error.OutOfMemory; try out.appendSlice(gpa, line); } fn churnIndex(cfg: Config, _: u64, changed: u64) Error!u64 { // Repeatedly mutate the same deterministic sparse working set. This keeps // the workload's inherited-tree cost stable while exercising the canonical // path rewriter rather than accidentally turning a scaling control into a // breadth-first mutation sweep. const index = std.math.add(u64, cfg.seed, changed) catch return error.BadArgs; return index % cfg.width; } fn corpusFingerprint(stream: []const u8) [32]u8 { var digest: [32]u8 = undefined; var hasher = std.crypto.hash.sha2.Sha256.init(.{}); hasher.update(stream); hasher.final(&digest); return digest; } const SemanticRoot = union(enum) { flat: []const artifact.FCard, tree: []const artifact.SCard, }; fn rootSemanticDigest(gpa: std.mem.Allocator, store: *Store, checkin: []const u8) ![32]u8 { var raw: [32]u8 = undefined; const digest = rawHashName(checkin, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; const bytes = (try store.log.content(gpa, rid)) orelse return error.SemanticMismatch; defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); var hasher = std.crypto.hash.sha2.Sha256.init(.{}); const root: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try hashRoot(&hasher, gpa, store, root); var result: [32]u8 = undefined; hasher.final(&result); return result; } fn compareSampledTrees(gpa: std.mem.Allocator, flat_store: *Store, flat_checkin: []const u8, tree_store: *Store, tree_checkin: []const u8) !SampleComparison { var flat_cards = try flattenCheckin(gpa, flat_store, flat_checkin); defer deinitCards(gpa, &flat_cards); var tree_cards = try flattenCheckin(gpa, tree_store, tree_checkin); defer deinitCards(gpa, &tree_cards); std.mem.sort(artifact.FCard, flat_cards.items, {}, lessCard); std.mem.sort(artifact.FCard, tree_cards.items, {}, lessCard); const flat_digest = try digestLeaves(gpa, flat_store, flat_cards.items); const tree_digest = try digestLeaves(gpa, tree_store, tree_cards.items); var equal = flat_cards.items.len == tree_cards.items.len; const common = @min(flat_cards.items.len, tree_cards.items.len); for (flat_cards.items[0..common], tree_cards.items[0..common]) |flat, tree| { if (!std.mem.eql(u8, flat.filename, tree.filename) or flat.mode != tree.mode or !optionalBytesEqual(flat.perm, tree.perm) or !optionalBytesEqual(flat.hash, tree.hash)) equal = false; const flat_blob = try verifiedBlob(gpa, flat_store, flat); defer gpa.free(flat_blob); const tree_blob = try verifiedBlob(gpa, tree_store, tree); defer gpa.free(tree_blob); if (!std.mem.eql(u8, flat_blob, tree_blob)) equal = false; } return .{ .flat_digest = flat_digest, .tree_digest = tree_digest, .equal = equal }; } fn flattenCheckin(gpa: std.mem.Allocator, store: *Store, checkin: []const u8) !std.ArrayList(artifact.FCard) { var cards = std.ArrayList(artifact.FCard).empty; errdefer deinitCards(gpa, &cards); try appendStoredManifest(gpa, store, checkin, &cards); return cards; } fn appendStoredManifest(gpa: std.mem.Allocator, store: *Store, name: []const u8, cards: *std.ArrayList(artifact.FCard)) !void { const bytes = try storedArtifact(gpa, store, name); defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); if (manifest.s.len == 0) { for (manifest.f) |card| try cards.append(gpa, try cloneCard(gpa, card)); return; } for (manifest.s) |sub| try appendStoredManifest(gpa, store, sub.hash, cards); } fn deinitCards(gpa: std.mem.Allocator, cards: *std.ArrayList(artifact.FCard)) void { for (cards.items) |card| { gpa.free(card.filename); if (card.hash) |hash| gpa.free(hash); if (card.perm) |perm| gpa.free(perm); if (card.old_name) |old_name| gpa.free(old_name); } cards.deinit(gpa); } fn digestLeaves(gpa: std.mem.Allocator, store: *Store, cards: []const artifact.FCard) ![32]u8 { var hasher = std.crypto.hash.sha2.Sha256.init(.{}); for (cards) |card| { const blob = try verifiedBlob(gpa, store, card); defer gpa.free(blob); hasher.update(card.filename); hasher.update(@tagName(card.mode)); hasher.update(card.perm orelse ""); hasher.update(card.hash orelse ""); hasher.update(blob); } var digest: [32]u8 = undefined; hasher.final(&digest); return digest; } fn verifiedBlob(gpa: std.mem.Allocator, store: *Store, card: artifact.FCard) ![]u8 { const hash = card.hash orelse return error.SemanticMismatch; const bytes = try storedArtifact(gpa, store, hash); errdefer gpa.free(bytes); var expected: [64]u8 = undefined; if (!std.mem.eql(u8, hash, artifact.artifactName(git_import.import_hash_algo, bytes, &expected))) return error.SemanticMismatch; return bytes; } fn storedArtifact(gpa: std.mem.Allocator, store: *Store, name: []const u8) ![]u8 { var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; return (try store.log.content(gpa, rid)) orelse error.SemanticMismatch; } fn optionalBytesEqual(a: anytype, b: anytype) bool { if (a) |a_value| { if (b) |b_value| return std.mem.eql(u8, a_value, b_value); return false; } return b == null; } fn hashRoot(hasher: anytype, gpa: std.mem.Allocator, store: *Store, root: SemanticRoot) !void { switch (root) { .flat => |flat| for (flat) |card| { hasher.update(card.filename); hasher.update(card.hash orelse ""); hasher.update(card.perm orelse ""); hasher.update(@tagName(card.mode)); }, .tree => |tree| for (tree) |sub| { var raw: [32]u8 = undefined; const digest = rawHashName(sub.hash, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; const bytes = (try store.log.content(gpa, rid)) orelse return error.SemanticMismatch; defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); const child: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try hashRoot(hasher, gpa, store, child); }, } } fn rawHashName(name: []const u8, buffer: *[32]u8) ?[]const u8 { if (name.len != 40) return null; const raw = buffer[0..20]; _ = std.fmt.hexToBytes(raw, name) catch return null; return raw; } fn checkoutRevision(gpa: std.mem.Allocator, io: std.Io) ![40]u8 { const result = std.process.run(gpa, io, .{ .argv = &.{ "fossil", "info" } }) catch return error.ProvenanceUnavailable; defer gpa.free(result.stdout); defer gpa.free(result.stderr); const succeeded = switch (result.term) { .exited => |code| code == 0, else => false, }; if (!succeeded) return error.ProvenanceUnavailable; return revisionFromFossilInfo(result.stdout) orelse error.ProvenanceUnavailable; } fn revisionFromFossilInfo(output: []const u8) ?[40]u8 { var lines = std.mem.splitScalar(u8, output, '\n'); while (lines.next()) |line| { const trimmed = std.mem.trim(u8, line, " \t\r"); if (!std.mem.startsWith(u8, trimmed, "checkout:")) continue; const value = std.mem.trim(u8, trimmed["checkout:".len..], " \t"); var end: usize = 0; while (end < value.len and value[end] != ' ' and value[end] != '\t') : (end += 1) {} if (end != 40) return null; var revision: [40]u8 = undefined; @memcpy(revision[0..], value[0..end]); var raw: [20]u8 = undefined; _ = std.fmt.hexToBytes(raw[0..], revision[0..]) catch return null; return revision; } return null; } fn nowNs(io: std.Io) u64 { const ns = std.Io.Clock.Timestamp.now(io, .awake).raw.nanoseconds; return if (ns < 0) 0 else @intCast(ns); } const RusageSelector = enum(i32) { self = 0, }; const process_cpu_clock = "process_rusage"; fn selfCpuNs() u64 { const usage = std.posix.getrusage(@intFromEnum(RusageSelector.self)); const seconds: u64 = @intCast(usage.utime.sec + usage.stime.sec); const micros: u64 = @intCast(usage.utime.usec + usage.stime.usec); return seconds * std.time.ns_per_s + micros * std.time.ns_per_us; } fn peakRssBytes() u64 { const usage = std.posix.getrusage(@intFromEnum(RusageSelector.self)); const rss: u64 = @intCast(@max(usage.maxrss, 0)); return if (builtin.os.tag == .macos) rss else rss * 1024; } fn combinedPhaseNs(import_ns: u64, finalize_ns: u64) u64 { return std.math.add(u64, import_ns, finalize_ns) catch std.math.maxInt(u64); } fn ratio(big: u64, small: u64) f64 { return @as(f64, @floatFromInt(big)) / @as(f64, @floatFromInt(@max(small, 1))); } fn gateFailure(flat_wall: f64, tree_wall: f64, flat_cpu: f64, tree_cpu: f64, width_ratio: f64, equal_sampled_trees: bool, bounds_clear: bool, retained_state_clear: bool, rss_clear: bool) []const u8 { if (!bounds_clear) return "bound_exceeded"; if (!equal_sampled_trees) return "sampled_tree_mismatch"; if (!retained_state_clear) return "retained_state"; if (!rss_clear) return "peak_rss"; if (!scalePass(flat_wall)) return "flat_wall_scale"; if (!scalePass(tree_wall)) return "tree_wall_scale"; if (!scalePass(flat_cpu)) return "flat_cpu_scale"; if (!scalePass(tree_cpu)) return "tree_cpu_scale"; if (width_ratio > 1.5) return "width_doubling_cpu"; return "none"; } fn medianRatio(records: []const RunRecord, comptime wall: bool) f64 { var values: [7]f64 = undefined; for (records, 0..) |record, index| values[index] = if (wall) record.wall_scale_ratio else record.cpu_scale_ratio; std.mem.sort(f64, values[0..records.len], {}, struct { fn less(_: void, a: f64, b: f64) bool { return a < b; } }.less); return values[records.len / 2]; } fn scalePass(value: f64) bool { return value >= 1.6 and value <= 2.4; } fn retainedStateConstant(cfg: Config, record: RunRecord) bool { const limit: usize = @intCast(6 * (record.counters.blobs + record.counters.commits + record.counters.resets + record.counters.tags + 1)); return record.retained_state_entries <= limit and record.counters.cache_high_water_bytes <= cfg.cache_bytes and (record.arm == .flat_reference or record.counters.inherited_full_tree_materializations == 0); } fn executableHash(io: std.Io, gpa: std.mem.Allocator, executable: []const u8) ![32]u8 { const cwd = try std.process.currentPathAlloc(io, gpa); defer gpa.free(cwd); const path = try std.fs.path.resolve(gpa, &.{ cwd, executable }); defer gpa.free(path); var file = std.Io.Dir.openFileAbsolute(io, path, .{ .mode = .read_only }) catch return error.Io; defer file.close(io); const stat = file.stat(io) catch return error.Io; var hasher = std.crypto.hash.sha2.Sha256.init(.{}); var bytes: [64 * 1024]u8 = undefined; var offset: u64 = 0; while (offset < stat.size) { const len: usize = @intCast(@min(stat.size - offset, @as(u64, bytes.len))); const n = file.readPositionalAll(io, bytes[0..len], offset) catch return error.Io; if (n != len) return error.Io; hasher.update(bytes[0..len]); offset += len; } var result: [32]u8 = undefined; hasher.final(&result); return result; } fn writeJsonl(out: *std.Io.Writer, cfg: Config, executable: [32]u8, fingerprint: [32]u8, record: RunRecord, wall_ratio: f64, cpu_ratio: f64, width_ratio: f64, aggregate_peak_rss_bytes: u64, full_semantic_clear: bool, failed_gate: []const u8) !void { const executable_hex = std.fmt.bytesToHex(executable, .lower); const fingerprint_hex = std.fmt.bytesToHex(fingerprint, .lower); const semantic_hex = std.fmt.bytesToHex(record.semantic, .lower); const sample_hex = std.fmt.bytesToHex(record.sampled, .lower); const equality_json = if (record.equal_sampled_trees) |equal| if (equal) "true" else "false" else "null"; const retained_state_constant = retainedStateConstant(cfg, record); try out.print( "{{\"schema\":\"zit.import-git-benchmark.v1\",\"arm\":\"{s}\",\"binary_sha256\":\"{s}\",\"revision\":\"{s}\",\"platform\":\"{s}-{s}\",\"corpus_fingerprint\":\"{s}\",\"seed\":{d},\"width\":{d},\"requested_commits\":{d},\"effective_commits\":{d},\"semantic_prefix_commits\":{d},\"expected_control_bound\":\"{s}\",\"changed_paths\":{d},\"branch_every\":{d},\"merge_every\":{d},\"k\":{d},\"repetitions\":{d},\"cache_budget_bytes\":{d},\"max_rss_bytes\":{d},", .{ @tagName(record.arm), executable_hex, cfg.revision, @tagName(builtin.os.tag), @tagName(builtin.cpu.arch), fingerprint_hex, cfg.seed, cfg.width, cfg.commits, record.effective_commits, record.semantic_prefix_commits, @tagName(record.expected_control_bound orelse .none), cfg.changed, cfg.branch_every, cfg.merge_every, cfg.k, cfg.reps, cfg.cache_bytes, cfg.max_rss_bytes }, ); try out.print( "\"process_cpu_clock\":\"{s}\",\"phases_ns\":{{\"corpus\":{d},\"import\":{d},\"finalize\":{d},\"finalize_cpu\":{d},\"semantic\":{d},\"wall\":{d},\"cpu\":{d}}},\"counters\":{{\"blobs\":{d},\"commits\":{d},\"resets\":{d},\"tags\":{d},\"changed_paths\":{d},\"max_tree_height\":{d},\"emitted_nodes\":{d},\"reused_nodes\":{d},\"cache_high_water_bytes\":{d},\"inherited_full_tree_materializations\":{d},\"tree_apply_count\":{d},\"tree_apply_cpu_ns\":{d},\"tree_apply_cpu_clock\":\"{s}\"}},", .{ process_cpu_clock, record.phase.corpus_ns, record.phase.import_ns, record.phase.finalize_ns, record.phase.finalize_cpu_ns, record.phase.semantic_ns, record.phase.wall_ns, record.phase.cpu_ns, record.counters.blobs, record.counters.commits, record.counters.resets, record.counters.tags, record.counters.changed_paths, record.counters.max_tree_height, record.counters.emitted_nodes, record.counters.reused_nodes, record.counters.cache_high_water_bytes, record.counters.inherited_full_tree_materializations, record.counters.tree_apply_count, record.counters.tree_apply_cpu_ns, @tagName(record.counters.tree_apply_cpu_clock) }, ); try out.print( "\"store_bytes\":{d},\"emitted_f_cards\":{d},\"bound\":\"{s}\",\"process_peak_rss_bytes\":{d},\"aggregate_peak_rss_bytes\":{d},\"retained_state_entries\":{d},\"semantic_digest\":\"{s}\",\"sampled_tree_digest\":\"{s}\",\"equal_sampled_trees\":{s},\"failed_gate\":\"{s}\",\"gates\":{{\"scale_wall_median\":{d},\"scale_cpu_median\":{d},\"width_doubling_cpu\":{d},\"cache_bound\":{},\"peak_rss_within_limit\":{},\"full_semantic_check\":{},\"retained_state_constant\":{},\"production_no_inherited_full_list\":{}}}}}\n", .{ record.store_bytes, record.f_cards, @tagName(record.bound), record.process_peak_rss_bytes, aggregate_peak_rss_bytes, record.retained_state_entries, semantic_hex, sample_hex, equality_json, failed_gate, wall_ratio, cpu_ratio, width_ratio, record.counters.cache_high_water_bytes <= cfg.cache_bytes, aggregate_peak_rss_bytes <= cfg.max_rss_bytes, full_semantic_clear, retained_state_constant, record.arm == .flat_reference or record.counters.inherited_full_tree_materializations == 0 }, ); } test "git import benchmark corpus bounds reject overflow and oversized streams" { const normal = corpusBounds(.{ .width = 2, .commits = 2, .changed = 1 }, 2); try std.testing.expectEqual(Bound.none, normal.bound); const overflow = corpusBounds(.{ .width = std.math.maxInt(u64), .commits = std.math.maxInt(u64), .changed = std.math.maxInt(u64), }, std.math.maxInt(u64)); try std.testing.expectEqual(Bound.f_cards, overflow.bound); const oversized = corpusBounds(.{ .width = 500_000, .commits = 1, .changed = 1 }, 1); try std.testing.expectEqual(Bound.store_bytes, oversized.bound); const full = corpusBounds(.{ .full = true, .width = 100_000, .commits = 100_000, .changed = 100_000 }, 100_000); try std.testing.expectEqual(Bound.f_cards, full.bound); } test "git import benchmark reports its proactive flat control cap" { const prefix = commonPrefix(.{ .width = 20_000, .commits = 1_000 }); try std.testing.expectEqual(@as(u64, 499), prefix.commits); try std.testing.expectEqual(@as(?Bound, .f_cards), prefix.expected_control_bound); try std.testing.expect(pairedBoundsAccepted(.f_cards, .none, prefix.expected_control_bound)); const full_prefix = commonPrefix(.{ .full = true, .width = 100_000, .commits = 100_000 }); try std.testing.expectEqual(@as(u64, 99), full_prefix.commits); try std.testing.expectEqual(@as(?Bound, .f_cards), full_prefix.expected_control_bound); } test "git import benchmark rejects unexpected control and tree bounds" { try std.testing.expect(!pairedBoundsAccepted(.none, .none, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.store_bytes, .none, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.f_cards, .f_cards, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.f_cards, .none, null)); } test "git import benchmark churn index accepts the max seed boundary and rejects overflow" { const max = std.math.maxInt(u64); try std.testing.expectEqual(max % 2, try churnIndex(.{ .seed = max - 1, .width = 2 }, 0, 1)); try std.testing.expectError(error.BadArgs, churnIndex(.{ .seed = max, .width = 2 }, 0, 1)); const boundary = try parseArgs(&.{ "import-git-bench", "--seed", "18446744073709551614", "--changed", "2" }); try std.testing.expectEqual(max - 1, boundary.seed); try std.testing.expectError(error.BadArgs, parseArgs(&.{ "import-git-bench", "--seed", "18446744073709551615", "--changed", "2" })); } test "git import benchmark production gate includes retained state" { const failed_gate = productionGateFailure(true, true, false, true, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("retained_state", failed_gate); } test "git import benchmark full semantic gate rejects reference disagreement" { const failed_gate = productionGateFailure(true, false, true, true, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("full_semantic_mismatch", failed_gate); } test "git import benchmark scaling includes finalize refs" { const small = combinedPhaseNs(100, 100); const quadratic_finalize = combinedPhaseNs(200, 1_000); try std.testing.expect(!scalePass(ratio(quadratic_finalize, small))); } test "git import benchmark peak RSS gate rejects one byte over limit" { const limit = default_max_rss_bytes; const failed_gate = productionGateFailure(true, true, true, limit + 1 <= limit, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("peak_rss", failed_gate); }