commit 34fcf78b10ce2bb4532c8a2ac8d1fd5a453a7b52
parent f42db2d18a96b8cb19d7bbf8bcac06a2f0726351
Author: James Eversole <james@eversole.co>
Date: Fri, 16 Oct 2026 19:02:36 -0500
Fuse constructor triage and inline collector marking
Diffstat:
4 files changed, 125 insertions(+), 10 deletions(-)
diff --git a/ext/zig/README.md b/ext/zig/README.md
@@ -245,10 +245,11 @@ The reducer is a heap-framed, in-place, call-by-need WHNF machine. It evaluates
terms on demand. Constructor demands dispatch directly; only suspended function,
discriminator, argument and update demands use heap frames. Already-normal
observations avoid borrowing continuation storage unless collection is due.
-Distribution also fuses immediately demanded constructor/constant applications,
-without allocating their private intermediate thunks. These are kernel-rule
-reductions, not source-name intrinsics: they do not demand discarded arguments,
-and charge the same application-entry fuel as the unfused rules. Low-fuel cases
+Distribution and fork-argument triage also fuse immediately demanded
+constructor/constant applications, without allocating their private intermediate
+thunks. These are kernel-rule reductions, not source-name intrinsics: they do not
+demand discarded arguments, and charge the same application-entry fuel as the
+unfused rules. Low-fuel cases
fall back to the unfused path. Tests compare single-invocation fuel boundaries
and resumed results against a literal unfused evaluator.
diff --git a/ext/zig/src/arena.zig b/ext/zig/src/arena.zig
@@ -90,7 +90,8 @@ pub const Arena = struct {
self.gc_interval = @max(minimum, self.last_live *| multiplier);
}
- fn mark(self: *Arena, idx: u32) !void {
+ // Inline the per-edge duplicate check; shared edges normally need no enqueue.
+ inline fn mark(self: *Arena, idx: u32) !void {
if (self.marks.items[idx]) return;
// Mark on enqueue so shared children occupy the work stack only once.
try self.grey.append(self.allocator, idx);
diff --git a/ext/zig/src/reduce.zig b/ext/zig/src/reduce.zig
@@ -163,6 +163,51 @@ pub fn reduce(root: u32, arena: *Arena, fuel: u64) ReduceError!u32 {
break :demand;
},
.fork => |arg| {
+ // Triage produces (handler left) right. The inner
+ // application is private and immediately demanded;
+ // preserve both application-entry charges when fused.
+ if (remaining >= 2) {
+ switch (arena.get(f.right).*) {
+ .leaf => {
+ remaining -= 2;
+ arena.get(orig).* = .{ .fork = .{ .left = arg.left, .right = arg.right } };
+ current = orig;
+ break :demand;
+ },
+ .stem => |k| if (arena.get(k.child).* == .leaf) {
+ remaining -= 2;
+ frame.kind = .update;
+ current = arg.left;
+ continue :demand;
+ },
+ .fork => |k| if (arena.get(k.left).* == .leaf) {
+ const value = arena.get(k.right).*;
+ if (value == .fork and arena.get(value.fork.left).* == .leaf) {
+ remaining -= 2;
+ frame.kind = .update;
+ current = value.fork.right;
+ continue :demand;
+ }
+ switch (value) {
+ .leaf => {
+ remaining -= 2;
+ arena.get(orig).* = .{ .stem = .{ .child = arg.right } };
+ },
+ .stem => |v| {
+ remaining -= 2;
+ arena.get(orig).* = .{ .fork = .{ .left = v.child, .right = arg.right } };
+ },
+ else => {
+ remaining -= 1;
+ arena.get(orig).* = .{ .app = .{ .func = k.right, .arg = arg.right } };
+ },
+ }
+ current = orig;
+ break :demand;
+ },
+ else => {},
+ }
+ }
const inner = try arena.allocApp(f.right, arg.left);
arena.get(orig).* = .{ .app = .{ .func = inner, .arg = arg.right } };
current = orig;
diff --git a/ext/zig/src/reduce_test.zig b/ext/zig/src/reduce_test.zig
@@ -462,7 +462,7 @@ fn equalUnfused(a: *Arena, x: u32, b: *Arena, y: u32) !void {
}
}
-fn fusionFixture(a: *Arena, variant: usize, argument: usize) !u32 {
+fn fusionFixture(a: *Arena, variant: usize, argument: usize, triage: bool) !u32 {
const t = try a.alloc(.leaf);
const k = try stem(a, t);
const payload = try fork(a, k, t);
@@ -486,17 +486,22 @@ fn fusionFixture(a: *Arena, variant: usize, argument: usize) !u32 {
3 => try app(a, try fork(a, t, payload), t),
else => unreachable,
};
+ if (triage) {
+ const pair = try fork(a, x, k);
+ const input = if (argument == 3) try app(a, try fork(a, t, pair), t) else pair;
+ return app(a, try fork(a, try fork(a, k, t), value), input);
+ }
return app(a, try fork(a, try stem(a, value), t), x);
}
-test "fused distribution agrees with literal rules at every small fuel boundary" {
- for (0..9) |variant| for (0..4) |argument| for (0..20) |budget| {
+test "fused distribution and triage agree with literal rules at every small fuel boundary" {
+ for ([_]bool{ false, true }) |triage| for (0..9) |variant| for (0..4) |argument| for (0..20) |budget| {
var expected = Arena.init(testing.allocator);
defer expected.deinit();
var actual = Arena.init(testing.allocator);
defer actual.deinit();
- const x = try fusionFixture(&expected, variant, argument);
- const y = try fusionFixture(&actual, variant, argument);
+ const x = try fusionFixture(&expected, variant, argument, triage);
+ const y = try fusionFixture(&actual, variant, argument, triage);
var fuel: u64 = budget;
const reference_result = unfused(x, &expected, &fuel);
if (reference_result) |_| {
@@ -573,3 +578,66 @@ test "scalar application allocation initializes dirty recycled slots completely"
try testing.expectEqual(hole, try a.alloc(.leaf));
try testing.expect(a.get(hole).* == .leaf);
}
+
+test "fused triage preserves lazy children and shared updates with forced GC" {
+ for ([_]bool{ false, true }) |gc| for (0..5) |variant| {
+ var a = Arena.init(testing.allocator);
+ defer a.deinit();
+ const t = try a.alloc(.leaf);
+ const k = try stem(&a, t);
+ const poison = try app(&a, t, t);
+ a.get(poison).* = .{ .app = .{ .func = poison, .arg = poison } };
+ const payload = try app(&a, try fork(&a, t, t), t);
+ const handler = switch (variant) {
+ 0 => t,
+ 1 => k,
+ 2 => try fork(&a, t, t),
+ 3 => try fork(&a, t, k),
+ 4 => try fork(&a, t, try fork(&a, t, payload)),
+ else => unreachable,
+ };
+ const left = if (variant == 1) payload else poison;
+ const pair = try fork(&a, left, poison);
+ const root = try app(&a, try fork(&a, try fork(&a, poison, poison), handler), pair);
+ try a.roots.append(a.allocator, payload);
+ a.gc_enabled = gc;
+ try a.setGcPolicy(1, 1);
+ const before = a.allocations;
+ _ = try machine.reduce(root, &a, if (variant == 1 or variant == 4) 4 else 3);
+ if (gc) {
+ try testing.expect(a.collections > 0);
+ try a.collect(&.{root});
+ } else try testing.expectEqual(before, a.allocations);
+ switch (variant) {
+ 0 => {
+ try testing.expectEqual(poison, a.get(root).fork.left);
+ try testing.expectEqual(poison, a.get(root).fork.right);
+ },
+ 1, 4 => {
+ try testing.expect(a.get(root).* == .leaf);
+ try testing.expect(a.get(payload).* == .leaf);
+ },
+ 2 => try testing.expectEqual(poison, a.get(root).stem.child),
+ 3 => {
+ try testing.expect(a.get(a.get(root).fork.left).* == .leaf);
+ try testing.expectEqual(poison, a.get(root).fork.right);
+ },
+ else => unreachable,
+ }
+ if (variant != 1 and variant != 4) try testing.expect(a.get(payload).* == .app);
+ };
+}
+
+test "fused triage still demands a selected divergent child" {
+ var a = Arena.init(testing.allocator);
+ defer a.deinit();
+ const t = try a.alloc(.leaf);
+ const poison = try app(&a, t, t);
+ a.get(poison).* = .{ .app = .{ .func = poison, .arg = poison } };
+ const handler = try stem(&a, t);
+ const root = try app(&a, try fork(&a, try fork(&a, t, t), handler), try fork(&a, poison, t));
+ a.gc_enabled = true;
+ try a.setGcPolicy(1, 1);
+ try testing.expectError(error.FuelExhausted, machine.reduce(root, &a, 100));
+ try testing.expectError(error.FuelExhausted, machine.reduce(root, &a, 100));
+}
