Hazel reports · ^report(38) · the editor and undo · 2026-11-03 · work in progress · after ^report(14) and ^report(36)

Undo, in Time and Space

What does an undo cost in Hazel's editor, in memory and in time? How did we find out, where does the investigation stand, and what comes next? The memory story is ^report(14)'s update (2026-10-14 and 15); the time story is ^report(36) (2026-11-02). This report puts them together and adds one new measurement: the modular editors' outline, rebuilt on every undo and redo, separated from the rest. For Matthew's meeting with Cyrus on 2026-11-04 (^report(37)).

The question#copy link

On 2026-11-03 Matthew read the meeting's agenda, ^report(37). Its undo item mentioned compacted snapshots, a large saving in memory, but never said how large the saving was or how it was found. He asked for one report, all about what undo costs, in time and in space: the investigation so far, where it stands, and what is next. He also asked for the cost of rebuilding the outline, which only the modular editors have, to be separated from the rest. That is the one new measurement here.

Where it stands#copy link

Space: what the undo history keeps#copy link

The undo history (History.Model in src/web/app/History.re) is two lists, the undo stack and the redo stack. Before every edit, the page as it was goes onto the undo stack. On #2597 as built, each entry is a whole page model: every slide's editor, with that editor's syntax, statics and layout. On Full Body that is about 90 MB per edit, and nothing else keeps it. The lists are meant to stop at 250 entries, but they are cut only when the setting cap_undo_stack is on, and Settings.re sets it off.

The capped build levels off once its history is full, but each of its two entries is still a whole page. The compaction keeps no derived data in any entry but the newest, so it levels off at a lower line. #2635, with the same compaction, kept less still; why it is lower than #2597 compacted was not examined. Over 30 edits, #2635 rose to 94 MB at the tenth edit and fell back to 46 MB at the eleventh, and again at the 22nd. The likely cause is the tables of values shared with the evaluation worker, which start over at their cap. That is not confirmed.

Dev today. Dev's History.re at f042cced44 (2026-11-02) still keeps whole page models and cuts them only when cap_undo_stack is on, and its default is still off. Dev's growth per edit has not been measured. Its slides differ from #2597's, so the 90 MB is #2597's figure, not dev's.

How it was found#copy link

^report(14) first ruled out every cache and table it could switch off, each in a build of its own. One of those builds was meant to cap the undo history at 2 states. It changed the 250 in capped_undo_stack_size, but the cut that uses it runs only when the setting is on. So the build kept every state, grew 92 MB per edit like the others, and the history looked innocent. When a cap changes nothing, check that its code runs before ruling it out. Then, in five steps, each one taking a suspect off the list:

1. Not what the browser holds. Over six edits the heap grew from 400 to 900 MB, while the page's event listeners (609), DOM nodes, detached ones included (47,923), observers and timers stayed exactly the same.
2. Not on #2635. The same sampled heap profile, over the same four edits, keeps 37.5 MB on #2635, against 390 MB on #2597, and almost none of it in types, statics, terms or layout.
3. A heap snapshot, at last. On this tab the usual tool killed the renderer at once. The lead was ValueHash's memo of hashes, a WeakMap of roughly two million entries: a test page with a WeakMap that size never finished its snapshot. A probe build keeps that memo only within one synchronous run. The tab still grew 68 MB per edit, and a snapshot after six edits completed: 2.3 GB of JSON in 75 seconds.
4. Two snapshots, one session. V8 keeps each object's snapshot id for the life of the tab. So the objects in a snapshot after edit 6 that a snapshot after edit 3 lacks were made by edits 4 to 6: 12.2 million objects, 257 MB. A dominator tree of the second snapshot (29 million nodes, 4.6 s, computed by a small C program) shows three copies of one 35 MB structure: Full Body's editor with its derived data. Two hang from the first and second entries of the undo history. The third is the one view in the projector view cache, which is replaced, not added to.
5. Confirmed by a build that always cuts the history to 2 states, whatever the setting: 284 MB after 12 edits, against 1,048, in two runs.

The fix was already written. Andrew Blinn had met the same growth on the modular editors, on a much larger program, and fixed it in 6010128b7d (2026-08-26): each page model saved for undo drops its derived data, and the cap always applies. That is why #2635, which has #2469 merged in, did not grow.

What a compacted entry keeps#copy link

On #2635 (History.re at 1d17541aaf), pushing an entry compacts the one below it:

• Dropped: the syntax, replaced by a small shared placeholder marked out of date; the statics; the evaluation states and results.
• Kept: the zippers, the editor's own form of the text and the caret. The code's own comment adds that compacted entries still hold frozen typing contexts and the master segments, and that a deep stack of them runs out of memory on large programs. That is why the cap of 250 stays.
• The newest entry of each stack stays whole, and is compacted only when the next one is pushed above it. That is at most two whole page models.
• Restoring a compacted entry rebuilds its syntax against the live editor's parse and layout caches (Page.carry_over), which hit for every piece the step did not change. Statics and results wait for the typing debounce, as after a keystroke.

So a compacted entry is smaller, but not free. How much it keeps at n definitions, and how much of it consecutive entries share, has not been measured (below).

The price in time#copy link

An entry without its derived data has to rebuild that data when it is restored. ^report(14)'s update timed an edit, an undo and a redo in the browser on Full Body, five runs per build: seconds from the key press to the picture changing.

With the compaction alone, every redo on #2597 took about as long as an edit, and half the undos did too. On #2635 a redo took about three edits. Keeping the newest entry whole gave back the latest undo and redo: on #2635 every one was done within 0.3 s, the check's own polling interval, and the memory kept over 12 edits was the same within about 1 MB. On #2597 it cost 49 MB more (208 against 159). An undo further back than the newest entry still rebuilds.

Time: what a step costs as the program grows#copy link

^report(36) measured an edit, an undo and a redo against the size of the program, in Node, on #2635 after dev's merge day. A program of n definitions, let v0 = 0 in let v1 = v0 + 1 in …, an edit in the middle one, then undos and redos, each through the app's own update loop. In short:

• Every step is linear in the program, a slope of 1.10 to 1.16 on a log-log plot from 800 to 6,400 definitions. At 6,400: an edit 106 ms, an undo 292, a redo 184, and about 78 ms of statics after each.
• The incremental work is constant. Whatever n, a step parses 1 or 2 definitions again, measures 1 or 2 chunks of layout and compares 2 definitions' heads in statics. What grows is the walks around that work: rebuilding the top-level term (38% at 3,200 definitions), statics' walk down the chain of definitions (20%), the outline (15%, on undo and redo only) and layout's walk (6%).
• The undo history itself costs almost nothing in time: an entry is pushed and popped at the head of a list.
• Two fixes, now on #2635, took 31 to 46% off at the two largest sizes. The auto-probe had rebuilt the whole top level's skeleton on every frame (394552d5d0), and completion suggestions were computed after every typed digit (bfa36a6ede).

Figures, tables and code are in ^report(36).

The outline's part, separated#copy link

What the outline is. Outline.of_source builds the tree of a program's definitions, which the sidebar's code map and the agent's view read. It came to #2635 with the modular editors, #2469; its first commit is 99b9e25d7d (2026-10-23). Dev has no outline, so on dev an undo does not pay for one.

Why an undo rebuilds it, and a redo mostly does not. Restoring an entry schedules a second frame, RealizeView, which asks for the program's outline. The outline is memoized on the last four programs, found by the segment's identity and then by Segment.same_program. An undo restores a program that is not among them, so the outline is built from scratch. Each undo leaves its outline in the memo, so after the probe's four undos it holds the four programs the redos will restore, except the last: the program from after the edits, which no undo built, since in the probe an edit never builds an outline (nothing draws the sidebar). So the first three redos find their outline and the last one rebuilds it. ^report(36) noticed that the last redo was slow and could not say why; this is why. In the app the sidebar asks for the outline after edits too, which changes which steps pay for it (below).

How it was separated. From the step times by position, in ^report(36)'s release-build runs after the fixes: an undo's outline is what the undo costs beyond a redo that finds its outline. And from a profile that tells the kinds apart: the probe again (58dae0b427), with one named function per kind of step, built so the profiler can name each function's source and profiled twice at each size. In the profile the outline is 28 to 32% of the undo steps' time and 8 to 10% of the redo steps', the redos' share being their one rebuild in four.

Milliseconds per step, medians: an edit and an undo over all 12 steps (3 runs of 4), a redo that finds its outline over the first three of each run (9), the last redo over 3. "The outline" is the undo minus the redo that finds its outline. The profile's share is the outline's part of the undo steps' profiled time: a separate measurement of the same thing, which reads lower, 28 to 32% against 32 to 40% from the timings, perhaps because the profiler drops samples whose stack it cut off. Read the outline as about a third of an undo.

• An undo is a redo plus the outline. The rebuild is 32 to 40% of an undo from 1,600 definitions up, about 39 ms at 3,200, and it grows with the program like the rest of the step.
• A redo rebuilds it only when its memo misses. In the probe that is the last redo, as slow as an undo or slower; in use, it would be any undo or redo to a program the memo no longer holds.
• Without the outline, a restore still costs 1.7 to 1.9 edits. In the profile, a redo spends about 1.8 times an edit's time rebuilding the program's syntax (CachedSyntax.mk), 534 against 296 ms of profile at 3,200 definitions: a restore rebuilds it against the live caches. It is not only the compaction: the newest entry keeps its syntax whole, and ^report(36) found it restores no faster. Every whole-program pass under it costs 1.8 to 2 times an edit's: the restore rebuilt the syntax twice (below).

With the sidebar, every edit pays for the outline#copy link

The probe draws no view, so nothing asks for the outline after an edit. In the app the sidebar's code map does, whenever it is shown, as it is in the deck's screenshots. So the probe was run once more asking for the outline after every step and once before the edits, as the sidebar's view would, timed on its own (UNDO_VIEW_OUTLINE, 5544ca12a3; the dev-profile build without the profiler, one run per size, so read the ratios).

Milliseconds, medians: edits 2 to 4 (the first edit of a run is slower), undos and redos 1 to 3.

• Each edit rebuilds the outline, about as much again as the edit itself: 44 ms after an edit of 51 at 3,200 definitions, 84 after 113 at 6,400. The edit changed the program, so the memo misses.
• Then an undo finds its outline, since the edits left it in the memo, and costs what a redo does: 89 and 90 ms at 3,200. The fourth undo, to the program before the edits, is out of the memo's four and rebuilds it.
• So the outline is a cost of every step that changes the program, on the edit when the sidebar shows it and on the undo when it does not. Making the outline's build touch only what changed would take it off both. Today its top level walks every definition: Outline.level visits each span of the top level, reusing the entries below an unchanged one.

An undo rebuilt the syntax twice, and the fix#copy link

Found. The probe read PerfTimer's editor-syntax total in every frame (ab7dfd0188). An edit is one frame with one syntax pass, about 40 ms at 3,200 definitions. An undo or a redo is two frames, and each ran a full pass of about the same cost. The second frame is RealizeView, which the restore schedules. It returned through Updated.return, whose is_edit defaults to true, so its calculate marked the restored program's syntax out of date and rebuilt it again. The probe's own counts said so all along: a restore parsed 2 definitions in full and measured 2 chunks, an edit 1 and 1.

The fix (ed4d484671; on #2635's head as 9df1b2601e, pushed for CI to the branch trial/665-realize-not-edit, not to #2635): realizing the view counts as an edit only if it opened or closed a cell, that is, only if it changed the program.

let realized = realize(~info_map, code.view, code);
realized
|> return(~is_edit=realized.program !== code.program, ~historic=false);

Milliseconds per step, medians of one run of 4 per size and build, the dev-profile build in one session: every size before, then every size after. The edit column is after; an edit is unchanged by the fix. "Syntax passes" counts the frames of an undo that spent a millisecond or more rebuilding syntax.

• An undo: 40% off at 3,200 definitions (141 to 84 ms) and 30% at 6,400 (263 to 184). It is now an edit plus the outline.
• A redo: 57% off (96 to 41 ms at 3,200), now what an edit costs.
• A restore now parses 1 definition and measures 1 chunk, like an edit, and the second frame does no syntax work.
• Checked locally, before and after: the test groups that touch undo, the outline and realizing the view all pass (Undo 11, OpenMember 6, UndoCaches 5, UndoStatics 3, ProbePersist 5, OutlineRename 15, OutlineText 47, StackFocus 14). Dev has no RealizeView; #2469 has the same code.

Not yet measured#copy link

• Space against the size of the program, on #2635. What a compacted entry and a whole entry keep at n definitions, and how much consecutive entries share. Zippers are persistent, so an entry after a small edit could share most of its pieces with the one before; that has not been checked.
• Dev's growth per edit, on its own slides, today.
• The sidebar's own cost beyond its outline: drawing its rows. The probe times only the outline it reads.
• An undo in the browser with evaluation and drawing: Node runs no worker and builds no view or DOM.
• Sharing across the worker boundary, which an undo also crosses when it re-evaluates (^ticket(666)).

What next#copy link

1. Make the outline's build touch only the definitions that changed, so that neither an edit with the sidebar shown nor an undo pays a walk of every definition: about 44 ms per edit and 39 per undo at 3,200 definitions. A cheaper first step for undo alone: keep the outline with its undo entry.
2. Put the fix for the second syntax pass on #2635 (9df1b2601e), once its CI is green, and measure an undo again in the browser.
3. Measure space against size on #2635 in Node: the heap after a forced collection with 0, 1, 10 and 100 undo entries, at each size, compacted and whole.
4. Decide dev: a small PR with the compaction and an always-on cap now, or wait for #2469 to bring them (the 2026-10-15 call was to wait).
5. Try the top level as a balanced tree of definitions (^report(36)'s Figure 5). A snapshot of a persistent tree is its root: it shares every node the edit did not touch, so an entry would keep O(log n) new nodes, and an undo could be a swap of roots, with its derived data kept.
6. Time an edit and an undo in the browser on Full Body, with evaluation and drawing.

For the meeting#copy link

• Dev's undo history still keeps every edit's whole editor state. Should dev get the compaction now, or with #2469?
• Should the outline be kept with each undo entry, or found again by the restored program's identity? It is a third of an undo.
• Is the balanced tree of definitions the direction for both costs, time per step and space per entry?

The agenda's item for this is ^report(37), Undo in O(log n)?

How this was put together#copy link

• Space is ^report(14)'s update, measured 2026-10-14 and 15 in Chromium 155 on Full Body: 12 slider edits per run, two forced garbage collections after each, then the page's live JavaScript heap. The times in the price table are from the same update's undo check, five runs per build, read by a DevTools-protocol driver. Both are copied into 038/data/space.json; the update's own data is in 014/data/update-2026-10-14/.
• Time is ^report(36)'s probe, 2026-11-02: medians of 12 steps, 3 runs per build, release build, Node 22.23 on a laptop (Intel Core i7-1370P, Linux). Read from 036/data/steps.json.
• The outline's part is new, 2026-11-03. From ^report(36)'s step times by position in each run of four (its 036/data/steps.json, the release build after the fixes). And from profiles: the probe at 58dae0b427 (d06473240f, which is #2635 at 2cab658ef1 with the probe and the two fixes, plus one named sampler per kind of step and the statics refresh as a function of its own), built in js_of_ocaml's dev profile so that its source markers name each function, run under node --cpu-prof at a 200 µs interval, 2 runs per size, 07:48 to 07:53 MST, on the same laptop with nice and a 64 MB stack under a 256 MB system stack. 038/drivers/kinds.py sums each kind's step time, not its refresh, and the part under Outline.of_source (Outline.re:290). Node's profiler keeps about 255 frames of a stack, so a sample whose sampler frame was cut off is not counted: the shares within a kind are read, not totals across kinds. An earlier profile of the same probe, without named samplers (07:23, data/outline_split.json), could not tell an undo from a redo; the first version of this report spread its outline time evenly over both, which was wrong.
• The data: in this page (script#report-data) and as files in 038/data/: the space readings, the outline split per run with each run's raw output (runs/). The profiles themselves (about 30 MB each) are not kept.
• The numbers, for programs too: every table in this report, and what its numbers measure, is also in this page as JSON, in its <script type="application/json" id="report-data"> element, so a reader or an agent that fetches the page alone has the dataset. The same, with any raw files that survive, is in 038/data/.