summaryrefslogtreecommitdiff
path: root/test/rollback_bench.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-29 18:19:13 -0300
committerGabriel Schneider <[email protected]>2026-10-29 20:19:19 -0300
commit3b57a72becd6dd6700d996c9c5c000e1cb53e076 (patch)
tree58e59aefe6ae067d95ce4ddf94e8155a9edd3b5a /test/rollback_bench.zig
parent8bad8e3701716a5f2d82d8255a39f3743b13fb96 (diff)
downloadpardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.tar.gz
pardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.zip
phase 5 part A: the speculation and rollback engine, in one process: a walker copy put back where it was, replicas that apply their own input at once and take the authority's tape as the truth, and a harness of typists over delayed links
src/rollback.zig: the replica core's allocator (`Epoch`) knows every allocation, and while a copy is held puts off frees of what was there before and refuses to grow it in place, so what the core held stays where it was. The copy (`Copy`) is the digest's walk saving the bytes of every allocation it reaches, field by field (the derived caches and this process's own too: a safe build's free writes over what it frees, and the frame arena points at what the epoch then frees), but the queues a step drains and the frame statistics; a file's text, its line index and its undo snapshots are pinned instead (made anew at each edit, never written; now freed raw everywhere), checked unchanged in a safe build. Put back, each allocation's bytes go back over it, the epoch's allocations are freed and its put-off frees forgotten; let go, they are made. Tree-sitter's trees, the C heap's, are held the same way (syntax.held_trees). src/replica.zig: an `Authority` records its core's every input to a tape in memory and hands each client's input back as a unit (origin, sequence number, its tape); a `Replica` applies its own input at once, as the authority will (update, then pump), recorded by its own tape (tape.zig's speculation mode), and for each unit in order drops its pending head when the authority recorded the same (inputs, host calls and answers: the fast path), else puts the copy back, replays the units since and this one (every digest checked) and applies its pending inputs again. A host call or a syscall stops a speculation: it is answered harmlessly, undone when it returns, and the input waits for the authority's answer; a clock or environment read is a guess the comparison checks; an emulator is the authority's (terminal.zig's writers stop a speculation; a safe build asserts none changed). The view's events (a resize, the pointer) wait. Messages are bytes: no transport yet. Each client has a view of its own (src/views.zig): the authority goes into it before the client's input (`toView`, taped), the replica's speculation the same, and the copy walks the views not live too (`parked`, each pane's `pv`). test/replicas.zig (`zig build replicas`): one authority and N replicas, a view each (`--shared` puts them in one), each client typing monkey.zig's mix at 50-200 ms over its own link (half the RTT plus 10% jitter, in order), the authority's pty echoing 2 ms later; gates: no replica diverges, every replica's digest is the authority's at quiescence; reported per RTT: inputs applied at once, stopped, waiting, fast paths, rollbacks (mispredicted, foreign), and what a speculative apply, a copy and a rollback cost. 3 clients x 100 inputs at 30, 80 and 207 ms: no divergence over 12 Debug seeds and 20 ReleaseFast ones with a filled heap; ReleaseFast p99 a speculative apply under 0.2 ms, a rollback under 1.6 ms. `zig build rollback-bench` times the real copy now (take, release, an edit, restore). What the replicas found, fixed: a release build reads what the heap had where Debug's fill made two cores agree: `col_panes` and `restore_buf` digested undefined (zeroed now), `terminal.State.reply_dropped` never set at create, `Text.sels` and `PendingPipe.ranges` digested past their length (a walker `len` cuts a slice too). PARDES_REPLICA_FILL fills a replica's allocations to show what is left. Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'test/rollback_bench.zig')
-rw-r--r--test/rollback_bench.zig120
1 files changed, 41 insertions, 79 deletions
diff --git a/test/rollback_bench.zig b/test/rollback_bench.zig
index 721c6f13..38fe011d 100644
--- a/test/rollback_bench.zig
+++ b/test/rollback_bench.zig
@@ -1,14 +1,11 @@
-//! What a replica's rollback copy would cost (docs/next-daemon.md, open
-//! point 3), and what a fork of the authority stalls it for (open point 5).
-//! A typical session and a big one are built in process; for each:
-//! - the state the walker visits (src/walk.zig's digest walk, which is
-//! what speculation can write: views, buffers, registers, counters,
-//! terminal metadata), in bytes;
-//! - the part of it that is pinned blobs: a file's text and its undo
-//! snapshots, which an edit replaces rather than changes
-//! (File.setContentSpan), so a copy keeps a reference;
-//! - the walk's time, the blobs' share of it, and a memcpy of the rest:
-//! a walker copy costs about the walk plus that write.
+//! What a replica's rollback copy costs (docs/next-daemon.md, open point
+//! 3, src/rollback.zig), and what a fork of the authority stalls it for
+//! (open point 5). A typical session and a big one are built in process, on
+//! a rollback epoch's allocator as a replica's core is; for each:
+//! - the copy taken and let go: its time, the bytes it saves, the bytes
+//! it pins (a file's text, its undo snapshots);
+//! - a key that edits a file (`x`) applied on top, as a speculation, and
+//! the copy put back: the apply's time and the restore's.
//! Then a fork of the big one, child gone at once, and the authority's
//! copy-on-write after it.
//!
@@ -69,8 +66,8 @@ fn writeFile(path: []const u8, lines: usize) !void {
}
}
-fn build(s: Session, dir: []const u8) !*pardes.Pardes {
- const core = try pardes.Pardes.init(gpa, .{ .tty_only = true });
+fn build(s: Session, dir: []const u8, a: std.mem.Allocator) !*pardes.Pardes {
+ const core = try pardes.Pardes.init(a, .{ .tty_only = true, .image_allocator = a, .pdf_allocator = a, .tree_sitter_allocator = a, .frame_allocator = a });
core.update(.{ .resize = .{ .cols = 200, .rows = 60 } });
pump(core);
// The shell: pane 0 of a tty boot, its output fed as a pty's.
@@ -112,36 +109,6 @@ fn build(s: Session, dir: []const u8) !*pardes.Pardes {
return core;
}
-/// Where a file's text and its undo snapshots are held: what a copy pins.
-fn blobs(core: *pardes.Pardes, out: *std.ArrayList(*[]u8)) !usize {
- var total: usize = 0;
- for (core.panes) |slot| if (slot) |pane| if (pane.file) |*f| {
- try out.append(gpa, &f.content);
- for (f.history.undo[0..f.history.undo_len]) |*snap| try out.append(gpa, &snap.content);
- for (f.history.redo[0..f.history.redo_len]) |*snap| try out.append(gpa, &snap.content);
- };
- for (out.items) |b| total += b.len;
- return total;
-}
-
-fn walkNs(core: *const pardes.Pardes) u64 {
- var t: [reps]u64 = undefined;
- var sink: u64 = 0;
- for (&t) |*x| {
- const t0 = nowNs();
- sink +%= walk.digest(pardes.Pardes, core);
- x.* = nowNs() - t0;
- }
- std.mem.doNotOptimizeAway(sink);
- return median(&t);
-}
-
-fn walked(core: *const pardes.Pardes) usize {
- var h = walk.Hasher.init(0);
- walk.hash(pardes.Pardes, core, &h);
- return h.total_len;
-}
-
fn median(samples: []u64) u64 {
std.mem.sort(u64, samples, {}, std.sort.asc(u64));
return samples[samples.len / 2];
@@ -161,49 +128,44 @@ pub fn main(init: std.process.Init) !void {
const dir = try std.fmt.bufPrint(&dir_buf, "{s}/rollback-bench-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) });
try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir);
defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {};
- std.debug.print("session panes walked MB blobs MB copy KB walk ms walk ms, blobs out memcpy ms copy ms (est.)\n", .{});
+ std.debug.print("session panes copy KB pinned MB take ms release ms edit ms restore ms\n", .{});
var big: ?*pardes.Pardes = null;
- for (sessions) |s| {
- const core = try build(s, dir);
- var list: std.ArrayList(*[]u8) = .empty;
- defer list.deinit(gpa);
- const blob_bytes = try blobs(core, &list);
- const all = walked(core);
- const walk_ns = walkNs(core);
- // The blobs taken out, as a copy pins them: the walk of what a copy
- // writes, then put back.
- const kept = try gpa.alloc([]u8, list.items.len);
- defer gpa.free(kept);
- for (list.items, kept) |b, *k| {
- k.* = b.*;
- b.* = &.{};
+ var epochs: [sessions.len]*pardes.rollback.Epoch = undefined;
+ for (sessions, &epochs) |s, *e| {
+ e.* = try gpa.create(pardes.rollback.Epoch);
+ e.*.* = .{};
+ const core = try build(s, dir, e.*.allocator());
+ var c: pardes.rollback.Copy = .{};
+ defer c.deinit();
+ var take: [reps]u64 = undefined;
+ var release: [reps]u64 = undefined;
+ for (&take, &release) |*x, *y| {
+ const t0 = nowNs();
+ try c.take(e.*, core);
+ const t1 = nowNs();
+ c.release();
+ x.* = t1 - t0;
+ y.* = nowNs() - t1;
}
- const copy_bytes = walked(core);
- const copy_walk_ns = walkNs(core);
- for (list.items, kept) |b, k| b.* = k;
- const src = try gpa.alloc(u8, @max(copy_bytes, 1));
- defer gpa.free(src);
- const dst = try gpa.alloc(u8, @max(copy_bytes, 1));
- defer gpa.free(dst);
- @memset(src, 1);
- @memset(dst, 0);
- var t: [reps]u64 = undefined;
- for (&t) |*x| {
+ var edit: [reps]u64 = undefined;
+ var restore: [reps]u64 = undefined;
+ for (&edit, &restore) |*x, *y| {
+ try c.take(e.*, core);
const t0 = nowNs();
- @memcpy(dst, src);
- std.mem.doNotOptimizeAway(dst.ptr);
- x.* = nowNs() - t0;
+ key(core, 'x', "x");
+ const t1 = nowNs();
+ c.restore();
+ x.* = t1 - t0;
+ y.* = nowNs() - t1;
}
- const memcpy_ns = median(&t);
var panes: usize = 0;
for (core.panes) |slot| panes += @intFromBool(slot != null);
const ms = 1e-6;
- std.debug.print("{s:<8} {d:>5} {d:>9.1} {d:>8.1} {d:>7.1} {d:>7.3} {d:>18.3} {d:>9.3} {d:>14.3}\n", .{
- s.name, panes,
- @as(f64, @floatFromInt(all)) / 1e6, @as(f64, @floatFromInt(blob_bytes)) / 1e6,
- @as(f64, @floatFromInt(copy_bytes)) / 1e3, @as(f64, @floatFromInt(walk_ns)) * ms,
- @as(f64, @floatFromInt(copy_walk_ns)) * ms, @as(f64, @floatFromInt(memcpy_ns)) * ms,
- @as(f64, @floatFromInt(copy_walk_ns + memcpy_ns)) * ms,
+ std.debug.print("{s:<8} {d:>5} {d:>7.1} {d:>9.1} {d:>7.3} {d:>10.3} {d:>7.3} {d:>10.3}\n", .{
+ s.name, panes,
+ @as(f64, @floatFromInt(c.savedBytes())) / 1e3, @as(f64, @floatFromInt(c.pinnedBytes())) / 1e6,
+ @as(f64, @floatFromInt(median(&take))) * ms, @as(f64, @floatFromInt(median(&release))) * ms,
+ @as(f64, @floatFromInt(median(&edit))) * ms, @as(f64, @floatFromInt(median(&restore))) * ms,
});
if (big) |b| b.deinit();
big = core;