From f264dbc4a646da695331fe7401fa013cbb720b6a Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Fri, 30 Oct 2026 00:25:19 -0300 Subject: the walker's digest: a blob's hash made once and folded in as a word (a 100 MB file was 5 ms a digest, two a unit, on the authority); blob fields annotated `.blob`, which the rollback copy's pins read too walk.zig: a field named in a type's `replica.blob` (a file's text, line index and location rows, an undo snapshot's text, a register's values and joined text, the rows an edit dropped, a query's saved rows) holds immutable blobs. A digest hashes one of 4 KiB or more once, keeps the word by its address and length, and folds the length and word in; `forget` drops the word, from memory.freeRaw and freeUnfilled, through which every such blob is freed raw. Only a Debug build (the tests, the harness, replay) hashes the bytes at every digest all the same and panics where the kept word is not their hash: a blob written in place, or freed past its word. A release build, ReleaseSafe the user's own as well as ReleaseFast, takes the word and never panics on a stale one: at worst a divergence, which a replica records and then stops at (nothing resets or rejoins it yet; the notes say so). File.zig: an edit's free of the old text went to `rawFree` itself and so kept its word; the next text of the same length at the same address folded in the old one (the ReleaseFast harness diverged in 162 of 180 replica runs, in `file.content`), and it goes through freeUnfilled now. Registers.zig: `put` makes a new values array rather than writing the old one. rollback.zig: the copy pins what `.blob` names (`pinned` and `pinnedDeep` gone). Measured, ReleaseFast on the perf cores: with a 100 MB file open (PARDES_DIGEST_BENCH=100, replica.zig's bench), a unit of a key into it went from p50 10.45 ms, p99 41.6 ms to p50 24 us, p99 6.1 ms (the first, which makes the word), a digest from 5.18 ms to 10 us. The harness (20 seeds x 120 inputs x 3 clients): rollback p99 9.5 -> 2.6 ms at 30 ms (1.5 and 1.4 ms at 80 and 207), copy p99 0.27 ms; none diverged, none unequal, no delta wrong. Tests: a blob hashed once, its kept word no longer its hash once written in place, its word gone when freed. docs/next-daemon.md: the follow-up. Co-Authored-By: Claude Opus 5.5 --- src/File.zig | 12 +++-- src/Query.zig | 1 + src/Registers.zig | 38 ++++++++------- src/memory.zig | 10 +++- src/replica.zig | 51 ++++++++++++++++++++ src/rollback.zig | 36 ++------------ src/walk.zig | 139 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 233 insertions(+), 54 deletions(-) (limited to 'src') diff --git a/src/File.zig b/src/File.zig index 48a996a4..7acf8dd6 100644 --- a/src/File.zig +++ b/src/File.zig @@ -30,6 +30,7 @@ const long_paint: usize = 16 << 10; /// Content and primary selection at one file edit boundary. Keeping only the /// primary avoids putting Text.max_selections ranges in every history entry. pub const Snapshot = struct { + pub const replica = .{ .blob = .{"content"} }; content: []u8, cur_row: i32, cur_col: i32, @@ -139,7 +140,11 @@ pub const History = struct { pub const State = struct { /// What the replay digest leaves out (src/walk.zig): what is made again /// from the text whenever it is wanted. - pub const replica = .{ .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" } }; + pub const replica = .{ + .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, + // Replaced whole at every edit (setContentSpan), never written. + .blob = .{ "content", "line_starts", "location_rows" }, + }; path: []u8, content: []u8, @@ -840,6 +845,7 @@ fn reportEdit(p: *Pardes, f: *State, new: []const u8) void { } pub const DroppedMarks = struct { + pub const replica = .{ .blob = .{"rows"} }; len: usize, hash: u64, rows: []locations.Row, @@ -908,8 +914,8 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { f.saved_len = f.content.len; } // Raw: `free` overwrites a safe build's freed memory, a whole file's - // worth per keystroke. - if (f.content.len > 0) p.gpa.rawFree(f.content, .of(u8), @returnAddress()); + // worth per keystroke; and its digest word goes (src/walk.zig). + pardes.memory.freeUnfilled(p.gpa, f.content); f.content = new; f.revision +%= 1; f.splice = .{ .revision = f.revision, .head = known.head, .tail = known.tail, .old_len = old_len }; diff --git a/src/Query.zig b/src/Query.zig index 8296aa80..49f58a0e 100644 --- a/src/Query.zig +++ b/src/Query.zig @@ -173,6 +173,7 @@ capped: bool = false, saved: ?Saved = null, pub const Saved = struct { + pub const replica = .{ .blob = .{"rows"} }; content: []u8, rows: []locations.Row, asked: []u8, diff --git a/src/Registers.zig b/src/Registers.zig index 760aff9a..6df7401d 100644 --- a/src/Registers.zig +++ b/src/Registers.zig @@ -12,11 +12,12 @@ const Registers = @This(); list: std.ArrayList(Reg) = .empty, last_search: u21 = '/', -/// A value and the joined text are replaced whole, never written in place, -/// so a replica's rollback copy pins them as it does a file's text -/// (src/rollback.zig `pinned`), and they are freed raw: a safe build's -/// free would write over one the copy still holds. +/// The values (their array too) and the joined text are replaced whole, +/// never written in place (`put` makes a new array), freed raw: blobs +/// (src/walk.zig), which a digest hashes once and a replica's rollback copy +/// pins as it does a file's text. pub const Reg = struct { + pub const replica = .{ .blob = .{ "values", "joined" } }; name: u21, /// gpa-owned, one per range, in document order values: [][]u8, @@ -36,7 +37,7 @@ pub fn deinit(r: *Registers, gpa: std.mem.Allocator) void { fn freeReg(gpa: std.mem.Allocator, reg: *Reg) void { for (reg.values) |v| freeRaw(gpa, v); - gpa.free(reg.values); + freeRaw(gpa, reg.values); if (reg.joined) |j| freeRaw(gpa, j); } @@ -65,19 +66,20 @@ pub fn put(r: *Registers, gpa: std.mem.Allocator, name: u21, bytes: []const u8, }; break :blk &r.list.items[r.list.items.len - 1]; }; - if (fresh or reg.values.len != n) { - const values = gpa.alloc([]u8, n) catch { - gpa.free(copy); - return; - }; - for (values) |*v| v.* = &.{}; - freeReg(gpa, reg); - reg.* = .{ .name = name, .values = values }; - } - freeRaw(gpa, reg.values[i]); - reg.values[i] = copy; - if (reg.joined) |j| freeRaw(gpa, j); - reg.joined = null; + // A new array, the old one's values moved into it but value `i`. + const values = gpa.alloc([]u8, n) catch { + gpa.free(copy); + return; + }; + const keep = !fresh and reg.values.len == n; + for (values, 0..) |*v, j| v.* = if (keep and j != i) reg.values[j] else &.{}; + values[i] = copy; + if (keep) { + freeRaw(gpa, reg.values[i]); + freeRaw(gpa, reg.values); + if (reg.joined) |j| freeRaw(gpa, j); + } else freeReg(gpa, reg); + reg.* = .{ .name = name, .values = values }; } /// The whole register as one text: its values joined by newlines, no diff --git a/src/memory.zig b/src/memory.zig index 1d082964..7adcf914 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -1,5 +1,6 @@ const std = @import("std"); const builtin = @import("builtin"); +const walk = @import("walk.zig"); const config = @import("pardes_config"); const board = config.platform == .esp32p4; @@ -418,7 +419,10 @@ pub fn dupeUnfilled(allocator: Allocator, bytes: []const u8) Allocator.Error![]u /// Frees without the safe-build overwrite `free` does, for text-sized buffers /// freed on every edit. pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { - if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); + if (bytes.len == 0) return; + // A blob's digest word goes with it (walk.zig). + walk.forget(@intFromPtr(bytes.ptr)); + allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); } /// `freeUnfilled` for a slice of any element: a text's line index, made @@ -427,7 +431,9 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { pub fn freeRaw(allocator: Allocator, items: anytype) void { const E = @typeInfo(@TypeOf(items)).pointer.child; const bytes = std.mem.sliceAsBytes(items); - if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); + if (bytes.len == 0) return; + walk.forget(@intFromPtr(bytes.ptr)); + allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); } /// Gives free memory back to the system, the arenas' and libc's, inside its diff --git a/src/replica.zig b/src/replica.zig index a96a056a..0b55a5bf 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -1011,3 +1011,54 @@ test "a delta applied under a speculation outlives its rollback: the terminal st const shown = a.core.panes[shell].?.rows; for (rows_a[rows_a.len - shown ..], rows_r[rows_r.len - shown ..]) |x, y| try std.testing.expectEqualStrings(x, y); } + +/// p50 and p99 of `samples`, sorted in place. +fn spread(samples: []u64) [2]u64 { + std.mem.sort(u64, samples, {}, std.sort.asc(u64)); + return .{ samples[samples.len / 2], samples[@min(samples.len - 1, samples.len * 99 / 100)] }; +} + +test "the authority's units with a big file open: its blobs hashed once (PARDES_DIGEST_BENCH=)" { + const arg = std.c.getenv("PARDES_DIGEST_BENCH") orelse return error.SkipZigTest; + const mb = std.fmt.parseInt(usize, std.mem.span(arg), 10) catch 100; + const gpa = std.heap.c_allocator; + const tmp = std.mem.span(std.c.getenv("TMPDIR") orelse "/tmp"); + var path_buf: [256]u8 = undefined; + const path = try std.fmt.bufPrintSentinel(&path_buf, "{s}/pardes-digest-bench.txt", .{tmp}, 0); + { + const fd = std.c.open(path, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(std.c.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = std.c.close(fd); + var line: [80]u8 = undefined; + var n: usize = 0; + var i: usize = 0; + while (n < mb << 20) : (i += 1) { + const text = try std.fmt.bufPrint(&line, "line {d:0>9} of a big file, as a log or a dump is\n", .{i}); + if (std.c.write(fd, text.ptr, text.len) != @as(isize, @intCast(text.len))) return error.WriteFailed; + n += text.len; + } + } + defer _ = std.c.unlink(path); + const a = try Authority.init(gpa, .{ .cols = 120, .rows = 40, .file = path }, TestHost.host(), true); + defer a.deinit(); + _ = try a.unit(0, 0); + var unit_ns: [40]u64 = undefined; + var digest_ns: [40]u64 = undefined; + for ([_]bool{ false, true }) |on| { + walk.blob_words_on = on; + defer walk.blob_words_on = true; + walk.forgetAll(); + for (&unit_ns, &digest_ns, 0..) |*u, *d, k| { + // A key into the file: a unit as a replica is sent it. + const t0 = nowNs(); + _ = try a.local(.{ .key = .{ .cp = if (k % 2 == 0) 'j' else 'k', .text = if (k % 2 == 0) "j" else "k" } }); + u.* = nowNs() - t0; + const t1 = nowNs(); + _ = digestOf(a); + d.* = nowNs() - t1; + } + const us = spread(&unit_ns); + const ds = spread(&digest_ns); + std.debug.print("{d} MB file, blobs {s}: a unit p50 {d} us p99 {d} us; a digest p50 {d} us p99 {d} us\n", .{ mb, if (on) "hashed once" else "hashed whole", us[0] / 1000, us[1] / 1000, ds[0] / 1000, ds[1] / 1000 }); + } +} diff --git a/src/rollback.zig b/src/rollback.zig index a7027da6..37fc481d 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -35,8 +35,8 @@ const Allocator = std.mem.Allocator; const Alignment = std.mem.Alignment; const Pardes = pardes.Pardes; -/// Blobs this long or longer (`pinned`) are pinned, not copied. Checked -/// unchanged in a safe build when the copy goes. +/// Blobs (walk.blob: fields annotated `.blob`) this long or longer are +/// pinned, not copied. Checked unchanged in a safe build when the copy goes. const blob_min = 4096; const checked = builtin.mode == .debug or builtin.mode == .safe; @@ -198,8 +198,6 @@ pub const Copy = struct { /// of the blobs: a file's text or an undo snapshot's. where: []const u8 = "", pinnable: bool = false, - /// Whether it is a blob of rows that own allocations of their own. - deep: bool = false, const Region = struct { addr: usize, off: usize, len: usize }; const Pin = struct { addr: usize, len: usize, hash: u64, where: []const u8 }; @@ -344,8 +342,7 @@ pub const Copy = struct { if (attr.@"comptime" or comptime (annotated(T, "authority", name) or ((annotated(T, "local", name) or annotated(T, "derived", name)) and unsaved(name)))) continue; if (comptime opaqueTo(F)) continue; c.where = @typeName(T) ++ "." ++ name; - c.pinnable = comptime pinned(T, name); - c.deep = comptime pinnedDeep(T, name); + c.pinnable = comptime walk.blob(T, name); if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { const len = comptime walk.lengthOf(T, name).?; if (comptime heapIn(@typeInfo(F).array.child, 0)) for (@field(v, name)[0..walk.lengthIn(v, len)]) |*e| try c.visit(@typeInfo(F).array.child, e); @@ -398,9 +395,8 @@ pub const Copy = struct { if (s.len == 0) return; const addr = @intFromPtr(s.ptr); if (try c.reached([]const E, addr)) return; - const flat = comptime !heapIn(E, 0); - if ((if (flat) c.pinnable else c.deep) and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { - // A blob of rows with allocations of their own pinned whole: + if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { + // A blob of rows with allocations of their own is pinned whole: // they are as immutable as it, and kept alive with it. const bytes = std.mem.sliceAsBytes(s); try c.pins.append(c.meta, .{ .addr = addr, .len = bytes.len, .hash = if (checked) std.hash.Wyhash.hash(0, bytes) else 0, .where = c.where }); @@ -411,28 +407,6 @@ pub const Copy = struct { } }; -/// The blobs: what an edit puts in place of its predecessor, never writes -/// (File.setContentSpan), and frees raw (memory.freeUnfilled, freeRaw). -fn pinned(comptime T: type, comptime name: []const u8) bool { - const File = pardes.panes.File; - return (T == File.State and (std.mem.eql(u8, name, "content") or std.mem.eql(u8, name, "line_starts"))) or - (T == File.Snapshot and std.mem.eql(u8, name, "content")) or - // A register's values and joined text: a yank of a terminal's whole - // grid is megabytes, which every speculation would otherwise copy. - (T == pardes.Registers.Reg and (std.mem.eql(u8, name, "values") or std.mem.eql(u8, name, "joined"))); -} - -/// Blobs of rows that own allocations of their own (a location's path, its -/// colours), the array and they replaced whole and never written, freed raw -/// (locations.freeRows): a file's location rows (5 MB after a flood of -/// search results), the ones an edit dropped, a query's saved. -fn pinnedDeep(comptime T: type, comptime name: []const u8) bool { - const File = pardes.panes.File; - return (T == File.State and std.mem.eql(u8, name, "location_rows")) or - (T == File.DroppedMarks and std.mem.eql(u8, name, "rows")) or - (T == pardes.panes.Query.Saved and std.mem.eql(u8, name, "rows")); -} - fn annotatedStruct(comptime T: type) bool { return @typeInfo(T) == .@"struct" and @hasDecl(T, "replica"); } diff --git a/src/walk.zig b/src/walk.zig index 5060de3d..33247d42 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -23,6 +23,10 @@ //! .len = .{ .{ "jumps", "njumps" } }, //! // What a field holds is made with another allocator on a load. //! .alloc = .{ .{ "image", "image" } }, +//! // Immutable blobs: replaced whole, never written, freed raw +//! // (memory.freeRaw, freeUnfilled). A digest hashes each once and +//! // folds that word in; a replica's rollback copy pins them. +//! .blob = .{ "content" }, //! }; //! //! None of the three kinds is in a digest or a dump. A type with a `pub fn @@ -31,6 +35,100 @@ const std = @import("std"); pub const Hasher = std.hash.Wyhash; +const builtin = @import("builtin"); +/// Only a Debug build hashes a blob's bytes at every digest and checks its +/// kept word; a release one, ReleaseSafe the user's own, takes the word. +const rehash = builtin.mode == .debug; + +/// Whether `T.name` holds immutable blobs (`.blob`): a file's text, an undo +/// snapshot, a register's text, a file's location rows. +pub fn blob(comptime T: type, comptime name: []const u8) bool { + @setEvalBranchQuota(100_000); + if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "blob")) return false; + inline for (T.replica.blob) |n| if (comptime std.mem.eql(u8, n, name)) return true; + return false; +} + +// ---- a blob's hash, made once ---- +// +// A digest walks the whole core at every unit a replica is sent (and every +// unit a replica replays): a 100 MB file was hashed in full each time. A +// blob of `blob_min` bytes or more is hashed once instead, its word kept by +// its address, and the digest folds the word in. The word goes when the +// blob is freed (`forget`, from memory.freeRaw and freeUnfilled: every +// such blob is freed raw, for the rollback copy's pins), so an address +// used again is hashed again. A Debug build hashes the bytes all the same, +// folds those in, and stops where a kept word is not their hash: a blob +// written in place (which the pins forbid too), or freed past `forget`. A +// release build never stops there: a stale word shows as a divergence. + +const blob_min = 4096; +var blob_words: std.AutoHashMapUnmanaged(usize, struct { len: usize, word: u64 }) = .empty; +var blob_lock: std.atomic.Value(bool) = .init(false); +var blob_count: std.atomic.Value(usize) = .init(0); +threadlocal var in_blob: bool = false; +/// Off: every blob hashed whole at every digest, as before (the bench's). +pub var blob_words_on = true; + +fn lockBlobs() void { + while (blob_lock.cmpxchgWeak(false, true, .acquire, .monotonic) != null) std.atomic.spinLoopHint(); +} + +fn unlockBlobs() void { + blob_lock.store(false, .release); +} + +/// The blob at `addr` is freed: its word, if it has one, goes with it. +pub fn forget(addr: usize) void { + if (blob_count.load(.acquire) == 0) return; + lockBlobs(); + defer unlockBlobs(); + if (blob_words.remove(addr)) blob_count.store(blob_words.count(), .release); +} + +/// The word kept for the blob at `addr` (a test's). +pub fn wordOf(addr: usize) ?u64 { + lockBlobs(); + defer unlockBlobs(); + return if (blob_words.get(addr)) |b| b.word else null; +} + +/// Every word forgotten (the bench's cold digests). +pub fn forgetAll() void { + lockBlobs(); + defer unlockBlobs(); + blob_words.clearRetainingCapacity(); + blob_count.store(0, .release); +} + +/// A blob as a digest takes it: its length and its word. +fn hashBlob(comptime E: type, items: []const E, h: *Hasher) void { + const addr = @intFromPtr(items.ptr); + const word: u64 = word: { + const kept: ?u64 = if (blob_words_on) kept: { + lockBlobs(); + defer unlockBlobs(); + const b = blob_words.get(addr) orelse break :kept null; + break :kept if (b.len == items.len) b.word else null; + } else null; + if (!rehash) if (kept) |w| break :word w; + in_blob = false; + defer in_blob = true; + var one = Hasher.init(0); + hashSlice(E, items, &one); + const w = one.final(); + if (kept) |k| if (k != w) std.debug.panic("walk: the {d}-byte blob at 0x{x} is not what its kept word was: written in place, or freed without memory.freeRaw", .{ items.len, addr }); + if (blob_words_on and kept == null) { + lockBlobs(); + defer unlockBlobs(); + blob_words.put(std.heap.page_allocator, addr, .{ .len = items.len, .word = w }) catch {}; + blob_count.store(blob_words.count(), .release); + } + break :word w; + }; + h.update(std.mem.asBytes(&items.len)); + h.update(std.mem.asBytes(&word)); +} pub fn digest(comptime T: type, v: *const T) u64 { var h = Hasher.init(0); @@ -46,6 +144,9 @@ pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 { inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { if (attr.@"comptime" or comptime excluded(T, name)) continue; var h = Hasher.init(0); + const was = in_blob; + in_blob = comptime blob(T, name); + defer in_blob = was; if (comptime lengthOf(T, name)) |len| { hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h); } else hash(F, &@field(v, name), &h); @@ -180,6 +281,9 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { if (attr.@"comptime" or comptime excluded(T, name)) continue; if (comptime opaqueTo(F)) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is " ++ @typeName(F) ++ ", which no walk sees into: say what it is (`replica`)"); + const was = in_blob; + in_blob = comptime blob(T, name); + defer in_blob = was; if (comptime lengthOf(T, name)) |len| { hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h); } else hash(F, &@field(v, name), h); @@ -214,6 +318,7 @@ fn hashInt(comptime I: type, n: I, h: *Hasher) void { } fn hashSlice(comptime E: type, items: []const E, h: *Hasher) void { + if (in_blob and items.len * @sizeOf(E) >= blob_min) return hashBlob(E, items, h); h.update(std.mem.asBytes(&items.len)); if (comptime flat(E)) return h.update(std.mem.sliceAsBytes(items)); for (items) |*e| hash(E, e, h); @@ -1584,3 +1689,37 @@ test "a dump that is not one, or is cut short, is refused" { // What it made before the end is freed again. try std.testing.expectError(error.EndOfDump, load(S, gpa, bytes[0 .. bytes.len - 2], null)); } + +test "a blob is hashed once and folded in as a word; one written in place is not its word, which a Debug build checks; a freed one's word goes" { + const memory = @import("memory.zig"); + const digestOfBlob = struct { + fn of(items: []const u8) u64 { + var h = Hasher.init(0); + hashSlice(u8, items, &h); + return h.final(); + } + }.of; + const gpa = std.testing.allocator; + const File = struct { + pub const replica = .{ .blob = .{"content"} }; + content: []u8, + cursor: u32 = 0, + }; + const text = try gpa.alloc(u8, 64 << 10); + @memset(text, 'a'); + var f: File = .{ .content = text }; + const before = digest(File, &f); + try std.testing.expect(wordOf(@intFromPtr(text.ptr)) != null); + // The same word again: nothing it holds moved. + try std.testing.expectEqual(before, digest(File, &f)); + // Written in place, which a blob never is: its kept word is no longer + // its hash, which a Debug build's digest checks (and panics at) where a + // release build's would fold the old word in. + text[1000] = 'b'; + try std.testing.expect(wordOf(@intFromPtr(text.ptr)).? != digestOfBlob(text)); + text[1000] = 'a'; + try std.testing.expectEqual(digestOfBlob(text), wordOf(@intFromPtr(text.ptr)).?); + // Freed, its word goes: an address used again is hashed again. + memory.freeUnfilled(gpa, text); + try std.testing.expect(wordOf(@intFromPtr(text.ptr)) == null); +} -- cgit v1.3