Find the grid cells under layers once a frame, not by scanning every layer for each cell

renderFrame skips the grid cells a body or tag layer paints itself, and it
asked which those are cell by cell: for every cell, twice a frame (counting
instances, then emitting them), bodyLayerAt and tagLayerIn walked all 16 body
layers and all 119 tag layers. In a ReleaseFast profile of a full screen of
src/pardes.zig those walks were about a third of the gui's CPU samples.

coverLayers now fills each live layer's rectangle into a per-cell map once a
frame, and the loops read one byte. The loops only ever asked whether some
layer covers a cell, never which, so overlap order does not enter into it; the
map marks exactly the cells the walks found: a tag layer only its viewport's
first row, and a viewport past the grid only the grid's part of it. The loops
over the layers a panel transition leaves get a second map, built only while
one runs.

A test holds the map to the old walk over a core's layouts (columns, stacked
and collapsed panes, column tags, Tagbottom, message and leader chips) and
3000 random layer sets, some past the grid's edges or at the top of u16.
Hidden captures of 27 layouts (message and prompt chips, a column grip rail,
a PDF, an image, font and tagline changes), with and without leftover edge
pixels, are byte-identical to before.

Over 10 interleaved rounds (160x50 cells), renderFrame's CPU a frame falls
from about 2.0 ms to 0.32-0.37 ms idle, scrolling, typing, under terminal
spew and over a PDF (-82 to -84%, every round), and cell emission from about
1.07 ms to 0.27 ms. The first frame's CPU goes from 6.2 to 4.6 ms.

Co-Authored-By: Claude Opus 5.5 (1M context) <[email protected]>

1 files changed, 106 insertions, 4 deletions

diff --git a/src/gui/gui.zig b/src/gui/gui.zig
index e3229b38..4537f192 100644
--- a/src/gui/gui.zig
+++ b/src/gui/gui.zig
@@ -1800,6 +1800,9 @@ const Gui = struct {
     native_images: std.AutoHashMapUnmanaged(pardes.ImageCacheKey, *c.SDL_GPUTexture) = .empty,
     presented_images: std.ArrayListUnmanaged(SavedImagePlace) = .empty,
     prepared_images: std.ArrayListUnmanaged(PreparedImage) = .empty,
+    /// renderFrame's cover of the grid by layers (coverLayers): this frame's
+    /// layers, then the layers a panel transition is leaving.
+    layer_cover: std.ArrayListUnmanaged(bool) = .empty,
 
     font: *c.UIFont,
     font_bytes: []u8 = &.{},
@@ -2397,6 +2400,7 @@ fn runNative(init: std.process.Init, opts_in: pardes.Options, attach: ?[]const u
         g.native_images.deinit(gpa);
         g.presented_images.deinit(gpa);
         g.prepared_images.deinit(gpa);
+        g.layer_cover.deinit(gpa);
     }
     defer c.SDL_ReleaseGPUTransferBuffer(device, g.image_vxfer);
     defer c.SDL_ReleaseGPUBuffer(device, g.image_vbuf);
@@ -5120,6 +5124,13 @@ fn renderFrame(
     }
 
     const cells: u32 = @as(u32, surface.cols) * surface.rows;
+    try g.layer_cover.resize(gpa, @as(usize, cells) * 2);
+    const covered = g.layer_cover.items[0..cells];
+    coverLayers(covered, surface.cols, surface.rows, surface.bodyLayers(), surface.tagLayers());
+    // Only a panel transition paints the grid under the layers it leaves.
+    const previous_covered = g.layer_cover.items[cells..];
+    if (paint_plan.len > 1)
+        coverLayers(previous_covered, surface.cols, surface.rows, surface.previous_body_layers, surface.previous_tag_layers);
 
     const page = ground(theme_bg, g.transparent);
     const background_opacity = backgroundOpacity(g.applied_window_opacity);
@@ -5143,7 +5154,7 @@ fn renderFrame(
     while (row < surface.rows) : (row += 1) {
         var col: u16 = 0;
         while (col < surface.cols) : (col += 1) {
-            if (bodyLayerAt(surface, col, row) != null or tagLayerIn(surface.tagLayers(), col, row) != null) continue;
+            if (covered[@as(usize, row) * surface.cols + col]) continue;
             const batch_index = paintBatchAt(&paint_plan, col, row);
             const track = paint_plan.batches[batch_index].track;
             const data_effect = if (track) |active|
@@ -5172,7 +5183,7 @@ fn renderFrame(
             var col: u16 = 0;
             while (col < surface.cols) : (col += 1) {
                 if (!boxContains(track.contentBox(), col, row)) continue;
-                if (bodyLayerIn(surface.previous_body_layers, col, row) != null or tagLayerIn(surface.previous_tag_layers, col, row) != null) continue;
+                if (previous_covered[@as(usize, row) * surface.cols + col]) continue;
                 const destination = if (duplicate_under) &paint_plan.batches[0] else batch;
                 const logical_idx: u32 = @as(u32, row) * surface.cols + col;
                 destination.cell_count = std.math.add(
@@ -5246,7 +5257,7 @@ fn renderFrame(
             const line_cursor: ?usize = if (surface.cursor) |cu| if (cu.y == row) cu.x else null else null;
             var col: u16 = 0;
             while (col < surface.cols) : (col += 1) {
-                if (bodyLayerAt(surface, col, row) != null or tagLayerIn(surface.tagLayers(), col, row) != null) continue;
+                if (covered[@as(usize, row) * surface.cols + col]) continue;
                 const batch_index = paintBatchAt(&paint_plan, col, row);
                 const track = paint_plan.batches[batch_index].track;
                 const logical_idx: u32 = @as(u32, row) * surface.cols + col;
@@ -5340,7 +5351,7 @@ fn renderFrame(
                 var col: u16 = 0;
                 while (col < surface.cols) : (col += 1) {
                     if (!boxContains(track.contentBox(), col, row)) continue;
-                    if (bodyLayerIn(surface.previous_body_layers, col, row) != null or tagLayerIn(surface.previous_tag_layers, col, row) != null) continue;
+                    if (previous_covered[@as(usize, row) * surface.cols + col]) continue;
                     const destination: usize = if (duplicate_under) 0 else batch_index;
                     emitSurfaceCell(
                         g,
@@ -5632,6 +5643,97 @@ fn tagLayerIn(layers: []const pardes.TagLayer, col: u16, row: u16) ?*const parde
     return null;
 }
 
+/// Marks the grid cells a body or tag layer covers, which the layers paint
+/// themselves: the grid's cell loops skip them. Filling each layer's rectangle
+/// once replaces scanning every layer for every cell, which was a third of the
+/// gui's CPU on a full screen of text. It marks exactly the cells bodyLayerIn
+/// and tagLayerIn find a layer for: a tag layer covers only its viewport's
+/// first row, and a viewport past the grid covers the grid's part of it.
+fn coverLayers(cover: []bool, cols: u16, rows: u16, body_layers: []const pardes.BodyLayer, tag_layers: []const pardes.TagLayer) void {
+    @memset(cover, false);
+    for (body_layers) |*layer| {
+        const r = layer.viewport;
+        const right = @min(cols, @as(u32, r.x) + r.w);
+        if (layer.rows == 0 or r.x >= right) continue;
+        var y: u32 = r.y;
+        while (y < @min(rows, @as(u32, r.y) + r.h)) : (y += 1) @memset(cover[y * cols ..][r.x..right], true);
+    }
+    for (tag_layers) |*layer| {
+        const r = layer.viewport;
+        const right = @min(cols, @as(u32, r.x) + r.w);
+        if (layer.cols == 0 or r.y >= rows or r.x >= right) continue;
+        @memset(cover[@as(usize, r.y) * cols ..][r.x..right], true);
+    }
+}
+
+fn expectCoverIsScan(cover: []const bool, cols: u16, rows: u16, body_layers: []const pardes.BodyLayer, tag_layers: []const pardes.TagLayer) !void {
+    for (0..rows) |row| for (0..cols) |col| {
+        const scan = bodyLayerIn(body_layers, @intCast(col), @intCast(row)) != null or tagLayerIn(tag_layers, @intCast(col), @intCast(row)) != null;
+        try std.testing.expectEqual(scan, cover[row * cols + col]);
+    };
+}
+
+test "the layer cover is the per-cell layer scan, over a core's layouts and random layers" {
+    // A gui-shaped core: its tagline is narrower and shorter than the body,
+    // so tags and notices are layers.
+    const core = try pardes.Pardes.init(std.testing.allocator, .{ .cols = 97, .rows = 31 });
+    defer core.deinit();
+    core.update(.{ .resize = .{ .cols = 97, .rows = 31, .row_metrics = .{ .body_w = 10, .body_h = 20, .tagline_w = 7, .tagline_h = 13 } } });
+    for (1..4) |id| _ = try core.newShell(id, "");
+    try std.testing.expect(pardes.layout.splitColumn(core, 0, 1, false));
+    pardes.layout.insert(core, 1, 1, 2);
+    pardes.layout.insert(core, 0, 1, 3);
+    var cover: [97 * 31]bool = undefined;
+    var notices = false;
+    for (0..32) |step| {
+        core.settings.tag_bottom = step & 1 != 0;
+        core.settings.column_tags = step & 2 != 0;
+        if (step & 3 == 0) try std.testing.expect(core.executeBuiltinLine(2, "Collapse"));
+        core.leader_on = step & 4 != 0;
+        if (step & 8 != 0) {
+            try std.testing.expect(core.executeBuiltinLine(0, "Msg a message chip over the body"));
+            try std.testing.expect(core.executeBuiltinLine(3, "Msg another"));
+        }
+        const s = try core.render(core.scratch.allocator());
+        try std.testing.expectEqual(@as(usize, cover.len), @as(usize, s.cols) * s.rows);
+        @memset(&cover, true); // what an earlier frame left
+        coverLayers(&cover, s.cols, s.rows, s.bodyLayers(), s.tagLayers());
+        try expectCoverIsScan(&cover, s.cols, s.rows, s.bodyLayers(), s.tagLayers());
+        for (s.tagLayers()) |layer| notices = notices or (layer.cols != 0 and layer.kind == .notice);
+    }
+    try std.testing.expect(notices);
+
+    // Random layers: overlapping, empty, past the grid's right and bottom
+    // edges, and at the top of u16, where x + w overflows it.
+    const gen = struct {
+        fn coordinate(random: std.Random, limit: u16) u16 {
+            if (random.uintLessThan(u8, 12) == 0) return std.math.maxInt(u16) - random.uintLessThan(u16, 3);
+            return random.uintAtMost(u16, limit + 3);
+        }
+        fn rect(random: std.Random, cols: u16, rows: u16) pardes.Rect {
+            return .{ .x = coordinate(random, cols), .y = coordinate(random, rows), .w = coordinate(random, cols), .h = coordinate(random, rows / 2) };
+        }
+    };
+    var prng = std.Random.DefaultPrng.init(0x6c61796572);
+    const random = prng.random();
+    var body: [pardes.MAX_PANES]pardes.BodyLayer = undefined;
+    var tag: [pardes.MAX_TAG_LAYERS]pardes.TagLayer = undefined;
+    var grid: [64 * 40]bool = undefined;
+    for (0..3000) |_| {
+        const cols = random.intRangeAtMost(u16, 1, 64);
+        const rows = random.intRangeAtMost(u16, 1, 40);
+        const empty = random.intRangeAtMost(u8, 2, 5); // about one layer in `empty` is empty
+        for (&body) |*layer| layer.* = .{ .rows = @intFromBool(random.uintLessThan(u8, empty) != 0), .viewport = gen.rect(random, cols, rows) };
+        for (&tag) |*layer| layer.* = .{ .cols = @intFromBool(random.uintLessThan(u8, empty) != 0), .viewport = gen.rect(random, cols, rows) };
+        const bodies = body[0..random.uintAtMost(usize, body.len)];
+        const tags = tag[0..random.uintAtMost(usize, tag.len)];
+        const cells = grid[0 .. @as(usize, cols) * rows];
+        @memset(cells, random.boolean());
+        coverLayers(cells, cols, rows, bodies, tags);
+        try expectCoverIsScan(cells, cols, rows, bodies, tags);
+    }
+}
+
 fn tagLayerCellCount(g: *const Gui, layer: *const pardes.TagLayer) u32 {
     const pixels = @as(u32, layer.viewport.w) * g.cell_w;
     return @min(layer.cols, (pixels + g.tagline_width - 1) / g.tagline_width);