diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-29 18:19:13 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-29 20:19:19 -0300 |
| commit | a8d9eb9e5051521aaeb1a95584729794059b5d83 (patch) | |
| tree | 9a70ead4cb0693385e74c4118eb6d90204596b5d /docs | |
| parent | 3b57a72becd6dd6700d996c9c5c000e1cb53e076 (diff) | |
| download | pardes-a8d9eb9e5051521aaeb1a95584729794059b5d83.tar.gz pardes-a8d9eb9e5051521aaeb1a95584729794059b5d83.zip | |
docs/next-daemon.md: Phase 5 part A notes: the copy put back where it was, speculation checked against the authority's tape, each client in its own view, what release builds read unwritten, and the numbers
Three clients typing 100 inputs a seed at 30, 80 and 207 ms RTT, a view each: no divergence and every replica on the authority's digest at quiescence (Debug 12 seeds, ReleaseFast with a filled heap 20, ReleaseFast timed 20, and 20 in one shared view). ReleaseFast, p50/p99: a speculative apply 35-54/168-183 us, a copy (1.3 MB) 75-94/198-447 us, a rollback 342-569/818-1561 us, the worst a tenth of a frame; rollbacks per input 31%, 76% and 129%, nearly all for another client's unit first, which views do not change (they change what a rollback shows); 2-7% mispredictions, every one a message's HH:MM:SS read in another second. rollback-bench: a typical session's copy 980 KB in 0.044 ms, put back in 0.036; a big one's 1.49 MB in 0.071, 0.051. What proved wrong (a 100 KB copy, rare mispredictions), what is not done (transport, the view's events at once, echo prediction, a single-threaded epoch), and fs.py's mounted-startup hang still on main, shown with main's own binary.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/next-daemon.md | 176 |
1 files changed, 174 insertions, 2 deletions
diff --git a/docs/next-daemon.md b/docs/next-daemon.md index efe5214a..d4f9130e 100644 --- a/docs/next-daemon.md +++ b/docs/next-daemon.md @@ -1136,5 +1136,177 @@ What proved wrong in the design: hashes every dependency, and leaves the OS out on purpose. - Pre-existing on the phase 1 tip, and not this line's: test/fs.py's `mounted-startup` session hangs at startup (its main thread waits on a - futex), the same with the base binary. A ReleaseFast `exit_answers` - run loses its Rclunk race about 1 time in 7 on base, and 1 in 40 here. + futex), the same with the base binary, and still on main after phase 4 + (Phase 5 part A notes). A ReleaseFast `exit_answers` run loses its + Rclunk race about 1 time in 7 on base, and 1 in 40 here. + +## Phase 5 part A notes + +Built 2026-10-29, in one process and with no transport: the rollback copy +(`src/rollback.zig`), the replica engine (`src/replica.zig`), the tape's +speculation mode (`src/tape.zig`), and an in-process harness +(`test/replicas.zig`, `zig build replicas`). `zig build rollback-bench` +now times the real copy. Decisions taken at the forks, with the ponytail +lens: + +- **The copy saves bytes and puts them back where they were.** Its walk + is the digest's (src/walk.zig): views, buffers, registers, counters and + terminal metadata. It saves the bytes of every allocation the walk + reaches, and puts each back over its allocation. That works because the + replica core's allocator (`rollback.Epoch`) changes three things while + a copy is held: + - a free of anything older than the copy is put off; + - growing such an allocation in place is refused, so the core moves it; + - anything allocated meanwhile belongs to the epoch. + + So every pointer in the saved bytes still points at what it pointed at + when the copy was taken. Putting the copy back frees the epoch's + allocations and forgets the put-off frees. Letting the copy go makes + them. Nothing has to know who owns what. +- **Three blobs are pinned instead of copied** (4 KiB and up): a file's + text, its line index and its undo snapshots. An edit puts a new one in + place of the old (File.setContentSpan) and never writes one, so the + copy keeps a reference and the put-off free keeps it alive. A safe + build checks every pin is unchanged when the copy goes. +- **More than the digest's fields are saved.** Within a struct the copy + saves every field: the derived caches, and this process's own state too. + It skips the queues a step drains (asserted empty) and the frame + statistics, and cuts an array at its `len`. Both were measured wrong + first: + - a safe build's `free` writes 0xAA over what it frees, so a cache the + speculation freed came back as that (a line index full of 0xAA, then a + crash); + - this process's own fields (the frame arena, the surface) point at what + the epoch then frees. + + For the same reason, file texts and line indexes are now freed raw + everywhere (`memory.freeRaw`), as setContentSpan already did. +- **A speculation is checked against the authority's tape of the same + input.** The replica applies its own input as the authority will (an + update, then a pump) and records it with its own tape. If the + authority's unit for that input has the same records (inputs, host calls + and their answers, digests aside), the head goes: that is the fast path. + The digests are left out of the comparison because the starting states + are equal by induction. A digest checks every unit a replica replays. +- **Each client has its own view** (src/views.zig). The authority goes + into the client's view before its input (`toView`, which is taped), and + the replica's speculation does the same. So a unit records the switch + only when another view was live, alike on both sides. The views not + live (`parked`, each pane's `pv`) are this process's own fields, and + the copy saves them with the rest. +- **A host call or a syscall stops a speculation, but cannot stop it + midway.** Zig has no unwinding. The call is answered with a harmless + value (an error of its set, null, zeroes, or a union's first zeroable + case), the input runs to its end, and then it is undone: the copy is + put back and the earlier pending inputs applied again. That input, and + those after it, wait for the authority's answer. A read of the clock or + the environment (`tape.value`) is a guess made locally, which the + comparison checks. `watched` is answered false, as the authority's host + says too: a replica draws outside the step. +- **An emulator is the authority's.** Its writers in terminal.zig (feed, + resize, scroll, follow, create, deinit) stop a speculation before they + write. A safe build asserts that a clean speculation left every + terminal's digest as it was. Tree-sitter's trees live on the C heap, + which the epoch cannot see. While a copy is held, `syntax.held_trees` + puts off their frees and frees the epoch's own. +- **The view's events wait** (a resize, the pointer): phase 4. +- **Messages are bytes.** A client's input is a u16 client id, a u32 + sequence number, and the event as detached/wire.zig frames it. A unit is + the input's origin (0 for the authority's own: a pty's output, a setup), + its sequence number, and the authority's tape of it. +- **The harness** is a discrete-event simulation. One authority and three + replicas share one view, each client typing monkey.zig's mix (keys, + typing, pastes, a few commands, resizes and clicks) at 50-200 ms with + pauses. Each link takes half the RTT plus up to 10% of it in jitter, in + order. The session is the tty's own boot (a raw shell over a text pane) + with three files looked at. The authority's pty echoes what it is + written 2 ms later, which makes units of its own. + +Found on the way: phase 1's replay ran Debug, whose 0xAA fill made every +read of unwritten memory alike in two cores. In a release build they read +what the heap had, and replicas diverged at once, from: +- `col_panes`, digested whole and undefined past each column's panes (now + zeroed); +- `restore_buf`, the same (now zeroed); +- `terminal.State.reply_dropped`, never set, since `create` leaves fields + as the heap had them; +- `Text.sels` and `PendingPipe.ranges`, digested past their length (a + `len` now cuts a slice too). + +`PARDES_REPLICA_FILL=0xff` fills a replica's allocations, so that what is +left shows at once. Any replica is a release build, so these mattered. + +Measured on main with views (lyntonns). The ReleaseFast runs were alone +through the perf lock; the correctness sweeps ran beside builds. + +- **Correctness.** Three clients each typed 100 inputs per seed, at RTTs + of 30, 80 and 207 ms. No replica diverged, and every replica ended on + the authority's digest, in all three runs: + - Debug: 12 seeds, a view each; + - ReleaseFast with `PARDES_REPLICA_FILL=0xff`: 20 seeds, a view each; + - ReleaseFast, timed: 20 seeds, a view each and in one shared view. +- **What happened to the inputs, and what it cost** (ReleaseFast, a view + each; times in µs, p50 / p99): + + | RTT | rollbacks per input (mispredicted + another's) | speculative apply | copy (1.3 MB) | rollback | + |---|---|---|---|---| + | 30 ms | 31% (106 + 1745) | 35 / 183 | 75 / 198 | 342 / 818 | + | 80 ms | 76% (257 + 4285) | 54 / 168 | 94 / 447 | 455 / 1318 | + | 207 ms | 129% (423 + 7335) | 50 / 174 | 91 / 373 | 569 / 1561 | + + - Of 6000 inputs a run, 259 to 348 stopped at a host call and waited, + and 434 to 449 were the view's own (resizes and clicks). + - In one shared view, the copy is half the size (0.66 MB), the costs + are half (copy 37 / 152, rollback 184 to 259 at p50), and the + rollbacks are the same: 30%, 70% and 121%. + - The worst rollback, 1.6 ms, is a tenth of a 16.7 ms frame. A + speculative apply is 0.2 ms at worst. +- **The copy alone** (`rollback-bench`, ReleaseFast, single view): + + | session | saved | pinned | take | put back after an edit | + |---|---|---|---|---| + | typical (5 panes) | 980 KB | 36.6 MB | 0.044 ms | 0.036 ms | + | big (14 panes) | 1.49 MB | 286.5 MB | 0.071 ms | 0.051 ms | + + Letting a copy go costs nothing measurable. + +What proved wrong: +- "Views cut the conflicts": they cut what a rollback shows, not how + often one happens. Any unit of another client's, in any view, comes + before this replica's pending inputs in the authority's order, so the + copy goes back and the pending inputs are applied again. Each costs a + third of a millisecond, a tenth of a frame at worst. Telling which + units commute with which pending inputs is the next lever, not a + needed one. +- "A copy of about 100 KB": it is 1 to 1.5 MB. The core struct itself is + most of it (the presentation, the surface, the settings and the column + tags), plus the views' parked state, now that the copy saves all of a + struct and not only what a digest takes. It is still under 0.1 ms. +- "A misprediction is rare": every key that leaves a message stamps it + with the time of day (`HH:MM:SS`). So a key confirmed in another second + than it was applied is recorded differently: 2 to 7% of inputs here. In + the harness both cores share one clock, so this is the floor. Across + machines an offset between the clocks raises it. Part B should guess + the authority's clock (its last confirmed reading, plus the time since + locally), not read its own. +- views.zig left a pane's slot for the live view unwritten, and a slot + holding the live body's selections. A pane closed before that view + parked again freed whatever its slot held. This is fixed in its own + change, before this one. Every replica switches views on every input, + and found it at once. + +Not done, and why: +- No transport: part B. +- The view's events (a resize, a click) still wait for the authority. + With views they could be applied at once. +- A pty write stops a speculation, so a shell's echo is shown late. + Phase 6 predicts the echo. +- The authority's own units (a shell's echo) roll back a replica that has + pending inputs. +- The epoch allocator is single-threaded. A replica core's workers + (images, search) must allocate elsewhere, or hold a lock, in part B. +- A replica keeps a timing sample for every input it applies (the + harness reads them). A long-lived one keeps only counters. +- test/fs.py's `mounted-startup` still hangs on main (lyntonns). The same + hang shows with main's own binary in a workspace of its own, so it is + not this line's. |
