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(), @backingInt(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(@backingInt(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(@backingInt(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);
}