optimize and harness PDF sections navigation

1 files changed, 550 insertions, 0 deletions

diff --git a/test/pdf_sections_bench.zig b/test/pdf_sections_bench.zig
new file mode 100644
index 00000000..bb3fc827
--- /dev/null
+++ b/test/pdf_sections_bench.zig
@@ -0,0 +1,550 @@
+//! ReleaseFast scoreboard for the PDF outline -> +PdfSections path.
+//!
+//!   zig build pdf-sections-bench -Doptimize=ReleaseFast
+//!   zig build pdf-sections-bench -Doptimize=ReleaseFast -- --json
+//!   zig build pdf-sections-bench -Doptimize=ReleaseFast -- --warmup 5 --reps 31
+//!
+//! Setup, destruction, semantic checksums, and reporting are outside each
+//! timer. The two interactive scenarios batch tiny real-core operations and
+//! report nanoseconds per operation; `operations_per_sample` makes that
+//! normalization explicit in both output formats.
+const std = @import("std");
+const libc = std.c;
+const pardes = @import("pardes");
+const pdf = @import("mupdf");
+const bench_config = @import("pdf_sections_bench_config");
+
+pub const std_options: std.Options = .{ .log_level = .err };
+
+const gpa = std.heap.smp_allocator;
+const cached_batch = 128;
+const step_batch = 256;
+const near_limit_items = 4096;
+const near_limit_depth = 64;
+
+const Config = struct {
+    json: bool = false,
+    warmup: usize = 5,
+    reps: usize = 31,
+};
+
+const Identity = struct {
+    items: u64,
+    bytes: u64,
+    checksum: u64,
+
+    fn eql(a: Identity, b: Identity) bool {
+        return a.items == b.items and a.bytes == b.bytes and
+            a.checksum == b.checksum;
+    }
+};
+
+const Sample = struct {
+    ns: u64,
+    identity: Identity,
+};
+
+const Result = struct {
+    name: []const u8,
+    operations_per_sample: usize,
+    min_ns: u64,
+    median_ns: u64,
+    p90_ns: u64,
+    max_ns: u64,
+    identity: Identity,
+};
+
+pub fn main(init: std.process.Init) !void {
+    if (!bench_config.release_fast_core)
+        fatal("the production core must be ReleaseFast; add -Doptimize=ReleaseFast", .{});
+    const args = try init.minimal.args.toSlice(init.arena.allocator());
+    const config = parseArgs(args);
+
+    const fixture = try pdf.makeOutlineTestPdf(gpa);
+    defer gpa.free(fixture);
+    var path_buf: [256]u8 = undefined;
+    const path = try std.fmt.bufPrint(&path_buf, "/tmp/pardes-pdf-sections-bench-{d}.pdf", .{libc.getpid()});
+    try writeFile(path, fixture);
+    defer unlink(path);
+
+    var document = try pdf.Document.open(path);
+    defer document.deinit();
+    var outline = try document.outline(gpa);
+    defer outline.deinit(gpa);
+
+    const synthetic = try makeWorstShape();
+    defer gpa.free(synthetic);
+
+    const results = [_]Result{
+        try measureOutline(path, config),
+        try measureMaterialize(path, outline.entries, config),
+        try measureCachedControl(path, config),
+        try measureCachedReopen(path, config),
+        try measureOrdinalStep(path, config),
+        try measureWorstShape(synthetic, config),
+    };
+
+    if (config.json)
+        reportJson(init.io, config, &results)
+    else
+        reportText(config, &results);
+}
+
+fn parseArgs(args: []const []const u8) Config {
+    var config: Config = .{};
+    var i: usize = 1;
+    while (i < args.len) : (i += 1) {
+        if (std.mem.eql(u8, args[i], "--json")) {
+            config.json = true;
+        } else if (std.mem.eql(u8, args[i], "--warmup") and i + 1 < args.len) {
+            i += 1;
+            config.warmup = parseCount("--warmup", args[i]);
+        } else if (std.mem.eql(u8, args[i], "--reps") and i + 1 < args.len) {
+            i += 1;
+            config.reps = parseCount("--reps", args[i]);
+        } else fatal("usage: pardes-pdf-sections-bench [--json] [--warmup N] [--reps N]", .{});
+    }
+    return config;
+}
+
+fn parseCount(flag: []const u8, text: []const u8) usize {
+    const value = std.fmt.parseUnsigned(usize, text, 10) catch
+        fatal("{s} expects a positive integer", .{flag});
+    if (value == 0 or value > 10_000)
+        fatal("{s} must be in 1..10000", .{flag});
+    return value;
+}
+
+fn measureOutline(path: []const u8, config: Config) !Result {
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        // Document open/close is setup: this row isolates MuPDF outline load,
+        // bridge flattening, and the Zig-owned two-allocation copy.
+        var document = try pdf.Document.open(path);
+        defer document.deinit();
+        const started = nowNs();
+        var outline = try document.outline(gpa);
+        const elapsed = nowNs() -| started;
+        const identity = outlineIdentity(outline.entries);
+        outline.deinit(gpa);
+        try verifyIdentity("outline-load-flatten-real", &expected, identity, round);
+        if (round >= config.warmup) try samples.append(gpa, @max(1, elapsed));
+    }
+    return summarize("outline-load-flatten-real", 1, samples.items, expected.?);
+}
+
+fn measureMaterialize(
+    path: []const u8,
+    entries: []const pdf.OutlineEntry,
+    config: Config,
+) !Result {
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        const started = nowNs();
+        const content = try pardes.PdfSectionRows.render(gpa, path, entries);
+        const elapsed = nowNs() -| started;
+        const identity = contentIdentity(content);
+        gpa.free(content);
+        try verifyIdentity("sections-first-materialize", &expected, identity, round);
+        if (round >= config.warmup) try samples.append(gpa, @max(1, elapsed));
+    }
+    return summarize("sections-first-materialize", 1, samples.items, expected.?);
+}
+
+fn measureCachedReopen(path: []const u8, config: Config) !Result {
+    const core = try preparedCore(path);
+    defer core.deinit();
+    const prepared = preparedReopen(core);
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        var observed: u64 = 0;
+        const started = nowNs();
+        for (0..cached_batch) |operation| {
+            perturbReopen(prepared, operation);
+            // Without the barriers ReleaseFast can observe that every call
+            // leaves the same final fields and coalesce the whole batch into
+            // one re-arm. The empty asm emits no instruction; its portable
+            // memory clobber makes each production call's reads and writes
+            // independently observable to the optimizer.
+            compilerBarrier();
+            core.openPdfSections(0);
+            compilerBarrier();
+            observed +%= observeReopen(prepared);
+        }
+        const elapsed = nowNs() -| started;
+        var identity = sectionsOutputIdentity(core);
+        identity.checksum = mix(identity.checksum, observed);
+        try verifyIdentity("sections-clean-cached-reopen", &expected, identity, round);
+        if (round >= config.warmup)
+            try samples.append(gpa, @max(1, elapsed / cached_batch));
+    }
+    return summarize("sections-clean-cached-reopen", cached_batch, samples.items, expected.?);
+}
+
+/// Cost floor for the anti-elision workload above. This performs the same
+/// varying state writes, barriers, and observation but deliberately omits the
+/// core call. Rearming once after the timer keeps fixture state canonical.
+fn measureCachedControl(path: []const u8, config: Config) !Result {
+    const core = try preparedCore(path);
+    defer core.deinit();
+    const prepared = preparedReopen(core);
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        var observed: u64 = 0;
+        const started = nowNs();
+        for (0..cached_batch) |operation| {
+            perturbReopen(prepared, operation);
+            compilerBarrier();
+            compilerBarrier();
+            observed +%= observeReopen(prepared);
+        }
+        const elapsed = nowNs() -| started;
+        core.openPdfSections(0);
+        var identity = sectionsOutputIdentity(core);
+        identity.checksum = mix(identity.checksum, observed);
+        try verifyIdentity("sections-perturb-observe-control", &expected, identity, round);
+        if (round >= config.warmup)
+            try samples.append(gpa, @max(1, elapsed / cached_batch));
+    }
+    return summarize("sections-perturb-observe-control", cached_batch, samples.items, expected.?);
+}
+
+fn measureOrdinalStep(path: []const u8, config: Config) !Result {
+    const core = try preparedCore(path);
+    defer core.deinit();
+    const owner = core.panes[0].?;
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        owner.search_row = null;
+        core.active = 0;
+        // Untimed first step parks on row zero. Timed n/N then alternates the
+        // root and child, which share a page but carry exact y placement.
+        core.update(.{ .key = .{ .cp = 'n', .text = "n" } });
+        const started = nowNs();
+        for (0..step_batch) |step| {
+            compilerBarrier();
+            core.update(.{ .key = .{
+                .cp = if (step & 1 == 0) 'n' else 'N',
+                .text = if (step & 1 == 0) "n" else "N",
+            } });
+            compilerBarrier();
+        }
+        const elapsed = nowNs() -| started;
+        drainEffects(core);
+        const identity = stepIdentity(core);
+        try verifyIdentity("sections-ordinal-destination-step", &expected, identity, round);
+        if (round >= config.warmup)
+            try samples.append(gpa, @max(1, elapsed / step_batch));
+    }
+    return summarize("sections-ordinal-destination-step", step_batch, samples.items, expected.?);
+}
+
+fn measureWorstShape(entries: []const pdf.OutlineEntry, config: Config) !Result {
+    var samples: std.ArrayList(u64) = .empty;
+    defer samples.deinit(gpa);
+    var expected: ?Identity = null;
+    for (0..config.warmup + config.reps) |round| {
+        const started = nowNs();
+        const content = try pardes.PdfSectionRows.render(gpa, "/tmp/near-limit.pdf", entries);
+        const elapsed = nowNs() -| started;
+        const identity = contentIdentity(content);
+        gpa.free(content);
+        try verifyIdentity("rows-near-limit-worst-shape", &expected, identity, round);
+        if (round >= config.warmup) try samples.append(gpa, @max(1, elapsed));
+    }
+    return summarize("rows-near-limit-worst-shape", 1, samples.items, expected.?);
+}
+
+fn preparedCore(path: []const u8) !*pardes.Pardes {
+    const core = try pardes.Pardes.init(gpa, .{ .file = path, .cols = 80, .rows = 28 });
+    errdefer core.deinit();
+    drainEffects(core);
+    core.openPdfSections(0);
+    drainEffects(core);
+    _ = sectionsOutputIdentity(core);
+    return core;
+}
+
+const PreparedReopen = struct {
+    core: *pardes.Pardes,
+    owner: *pardes.Pane,
+    output: *pardes.Pane,
+    output_id: usize,
+};
+
+fn preparedReopen(core: *pardes.Pardes) PreparedReopen {
+    const owner = core.panes[0] orelse fatal("PDF pane disappeared", .{});
+    const output_id = owner.search_pane orelse fatal("+PdfSections was not armed", .{});
+    return .{
+        .core = core,
+        .owner = owner,
+        .output = core.panes[output_id] orelse fatal("+PdfSections pane disappeared", .{}),
+        .output_id = output_id,
+    };
+}
+
+/// The output bytes and generated revision stay clean. Only transient UI
+/// state varies, so every invocation has observable reset work while still
+/// exercising the production clean-output cache guard.
+fn perturbReopen(prepared: PreparedReopen, operation: usize) void {
+    const marker: i32 = @intCast(operation % 31 + 1);
+    const output_file = &prepared.output.file.?;
+    output_file.scroll = @intCast(operation % 17 + 1);
+    prepared.output.cur_row = marker;
+    prepared.output.cur_col = marker + 1;
+    prepared.output.msel.active = true;
+    prepared.output.vsel.active = true;
+    prepared.output.nsel = 1;
+    prepared.owner.search_pane = null;
+    prepared.owner.search_row = operation % 23;
+    prepared.core.active = prepared.output_id;
+}
+
+fn observeReopen(prepared: PreparedReopen) u64 {
+    const file = prepared.output.file.?;
+    var observed: u64 = file.scroll;
+    observed = observed *% 131 +% @as(u64, @intCast(@max(0, prepared.output.cur_row)));
+    observed = observed *% 131 +% @as(u64, @intCast(@max(0, prepared.output.cur_col)));
+    observed = observed *% 131 +% @intFromBool(prepared.output.msel.active);
+    observed = observed *% 131 +% @intFromBool(prepared.output.vsel.active);
+    observed = observed *% 131 +% prepared.output.nsel;
+    observed = observed *% 131 +% (prepared.owner.search_pane orelse std.math.maxInt(usize));
+    observed = observed *% 131 +% (prepared.owner.search_row orelse std.math.maxInt(usize));
+    observed = observed *% 131 +% prepared.core.active;
+    return observed;
+}
+
+fn drainEffects(core: *pardes.Pardes) void {
+    while (core.nextEffect()) |_| {}
+}
+
+fn sectionsOutputIdentity(core: *pardes.Pardes) Identity {
+    const owner = core.panes[0] orelse fatal("PDF pane disappeared", .{});
+    const output_id = owner.search_pane orelse fatal("+PdfSections was not armed", .{});
+    const output = core.panes[output_id] orelse fatal("+PdfSections pane disappeared", .{});
+    const file = output.file orelse fatal("+PdfSections has no file", .{});
+    var identity = contentIdentity(file.content);
+    identity.checksum = mix(identity.checksum, output.serial);
+    identity.checksum = mix(identity.checksum, file.revision);
+    identity.checksum = mix(identity.checksum, output_id);
+    return identity;
+}
+
+fn stepIdentity(core: *pardes.Pardes) Identity {
+    var identity = sectionsOutputIdentity(core);
+    const owner = core.panes[0].?;
+    const view = owner.pdf.?;
+    identity.checksum = mix(identity.checksum, view.page);
+    identity.checksum = mix(identity.checksum, @as(u64, @bitCast(view.document_scroll_y)));
+    identity.checksum = mix(identity.checksum, owner.search_row orelse std.math.maxInt(usize));
+    identity.checksum = mix(identity.checksum, view.render_revision);
+    return identity;
+}
+
+fn contentIdentity(content: []const u8) Identity {
+    return .{
+        .items = std.mem.count(u8, content, "\n"),
+        .bytes = content.len,
+        .checksum = std.hash.Wyhash.hash(0, content),
+    };
+}
+
+fn outlineIdentity(entries: []const pdf.OutlineEntry) Identity {
+    var checksum: u64 = 0;
+    var bytes: u64 = 0;
+    for (entries) |entry| {
+        checksum = mix(checksum, entry.depth);
+        checksum = mix(checksum, entry.flags);
+        checksum = mix(checksum, @intFromBool(entry.is_open));
+        checksum = std.hash.Wyhash.hash(checksum, &entry.color);
+        if (entry.title) |title| {
+            bytes += title.len;
+            checksum = std.hash.Wyhash.hash(checksum, title);
+        } else checksum = mix(checksum, std.math.maxInt(u64));
+        switch (entry.destination) {
+            .none => checksum = mix(checksum, 0),
+            .internal => |destination| {
+                checksum = mix(checksum, 1);
+                checksum = mix(checksum, destination.page);
+                checksum = mix(checksum, if (destination.x) |x| @as(u32, @bitCast(x)) else std.math.maxInt(u32));
+                checksum = mix(checksum, if (destination.y) |y| @as(u32, @bitCast(y)) else std.math.maxInt(u32));
+            },
+            .external => |uri| {
+                bytes += uri.len;
+                checksum = mix(checksum, 2);
+                checksum = std.hash.Wyhash.hash(checksum, uri);
+            },
+        }
+    }
+    return .{ .items = entries.len, .bytes = bytes, .checksum = checksum };
+}
+
+fn mix(seed: u64, value: anytype) u64 {
+    const Value = @TypeOf(value);
+    const Stable = switch (@typeInfo(Value)) {
+        .comptime_int => u64,
+        else => Value,
+    };
+    var stable: Stable = value;
+    return std.hash.Wyhash.hash(seed, std.mem.asBytes(&stable));
+}
+
+fn makeWorstShape() ![]pdf.OutlineEntry {
+    const entries = try gpa.alloc(pdf.OutlineEntry, near_limit_items);
+    for (entries, 0..) |*entry, ordinal| {
+        const depth: u8 = @intCast(ordinal % near_limit_depth);
+        entry.* = .{
+            .depth = depth,
+            .title = "Worst shape outline title",
+            .is_open = true,
+            .flags = 0,
+            .color = .{ 0, 0, 0 },
+            .destination = if (depth + 1 == near_limit_depth)
+                .{ .internal = .{
+                    .page = ordinal / near_limit_depth,
+                    .x = 11.25,
+                    .y = 47.5,
+                } }
+            else
+                .none,
+        };
+    }
+    return entries;
+}
+
+fn verifyIdentity(
+    name: []const u8,
+    expected: *?Identity,
+    got: Identity,
+    round: usize,
+) !void {
+    if (expected.*) |want| {
+        if (!want.eql(got)) {
+            std.debug.print("pdf-sections-bench: unstable identity in {s} round {d}: expected {x:0>16}, got {x:0>16}\n", .{
+                name, round, want.checksum, got.checksum,
+            });
+            return error.UnstableIdentity;
+        }
+    } else expected.* = got;
+}
+
+fn summarize(
+    name: []const u8,
+    operations_per_sample: usize,
+    samples: []u64,
+    identity: Identity,
+) Result {
+    std.debug.assert(samples.len != 0);
+    std.mem.sort(u64, samples, {}, std.sort.asc(u64));
+    return .{
+        .name = name,
+        .operations_per_sample = operations_per_sample,
+        .min_ns = samples[0],
+        .median_ns = samples[samples.len / 2],
+        .p90_ns = samples[(samples.len * 9) / 10 -| 1],
+        .max_ns = samples[samples.len - 1],
+        .identity = identity,
+    };
+}
+
+fn nowNs() u64 {
+    var ts: std.c.timespec = undefined;
+    _ = std.c.clock_gettime(.MONOTONIC, &ts);
+    return @as(u64, @intCast(ts.sec)) *| 1_000_000_000 +|
+        @as(u64, @intCast(ts.nsec));
+}
+
+/// A host benchmark compiler barrier. MuPDF benchmarks are build-and-run
+/// steps, so they never target the freestanding web backend; an empty volatile
+/// asm with only the abstract memory clobber is valid on every native backend
+/// Zig can run here and costs no machine instruction.
+inline fn compilerBarrier() void {
+    asm volatile ("" ::: .{ .memory = true });
+}
+
+fn reportText(config: Config, results: []const Result) void {
+    std.debug.print("pardes PDF sections benchmark (ReleaseFast)\n", .{});
+    std.debug.print("warmup: {d}, sampled reps: {d}; medians are ns/op\n\n", .{ config.warmup, config.reps });
+    std.debug.print("{s:<42} {s:>10} {s:>10} {s:>10} {s:>10} {s:>8} {s:>8}  {s}\n", .{
+        "scenario", "min", "median", "p90", "max", "items", "bytes", "checksum",
+    });
+    std.debug.print("{s}\n", .{"-" ** 124});
+    for (results) |result| std.debug.print(
+        "{s:<42} {d:>10} {d:>10} {d:>10} {d:>10} {d:>8} {d:>8}  {x:0>16}\n",
+        .{
+            result.name,
+            result.min_ns,
+            result.median_ns,
+            result.p90_ns,
+            result.max_ns,
+            result.identity.items,
+            result.identity.bytes,
+            result.identity.checksum,
+        },
+    );
+    std.debug.print("\nBatched rows divide elapsed time by operations/sample: cached={d}, step={d}.\n", .{ cached_batch, step_batch });
+}
+
+fn reportJson(io: std.Io, config: Config, results: []const Result) void {
+    var out: std.ArrayList(u8) = .empty;
+    defer out.deinit(gpa);
+    out.print(gpa, "{{\"benchmark\":\"pardes-pdf-sections\",\"build\":\"ReleaseFast\",\"warmup\":{d},\"reps\":{d},\"results\":[", .{
+        config.warmup, config.reps,
+    }) catch return;
+    for (results, 0..) |result, i| out.print(
+        gpa,
+        "{s}{{\"scenario\":\"{s}\",\"operations_per_sample\":{d},\"min_ns\":{d},\"median_ns\":{d},\"p90_ns\":{d},\"max_ns\":{d},\"items\":{d},\"bytes\":{d},\"checksum\":\"{x:0>16}\"}}",
+        .{
+            if (i == 0) "" else ",",
+            result.name,
+            result.operations_per_sample,
+            result.min_ns,
+            result.median_ns,
+            result.p90_ns,
+            result.max_ns,
+            result.identity.items,
+            result.identity.bytes,
+            result.identity.checksum,
+        },
+    ) catch return;
+    out.appendSlice(gpa, "]}\n") catch return;
+    std.Io.File.stdout().writeStreamingAll(io, out.items) catch {};
+}
+
+fn writeFile(path: []const u8, bytes: []const u8) !void {
+    var path_buf: [4096]u8 = undefined;
+    const path_z = try std.fmt.bufPrintSentinel(&path_buf, "{s}", .{path}, 0);
+    const fd = libc.open(path_z, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o600));
+    if (fd < 0) return error.OpenFailed;
+    defer _ = libc.close(fd);
+    var offset: usize = 0;
+    while (offset < bytes.len) {
+        const written = libc.write(fd, bytes.ptr + offset, bytes.len - offset);
+        if (written < 0) {
+            if (libc.errno(written) == .INTR) continue;
+            return error.WriteFailed;
+        }
+        offset += @intCast(written);
+    }
+}
+
+fn unlink(path: []const u8) void {
+    var path_buf: [4096]u8 = undefined;
+    const path_z = std.fmt.bufPrintSentinel(&path_buf, "{s}", .{path}, 0) catch return;
+    _ = libc.unlink(path_z);
+}
+
+fn fatal(comptime format: []const u8, args: anytype) noreturn {
+    std.debug.print("pdf-sections-bench: " ++ format ++ "\n", args);
+    std.process.exit(1);
+}