From c0c722167a7c4d370c09eab4be0f777cef43feb4 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 25 Aug 2026 19:16:11 -0300 Subject: Bound the edit path's document scans, and find out they were never the problem The measurement said a keystroke costs 54 us per character already in the line. The source said why: `insertAt` called `lineCount` - `std.mem.count` over every byte - TWICE merely to clamp a row, and then `spliceAlloc` allocated and copied the whole document. Three whole-document passes before one character can be inserted, which fits a linear slope exactly. So it was fixed. `modal.lineSpan` finds a row's byte span in ONE scan that stops at that row, and `insertAt` uses it; a full count is paid only on the rare clamping path where the cursor is past the end. Two tests pin the equivalence, including the edges that make line counting awkward - an empty document, a trailing newline (its own empty last line), and a row past the end. The first version of `lineSpan` disagreed with `lineCount` about an empty document and the test caught it. On the host harness this is a real win, reproduced over three independent runs at matched sample counts: edit-char 1k lines 50k lines 300k lines before 730 us 2996 us 15030 us after 721 us 2414 us 10955 us ratio 0.98x 0.79-0.82x 0.78-0.83x Every operation I did not touch stayed at 1.00x, which is better evidence than any single cell. On the board it changed NOTHING. The slope was 54.3 us/char before and 54.0 after, a ratio of 1.00 over 5 conditions x 7 trials. Not a contradiction - the same fact seen twice. The removed passes are O(document), and this board's document is a few hundred BYTES, so two scans of it cost nothing worth measuring. ## Where the time actually goes `-Dprof` times the two phases on the die with the cycle counter around `pardes_p4_input` and `pardes_p4_render`: chars in line input (parse+edit) render 1 220 us 14804 us 80 212 us 17114 us 240 250 us 24615 us Input is FLAT at ~220 us - 1.5% of a keystroke - and does not grow with the document at all. The ~15 ms floor and every microsecond of the slope are inside `render`. The edit path could be made free and nobody would notice. `soc.flushFlashCache`'s home in soc.zig is what let the profiling build exist at all alongside the responder; `-Dprof` defaults off because it puts a line on the wire per frame, which is the resource being measured. ## The report `experiments/report.typ` gains Experiment 3 and, more importantly, a correction: Experiment 2's mechanism claim was wrong and now says so, with the disproof next to it. The ranked recommendations are reordered - the renderer is now #1 and the change this commit makes is listed unranked, because on this target it buys nothing, which is exactly why it is worth recording. The position table earns its place there too: in a fixed 320-character line, an insert at column 320 costs 33.9 ms and emits 28 bytes, while one at column 0 costs 26.0 ms and emits 81. Output size and latency are not merely uncorrelated on this board, they are inverted - which is the signature of a walk from the start of a line, and the next thing to go looking for. The lesson is the one the instrument exists to enforce. A plausible mechanism, read off the source and consistent with the shape of the data, was wrong about where the time went, and only a measurement inside the firmware could say so. --- src/modal.zig | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 71 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/modal.zig b/src/modal.zig index a98cfeb4..f8093ed8 100644 --- a/src/modal.zig +++ b/src/modal.zig @@ -503,6 +503,36 @@ pub fn lineSlice(content: []const u8, row: usize) []const u8 { return content[start..nl]; } +/// The byte span of line `row`, in ONE scan that stops at that row. +/// +/// This exists because the obvious spelling costs a scan of the WHOLE document per call and the +/// obvious USE of it costs several. `insertAt` below read `lineCount` twice merely to clamp a row, +/// and `lineCount` is `std.mem.count` over every byte; on a 19 MB fixture that was two full passes +/// before a single character could be inserted. Measured with `zig build perf`: `edit-char` on the +/// 300 000-line fixture cost 15.0 ms, against 1.5 ms to render the frame that shows it. +/// +/// Returns null when the row does not exist, so a caller that must clamp pays for the count only on +/// that path - which is the rare one, since a cursor is normally inside its document. +pub const LineSpan = struct { start: usize, end: usize }; + +pub fn lineSpan(content: []const u8, row: usize) ?LineSpan { + // An empty document has no lines at all, which is what `lineCount` says about it - not one + // empty line. Agreeing with that here is what lets `insertAt` fall through to offset 0. + if (content.len == 0) return null; + var start: usize = 0; + var r: usize = 0; + while (r < row) : (r += 1) { + const nl = std.mem.indexOfScalarPos(u8, content, start, '\n') orelse return null; + start = nl + 1; + } + // Row `row` exists if it begins inside the content, OR it is the empty last line after a + // trailing newline - which `lineCount` also counts, so the two agree. + if (start > content.len) return null; + if (start == content.len and !(row == 0 or content.len == 0 or content[content.len - 1] == '\n')) return null; + const end = std.mem.indexOfScalarPos(u8, content, start, '\n') orelse content.len; + return .{ .start = start, .end = end }; +} + // ---- file content mutations. caller frees the returned slice + the old one. ---- fn spliceAlloc(alloc: std.mem.Allocator, content: []const u8, start: usize, end: usize, replacement: []const u8) ![]u8 { const out = try alloc.alloc(u8, content.len - (end - start) + replacement.len); @@ -512,12 +542,15 @@ fn spliceAlloc(alloc: std.mem.Allocator, content: []const u8, start: usize, end: return out; } -// insert `text` at (row, col). col is clamped to the line length. +/// insert `text` at (row, col). col is clamped to the line length. pub fn insertAt(alloc: std.mem.Allocator, content: []const u8, c: Cursor, text: []const u8) ![]u8 { - const row = if (c.row >= lineCount(content)) lineCount(content) -| 1 else c.row; - const line = lineSlice(content, row); - const col = @min(c.col, line.len); - const off = lineStartOffset(content, row) + col; + // One bounded scan on the common path. The fallback keeps the old clamping exactly - a row past + // the end lands on the last line - and only it pays for a full count. + const span = lineSpan(content, c.row) orelse blk: { + const last = lineCount(content) -| 1; + break :blk lineSpan(content, last) orelse LineSpan{ .start = content.len, .end = content.len }; + }; + const off = span.start + @min(c.col, span.end - span.start); return spliceAlloc(alloc, content, off, off, text); } @@ -1520,6 +1553,39 @@ test "word motions cross line" { try std.testing.expectEqual(Cursor{ .row = 0, .col = 2 }, nextWordEnd(w, Cursor{ .row = 0, .col = 0 }, false)); } +test "lineSpan agrees with the whole-document scans it replaces" { + // The bounded scan is only worth having if it is indistinguishable from the pair it replaced, + // including at the edges that make line counting awkward: an empty document, a trailing + // newline (which is its own empty last line), and a row past the end. + for ([_][]const u8{ "", "a", "a\n", "a\nbb\n", "a\nbb\nccc", "\n", "\n\n" }) |content| { + const n = lineCount(content); + var row: usize = 0; + while (row < n) : (row += 1) { + const span = lineSpan(content, row) orelse { + std.debug.print("row {d} of {s} missing\n", .{ row, content }); + return error.MissingRow; + }; + try std.testing.expectEqual(lineStartOffset(content, row), span.start); + try std.testing.expectEqualStrings(lineSlice(content, row), content[span.start..span.end]); + } + // One past the last line must be absent, which is what lets insertAt clamp. + try std.testing.expectEqual(@as(?LineSpan, null), lineSpan(content, n)); + } +} + +test "insertAt still clamps a row past the end onto the last line" { + const gpa = std.testing.allocator; + const content = "a\nbb\nccc"; + const out = try insertAt(gpa, content, .{ .row = 99, .col = 99 }, "X"); + defer gpa.free(out); + try std.testing.expectEqualStrings("a\nbb\ncccX", out); + + // And an in-range insert lands where the old spelling put it. + const mid = try insertAt(gpa, content, .{ .row = 1, .col = 1 }, "X"); + defer gpa.free(mid); + try std.testing.expectEqualStrings("a\nbXb\nccc", mid); +} + test "long word W treats punct as word" { // "foo.bar baz" : W from 0 -> "baz" at 8 (foo.bar is one long word) const lines = [_][]const u8{"foo.bar baz"}; -- cgit v1.3