diff options
| -rw-r--r-- | build.zig | 9 | ||||
| -rw-r--r-- | test/fork_stall.py | 76 | ||||
| -rw-r--r-- | test/rollback_bench.zig | 246 |
3 files changed, 331 insertions, 0 deletions
@@ -1495,6 +1495,15 @@ pub fn build(b: *std.Build) void { const lspbench_check_step = b.step("lspbench-check", "require every configured language probe to complete correctly"); lspbench_check_step.dependOn(&run_lspbench_check.step); + const rollback_bench = b.addExecutable(.{ + .name = "pardes-rollback-bench", + .root_module = b.createModule(.{ .target = target, .optimize = optimize, .root_source_file = b.path("test/rollback_bench.zig"), .link_libc = true }), + }); + rollback_bench.root_module.addImport("pardes", core_module); + const run_rollback_bench = b.addRunArtifact(rollback_bench); + run_rollback_bench.has_side_effects = true; + b.step("rollback-bench", "a replica's rollback copy (walked state, pinned blobs, walk time) for a typical and a big session, and a fork of the big one (-Doptimize=ReleaseFast)").dependOn(&run_rollback_bench.step); + const locations_bench_step = b.step("locations-bench", "measure cold/warm result formatting (-Doptimize=ReleaseFast; CSV on stderr)"); if (optimize != .fast) { locations_bench_step.dependOn(&b.addFail("locations-bench requires -Doptimize=ReleaseFast").step); diff --git a/test/fork_stall.py b/test/fork_stall.py new file mode 100644 index 00000000..c865b6bc --- /dev/null +++ b/test/fork_stall.py @@ -0,0 +1,76 @@ +#!/usr/bin/env python3 +"""What a fork stalls the authority for (docs/next-daemon.md, open point 5: +the join writer as a fork child): a process holding N MB of written +anonymous memory, as a session's heap and arenas are, forks a child that +waits and exits; timed are the fork() itself and the copy-on-write of the +authority's next 64 MB written while the child lives. + + python3 -B test/fork_stall.py [MB ...] (default 100 600 1024 4096) + +On Linux each size runs twice: with transparent huge pages as the system +has them, and with MADV_NOHUGEPAGE (4 KiB pages, as a fragmented heap). +""" +import mmap +import os +import statistics +import sys +import time + +REPS = 9 +COW = 64 << 20 + + +def fill(m, size): + block = b'\1' * (16 << 20) + for at in range(0, size, len(block)): + m[at:at + len(block)] = block[:size - at] + + +def one(size, huge): + m = mmap.mmap(-1, size, flags=mmap.MAP_PRIVATE | mmap.MAP_ANONYMOUS) + if not huge: + m.madvise(mmap.MADV_NOHUGEPAGE) + fill(m, size) + forks, cows = [], [] + for _ in range(REPS): + r, w = os.pipe() + t0 = time.perf_counter_ns() + pid = os.fork() + if pid == 0: + os.read(r, 1) + os._exit(0) + t1 = time.perf_counter_ns() + # What the authority writes next, the child holding its pages. + for at in range(0, min(COW, size), 4096): + m[at] = 2 + t2 = time.perf_counter_ns() + os.write(w, b'x') + os.waitpid(pid, 0) + os.close(r) + os.close(w) + forks.append((t1 - t0) / 1e6) + cows.append((t2 - t1) / 1e6) + # The same writes with no child: the loop's own cost, taken off. + t0 = time.perf_counter_ns() + for at in range(0, min(COW, size), 4096): + m[at] = 3 + loop = (time.perf_counter_ns() - t0) / 1e6 + m.close() + return statistics.median(forks), max(forks), statistics.median(cows) - loop + + +def main(): + sizes = [int(a) for a in sys.argv[1:]] or [100, 600, 1024, 4096] + modes = [True, False] if hasattr(mmap, 'MADV_NOHUGEPAGE') else [True] + print(f'{os.uname().sysname} {os.uname().release}: fork of a process with N MB written, ' + f'median and max of {REPS}; then {COW >> 20} MB written under the child') + for size in sizes: + for huge in modes: + fork_med, fork_max, cow = one(size << 20, huge) + pages = 'system pages' if huge else '4 KiB pages' + print(f'{size:>6} MB {pages:<12} fork {fork_med:8.3f} ms (max {fork_max:8.3f}) ' + f'cow {cow:8.3f} ms', flush=True) + + +if __name__ == '__main__': + main() diff --git a/test/rollback_bench.zig b/test/rollback_bench.zig new file mode 100644 index 00000000..721c6f13 --- /dev/null +++ b/test/rollback_bench.zig @@ -0,0 +1,246 @@ +//! 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. +//! Then a fork of the big one, child gone at once, and the authority's +//! copy-on-write after it. +//! +//! zig build rollback-bench -Dplatform=tty -Doptimize=ReleaseFast +const std = @import("std"); +const libc = std.c; +const pardes = @import("pardes"); +const walk = pardes.walk; + +const gpa = std.heap.c_allocator; + +fn nowNs() u64 { + var ts: libc.timespec = undefined; + _ = libc.clock_gettime(.MONOTONIC, &ts); + return @as(u64, @intCast(ts.sec)) *| 1_000_000_000 +| @as(u64, @intCast(ts.nsec)); +} + +const File = struct { lines: usize, copies: usize = 1 }; + +const Session = struct { + name: []const u8, + files: []const File, + /// The shell's scrollback, fed through its terminal. + scrollback_kb: usize, + /// Insert sessions (`i x Esc`), each an undo step, spread over the files. + edits: usize, +}; + +// 60-column lines: 1k lines is 60 KB, 50k is 3 MB, 300k is 18 MB. +const sessions = [_]Session{ + .{ .name = "typical", .files = &.{ .{ .lines = 1_000, .copies = 3 }, .{ .lines = 50_000 } }, .scrollback_kb = 1024, .edits = 40 }, + .{ .name = "big", .files = &.{ .{ .lines = 1_000, .copies = 8 }, .{ .lines = 50_000, .copies = 4 }, .{ .lines = 300_000 } }, .scrollback_kb = 8 * 1024, .edits = 200 }, +}; + +fn pump(core: *pardes.Pardes) void { + while (core.nextEffect()) |_| {} +} + +fn key(core: *pardes.Pardes, cp: u21, text: []const u8) void { + core.update(.{ .key = .{ .cp = cp, .text = text } }); + pump(core); +} + +fn writeFile(path: []const u8, lines: usize) !void { + var out: std.Io.Writer.Allocating = .init(gpa); + defer out.deinit(); + for (0..lines) |n| try out.writer.print("const value_{d:0>7}: u32 = {d:0>10}; // a line of sixty\n", .{ n, n *% 2654435761 }); + var pathbuf: [4096]u8 = undefined; + const fd = libc.open(try std.fmt.bufPrintSentinel(&pathbuf, "{s}", .{path}, 0), .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = libc.close(fd); + const text = out.written(); + var off: usize = 0; + while (off < text.len) { + const n = libc.write(fd, text.ptr + off, text.len - off); + if (n <= 0) return error.WriteFailed; + off += @intCast(n); + } +} + +fn build(s: Session, dir: []const u8) !*pardes.Pardes { + const core = try pardes.Pardes.init(gpa, .{ .tty_only = true }); + core.update(.{ .resize = .{ .cols = 200, .rows = 60 } }); + pump(core); + // The shell: pane 0 of a tty boot, its output fed as a pty's. + var chunk: std.Io.Writer.Allocating = .init(gpa); + defer chunk.deinit(); + var n: usize = 0; + while (chunk.written().len < s.scrollback_kb * 1024) : (n += 1) + try chunk.writer.print("\x1b[90m[{d:0>6}]\x1b[0m compiling module_{d} ... \x1b[32mok\x1b[0m\r\n", .{ n, n }); + var off: usize = 0; + while (off < chunk.written().len) { + const end = @min(off + 8192, chunk.written().len); + core.update(.{ .output = .{ .pane = 0, .bytes = chunk.written()[off..end] } }); + pump(core); + off = end; + } + var opened: [pardes.MAX_PANES]usize = undefined; + var nopened: usize = 0; + for (s.files, 0..) |f, fi| for (0..f.copies) |c| { + var buf: [512]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, "{s}/f{d}-{d}.zig", .{ dir, fi, c }); + try writeFile(path, f.lines); + pardes.look.lookAt(core, 0, path); + pump(core); + for (core.panes, 0..) |slot, id| if (slot) |pane| if (pane.file) |file| if (std.mem.eql(u8, file.path, path)) { + opened[nopened] = id; + nopened += 1; + }; + }; + if (nopened == 0) return error.NothingOpened; + for (0..s.edits) |e| { + core.active = opened[e % nopened]; + key(core, 'i', "i"); + key(core, 'x', "x"); + key(core, pardes.Key.escape, ""); + } + var arena: std.heap.ArenaAllocator = .init(gpa); + defer arena.deinit(); + _ = try core.render(arena.allocator()); + 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]; +} + +fn rssKb() usize { + var ru: libc.rusage = undefined; + _ = libc.getrusage(libc.rusage.SELF, &ru); + return @intCast(ru.maxrss); +} + +const reps = 15; + +pub fn main(init: std.process.Init) !void { + var dir_buf: [256]u8 = undefined; + const tmp = std.mem.span(libc.getenv("TMPDIR") orelse "/tmp"); + 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", .{}); + 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.* = &.{}; + } + 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| { + const t0 = nowNs(); + @memcpy(dst, src); + std.mem.doNotOptimizeAway(dst.ptr); + x.* = nowNs() - t0; + } + 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, + }); + if (big) |b| b.deinit(); + big = core; + } + // The join writer as a fork child: what fork() holds the authority for, + // and its copy-on-write after, the child alive. The child waits on a + // pipe and exits. + const core = big.?; + defer core.deinit(); + var t: [reps]u64 = undefined; + var cow: [reps]u64 = undefined; + const touch = try gpa.alloc(u8, 64 << 20); + defer gpa.free(touch); + @memset(touch, 1); + for (&t, &cow) |*x, *c| { + var pipe: [2]c_int = undefined; + if (libc.pipe(&pipe) != 0) return error.Pipe; + const t0 = nowNs(); + const pid = libc.fork(); + if (pid == 0) { + var one: [1]u8 = undefined; + _ = libc.read(pipe[0], &one, 1); + libc._exit(0); + } + x.* = nowNs() - t0; + // 64 MB the authority writes while the child holds its pages. + const t1 = nowNs(); + var i: usize = 0; + while (i < touch.len) : (i += 4096) touch[i] +%= 1; + c.* = nowNs() - t1; + _ = libc.close(pipe[0]); + _ = libc.write(pipe[1], "x", 1); + _ = libc.close(pipe[1]); + var status: c_int = 0; + _ = libc.waitpid(pid, &status, 0); + } + std.debug.print("fork of the big session (max RSS {d} MB): {d:.3} ms; then 64 MB written under the child: {d:.3} ms\n", .{ + rssKb() / 1024, @as(f64, @floatFromInt(median(&t))) / 1e6, @as(f64, @floatFromInt(median(&cow))) / 1e6, + }); +} |
