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

What an Undo Costs

How do the times of an edit, an undo and a redo grow with the size of the program? Where does that time go? And what would it take for each to cost O(log n) in the program's size, rather than O(n)? Matthew's question (2026-11-02), for the meeting with Cyrus on 2026-11-04. Measured on #2635 (livelits × modular editors), in Node, on a program of n definitions at five sizes.

The question#copy link

An edit in Hazel's editor is meant to cost time in proportion to what it changes. Matthew's question on 2026-11-02 was whether that is true of undo. It seemed to cost O(n) in the size of the program. Could an edit and an undo each cost O(log n)? The question is for the meeting with Cyrus on 2026-11-04. A related question, how much structure sharing is lost as values go to the evaluation worker and back, is not measured here.

^report(14) measured what the undo history keeps, in a browser on the Full Body slide: whole versions of the editor's state, about 92 MB an edit on #2597, until Andrew Blinn's compaction of snapshots (6010128b7d) was ported there. #2635 had it already and keeps about 8 MB an edit; keeping the newest undo and redo entries whole (032fe3aca6) followed. This report measures what an undo costs in time, and how that grows with the program.

How an undo works today#copy link

The undo history (src/web/app/History.re, at bfa36a6ede) is two lists of page models, the undo stack and the redo stack, capped at 250 entries. An edit pushes the model from before it onto the undo stack. Pushing compacts the entry below the new head: it drops the derived caches (syntax, statics, evaluation results) and keeps the zippers, the editor's own representation of the text and the caret. The newest entry stays whole. An undo pops the head and restores it:

• Syntax is rebuilt against the live caches. Page.carry_over hands the restored model the live editor's parse and layout caches, which hit for every piece the step did not change. So 1 or 2 definitions are parsed again, whatever the size of the program.
• A second frame realizes the view. The restore schedules RealizeView, which rebuilds the outline of the program: the tree of its definitions that the sidebar and the agent read.
• Statics wait for the typing debounce, as after a keystroke, and re-analyze incrementally: the definitions are walked in order and their heads compared with the previous version's, and only those that changed are analyzed again.

How it grows#copy link

The probe builds a program of n definitions, let v0 = 0 in let v1 = v0 + 1 in … vn-1. It moves the caret into the middle definition and types four digits there, then undoes four times and redoes four times. Each step goes through the app's own update loop, with each frame told whether it was an edit, as the app's main loop tells it. Then comes the statics refresh that the typing debounce would run. Evaluation is off. Sizes 400 to 6,400, three runs of four steps of each kind for each build.

Milliseconds per step, medians of 12 (3 runs × 4 steps); the after column's range in brackets. "Statics, after" is the median refresh after each of the 36 steps at that size. "Building the program" is the first run's initial build of the editor, for scale.

Two things in the spread are worth knowing. The first edit of each run takes about twice as long as the other three. The last redo takes longer than the other redos: about 40 ms more at 3,200 definitions, and up to 300 more at 6,400. Neither is explained yet; medians of 12 are robust to both. Runs of the same two builds this morning (800 to 3,200 definitions) were 20 to 70% slower at every size, for both builds alike. That is the laptop's spread between sessions, larger than the fixes' effect at the small sizes, so compare within a session: this morning's gap between the builds was 25 to 45% at the larger sizes, much as here.

Where the time goes#copy link

Inside those parts, after the fixes:

Every remaining part is a pass over the whole top level, around work that is already incremental:

• The top-level term (MakeTerm.go_incr). The syntax cache re-parses only the changed definition, but the top level's term is then rebuilt from all of them: a simulation of the top-level frame over every definition (record_top_frame), and every definition's span (ItemSpans).
• Statics' chain (DefStatics.step_chain, calc_chain). Definitions are analyzed one by one, each in the context the ones before it make. Only 2 heads are compared structurally, and every other definition is found physically the same in constant time, but the walk itself visits all n.
• The outline (Outline.build), rebuilt on every undo and redo (below).
• Layout's walk (Measured.of_segment). One or two chunks are measured again, and the walk to place them visits the rest.

Two cheap fixes#copy link

Both were passes over the whole program that nothing needed. Both are on #2635 since 2026-11-02, cherry-picked as 394552d5d0 and bfa36a6ede (first made on a probe branch as 459b029f68 and d06473240f).

The auto-probe's program root (394552d5d0)#copy link

Auto-probes find the program's root expression on every frame (AutoProbePerform.program_root_id). They did it from a skeleton of the whole top level, through a memo keyed on the segment's identity, which every edit replaces, so it missed on every frame after an edit: 13% of the profile before. The parser already keeps that skeleton (MakeTerm.Incr's c_skel, from #2469), so the fix reads it when it belongs to this segment:

let skel =
  switch (syntax.t_cache.c_skel) {
  | Some((Sort.Exp, parsed, skel)) when parsed === seg => skel
  | _ => Segment.skel(seg)
  };
switch (Segment.root_id(skel, seg)) {

This one is #2635's and #2469's only: dev has no c_skel.

No completions after a numeral (bfa36a6ede)#copy link

After each keystroke, the editor fills its completion buffer with the best suggestion for the token left of the caret (TyDi.set_buffer). To find it, it scans the context for names and completes the whole segment to find the delimiters the syntax expects. That is a pass over the program, 10% of the profile before. No suggestion starts with a digit (names, keywords, operators and missing delimiters don't), so after a numeral none is computed now:

let* tok_to_left = token_to_left(z);
let* _ =
  switch (tok_to_left.[0]) {
  | '0' .. '9' => None
  | _ => Some()
  | exception (Invalid_argument(_)) => Some()
  };

A limit to keep in mind: this fix helps exactly the probe's edits, which type digits. Typing a name still computes suggestions over the program. Dev has the same code, so the fix would suit dev as well.

Why an undo costs more than an edit#copy link

An undo or a redo is two frames: the restore, then the RealizeView it schedules. The second builds the program's outline (Program.outline → Outline.of_source). The outline is memoized on the last four programs, keyed by the segment's identity and then by Segment.same_program, and the restored program matches none of them. So the outline is built from scratch, about 26 ms at 3,200 definitions. In this probe an edit never builds it, because nothing draws the sidebar. In the app, the sidebar's view may ask for it after edits too; that is not measured here.

That accounts for most of a redo's extra over an edit (42 ms), but only a third of an undo's (77 ms). An undo parses 2 definitions again where an edit parses 1, but that is constant work. Why an undo costs about one and a half redos is the next thing to profile, with the undo steps alone.

Toward O(log n)#copy link

Every pass left is a walk over the top level's definitions. The incremental work inside each pass is already constant, so making each step O(log n) means making the walks O(log n). That starts with how the top level is represented.

There are two ways to make an undo cheap, and they compose. Undo as a swap of roots keeps each version's derived data in a shared tree, and needs that tree. Undo as an inverse edit replays the edit backwards through the same incremental path a keystroke takes, and needs every action to have an inverse. Either way the walks above have to become O(log n) first, since an edit pays them too. The cheapest walk to isolate and try first is statics' chain: DefStatics already treats the top level as a list of items with summaries.

What this does not measure#copy link

• Evaluation. The probe turns it off. In the app, an undo also re-evaluates the program in the worker, which ships the program to it and the results back.
• Drawing. The probe builds no view and no DOM, so the time to redraw the code after an edit or an undo is not here.
• The browser. These are Node timings of the test build. Hosted builds in a browser differ in speed, not in how the work grows.
• Real programs. A chain of short lets is the plainest shape that grows. Slides like Full Body have fewer, larger definitions, modules and livelits; the same walks apply to them, but with smaller n and larger per-definition costs.

What next#copy link

1. Profile undo steps alone, to explain why an undo costs about one and a half redos.
2. Let a restored program reuse its outline: keep the outline with the snapshot, or find it by the restored program's identity. Then measure an undo again.
3. Time an edit and an undo in the browser on Full Body, with evaluation and drawing, to see what share of a real undo these passes are.
4. Try the top level as a balanced tree of definitions for statics' chain first, and measure it with this probe: does an edit's statics refresh stop growing with n?
5. Then the top-level term and layout over the same tree.
6. Offer the completions fix (no suggestions after a numeral) to dev as a PR of its own: dev has the same code.

How this was put together#copy link

• The builds. Before: #2635 at 2cab658ef1 (dev's merge day of 2026-10-29 merged in) plus the probe, 1d98b3aed7 and 167247e61d. After: the same plus the two fixes, 459b029f68 and d06473240f. On #2635 the fixes are 394552d5d0 and bfa36a6ede, with the same code. The probe commits are on a local branch; the probe's source is in 036/drivers/.
• The probe (Test_UndoScaling.re, one of Hazel's test modules): for each size, build the program, move the caret into the middle definition, then 4 edits (typing 1), 4 undos and 4 redos. Each step runs through History.Update.update and calculate, then the frames it schedules, then a statics refresh (RefreshStatics, which the typing debounce runs in the app). Each frame's calculate is told whether its update was an edit, as Main.re tells it, and dynamics=false. For each step it counts the top-level items parsed in full (MakeTerm.Incr.full_analyzed), the layout chunks measured (Measured.Incr.built) and the definitions' heads compared structurally (DefStatics.head_compares).
• Two checks the test runner installs were turned off for the probe, because each made the numbers mean something else. One compares the incremental statics with a whole-program analysis after every calculation (DefStatics.after_calc). It made the first numbers look quadratic, then cheap past 3,000 entries, where it stops. The other re-molds the whole program after every edit (Zipper.normalize_check). A helper of the undo tests also told every frame it was an edit; the probe tells each frame what the app's main loop would.
• Timing: Node 22.23 on a laptop (Intel Core i7-1370P, Linux), the test build compiled by js_of_ocaml in its release profile, run with nice. Times come from Sys.time, read to the millisecond. There were 3 runs per build at 400, 800, 1,600, 3,200 and 6,400 definitions, with every after run before every before run (not alternated), on 2026-11-02 near 10:30 MST. Node runs with a 64 MB stack under a 256 MB system stack, because at 6,400 definitions the default one overflows: the same probe crashed in four of six runs with an 8 MB stack.
• Profiles: node --cpu-prof at a 200 µs interval, one run of each build at 3,200 definitions (earlier the same day, same builds). Read by 036/drivers/prof.py, which maps the test bundle's functions to their source through js_of_ocaml's source markers and sums inclusive time per function, under the probe's sample. Node's profiler keeps about 255 frames of a stack, so deep recursion can hide callers; the parts in Figure 3 are separate branches below sample, so none is counted twice. Raw profiles are summarized in data/profile_3200.json.
• The data, twice: in this page (script#report-data) and as files in 036/data/, every run's raw output (runs/), the medians and samples (steps.json, by drivers/medians.py) and the profiles' parts.
• 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 036/data/.