Hazel performance analysis · ^report(9) · 2026-10-13

Names and reuse: what fresh ids cost Hazel

How do fresh ids relate to lack of reuse in Hazel? An incremental system recognizes work it can reuse by identity, and identity is only as stable as the ids it hands out. Incremental Computation with Names (Hammer, Dunfield, Headley, Labich, Foster, Hicks and Van Horn, OOPSLA 2015), which Matthew co-wrote, asks this of Adapton: allocate with a fresh name and a re-run never matches the last one; allocate with a name derived from where you are, and it can. This report measures what Hazel can tell us about it today, on the Livelit Playground's slides.

At a glance

Where Hazel's ids come from

An id in Hazel is a 16-byte UUID. Id.mk makes one from a counter in its leading bytes and random bytes after it: a gensym, new at every call, which is what an incremental system cannot match from one run to the next. Id.derive(~salt, x), Id.next(x) and Id.mk_str(s) make version-5 UUIDs from a parent id or a string: names, the same every time they are computed from the same place. IdTagged.fresh_deterministic(prev_id, term) builds a node with Id.next(prev_id).

The program's syntax is named by the editor: each tile keeps its id across edits, so an item that did not change carries the same ids into the next analysis. Statics keeps those ids in the elaboration and mints ids for the nodes it adds. A few sites name them (function sugar, one definition site in Statics, module roots, padding in the pretty printer); most use IdTagged.fresh, which calls Id.mk, often through IdTagged.FreshGrammar. The evaluator gives every node it builds a fresh id.

Added later on 2026-10-13: not quite every one. A step's result keeps the id of the expression it came from (rewrap, about 116 uses in Transition, and fast_copy): an input name passed straight through, with no part saying which instance it is, so one piece of syntax evaluated in many calls gives many values with one id. And a variable's value is named, for reuse, by the binding it came from and the path into it (below). Sampling who mints the rest: variable lookups 38% (each copies the value under a new id), environment frames 20%, ascriptions pushed through values about 30%.

Statics, run again: what gets renamed

Each slide was parsed once, so its syntax has one set of ids, and analyzed twice with Statics.mk_unmemoized, as the editor's per-item statics does for an item it analyzes again. (The memoized Statics.mk hands back the very same elaboration for the very same term, and so renames nothing.) This is the worst case: in the editor, only the edited item is analyzed again, and, in UX mode, the open cells (^report(8)). The two elaborations have the same structure, node for node; walking them side by side:

Every renamed node is one statics minted; no syntax id changes. On Full Body they are, by kind: 42 case expressions and 42 holes, 84 constructor patterns and 84 constructor applications in patterns, 86 variable bindings, 59 ascriptions, 52 variable references, 47 field accesses, 45 applications, and 62 type nodes: about one set for each of the slide's livelit uses, and the types. They come from two places:

• UserLivelit.mk_expand_dot_def builds each livelit use's elaboration: a case on the definition's expand, a Functional arm that applies it to the model and a Macro arm that is an ascribed hole. It is built with IdTagged.FreshGrammar, so every analysis gives it new ids.
• StaticsBase.fresh_ascription inserts an ascription where a value's type differs from the expected one, also with FreshGrammar.

A renamed node changes the Merkle hash (Util.ValueHash, ids included) of every expression that holds it. A slide is a chain of lets, each holding the rest of the program, so one renamed node late in the chain changes the hash of every let above it.

Naming them: the experiment

Both sites can be named by where they are, as Adapton names an allocation:

• the dispatch is renamed after it is built, each node's id derived from its parent's and its place among the parent's children, from a root derived from the use's own id. The code it embeds, the use's function and its model, keeps its ids. Two uses get different names; one use gets the same names at every analysis;
• an inserted ascription takes its id from the expression it ascribes: Id.derive(~salt="ascription", Exp.rep_id(d)).

The renames fall from 667 to 85 on Full Body, and to 85 on every slide that uses the Drawing library: those 85 (62 of them type nodes) are the same on each of those slides, which points at the library's own analysis. Polygons has none left. The changed hashes fall from 692 to 247 (Figures 2 and 3). The experiment is on a local branch and was not committed; it is a measurement, not a proposal.

What the eval worker reuses, and what it costs

The worker evaluates incrementally: it checks each part of the new elaboration against its cache of the last run, by id, and reuses a part found the same with the same inputs. "The same" is the check from ^report(8): one hash lookup, ids included, and if that fails, a walk comparing structure and lexemes, memoized. Here, each slide was evaluated, a slider's model was edited in place with every id kept (as the slider's commit keeps them), the edited program analyzed again, and evaluated against the first run's cache:

The parts reused are the same with fresh ids and with names: the structural fallback finds a renamed part the same, as a hash lookup finds a named one. Names only change the cost of finding it, which the one-walk check of ^report(8) already made small. So in Hazel today, fresh ids do not cause lack of reuse; they cost the check. Added later on 2026-10-13: at the granularity Hazel caches, a top-level binding. Inside a binding's evaluation nothing is cached, so there is no reuse there for fresh ids to lose; what names there could find is the subject of ^report(10) and ^report(11).

What the reuse saves is another question. Timed, five runs each, alternating the incremental run and one from scratch, each slide and configuration in its own process:

The first incremental run in each process is usually its slowest (the JavaScript engine warming up); the medians are what Figure 5 shows. Incremental evaluation is no faster here, with fresh ids or named. A slider's value flows into the drawing, so the parts that depend on it, the costly ones, are evaluated again; what is reused is mostly definitions, which are cheap. The reuse that would pay is inside those parts: the shapes of a picture that the slider did not move. Recognizing that needs the values computed inside an evaluation to carry identities from one run to the next, which is where the evaluator's ids come in. Added later on 2026-10-13: ^report(10) measures what is inside those parts: a slider edit changes 5 to 16% of a picture's shapes, and 75 to 84% of the steps evaluated after it are in calls whose inputs did not change.

This is node, with the whole program analyzed again. In the browser, the worker's request shares unchanged values with the last one and per-item statics keeps unchanged items, so more checks succeed by identity; whether the worker's incremental run beats a fresh one there is the next measurement.

The evaluator: an id for every node it builds

Counting Id.mk calls while the Scenes slide is evaluated up to its woods picture: 461,422 ids, the same number every run, for a picture of 33,847 nodes with 7,650 distinct ids (copies of a value keep its id). Nearly all of them belong to intermediate terms the evaluator builds and throws away; a fresh id is a 16-byte string, made at every step that builds a node: part of what each step of evaluation allocates.

Evaluated twice, the two pictures are equal in structure and differ by hash. Of the second picture's nodes, 26,266 have an id that is also in the first, and every one of those is an id of the program itself, a literal carried into the picture. The rest are new each time. So a cache keyed by a value's hash can never recognize the same value computed again. That is why the views' call memo erases ids from its keys before comparing, and why the worker's results share well only where its reuse handed back the very same object.

Between the page and the worker

Requests and results cross between the page and the worker with their already-sent values replaced by references, by hash, ids included (Util.ShareCodec). A build that counted, for each message, the slots of the values it sent, and the slots it would have sent if every part equal in structure to one already sent had also gone as a reference, moved the figure in the woods eight times:

About 2,900 parts a move went to the page as references. They are the parts the worker reused: the same objects as last time, so the same hashes. What a result sends beyond them is mostly new: the moved figure and the picture's list built around it. A request is twice what it could be, from a small base (about 5,400 slots a move, against 749,480 when the slide loads): the edited item, analyzed again, with what statics adds renamed (above).

The paper's main ideas added later on 2026-10-13

An incremental system saves work by recognizing, in a new run, work it did in the last one. Incremental Computation with Names is about how it recognizes it.

• By structure is too conservative. Classic Adapton matched a thunk or a reference cell by its content. Map a function over a list, insert an element, and every new cell before the insertion points to a new tail, so each looks changed and the whole prefix is computed again: "small changes cascade into larger changes" (its Section 2.2).
• Names, fresh only at the edges. A name is a first-class identifier given to an allocation, a thunk or a reference. Fresh names are made only in the outer layer, where the inputs are built. Inside the computation, every name is derived from the names it is given: fork n makes two names from n, the same two every time, and namespaces (ns, nest) let one computation run twice under different names. The same input names give the same names, in every run.
• A graph of what was demanded. Running records a demanded computation graph: each force, with the result it observed, and each allocation. Changing an input dirties, backwards along those edges, whatever observed it. Asking for the result again re-checks a dirty node's forces in order: where a dependency's result is unchanged, the edge is clean and the work stops there (an early cutoff); where it changed, the node runs again. Running again, it allocates under the same names, so it finds its old nodes, updates them in place, and dirties only what really changed.
• Where to put names is the programmer's choice, with guidance: one per list cell, forked from the input cell's name; folds over trees rather than lists, so a change touches one path; in the paper's interpreter, the program position and the loop count.
• Misused names cost speed, not correctness. A name used for two different things in one run is detected (a node on the stack of forces is dirtied by the match) and reported. The calculus is proved from-scratch consistent: an incremental run gives what a run from scratch gives.
• The results: speedups over running from scratch of up to about 10,900 times, and over classic Adapton of up to about 21,000, on lists, trees and an interpreter.

Caching in Hazel, in the paper's terms added later on 2026-10-13

The input names. The editor makes a tile's id when the tile is made, keeps it while the tile is edited, and drops it when the tile goes: the gensym happens in the outer layer, as in the paper. A slider's model is a literal in the program, so moving a slider changes that literal and keeps its id.

What is cached. One entry per top-level node of the program, keyed by its id: its elaboration, the provenance of its free variables, its probe targets, its value, and what the evaluation recorded (probe samples and tests, replayed when the entry is reused). Nothing is cached inside a function call: entries are recorded and reused only at the top of the program.

Names Hazel derives today. Statics derives a few (function sugar, one definition site, module roots, livelits' context entries) and mints the rest. The evaluator passes input names through: a step's result keeps its redex's id. And the incremental evaluator names each variable's value by its provenance: the id of the binding that produced it and the path into that value (a tuple's field, a list's cell, a constructor's argument, an ascription), with a flag, clean or dirty. That pair is a derived name for a value, though it says where the value came from, not what it is.

How invalidation works. The evaluator runs the program from the top. At each top-level node with an entry, it reuses the entry if the node's elaboration is the same (by hash, or by structure: ^report(8)), its free variables' provenances are what they were (the same binding, the same path, still clean), and its probe targets are the same. A binding whose right-hand side was reused makes its variables clean; one that was evaluated again makes them dirty, whatever value it produced. So:

Hazel does the paper's outer layer, and does it well: unchanged code keeps its names across edits. It has not tried the inner layer. That explains the timings above: a slider's value flows into the drawing, the binding it reaches is evaluated again, every binding after it is dirty whatever it computes, and nothing inside the calls that draw can be reused. It also explains why the inner layer cannot simply be added: with fresh ids inside, nothing computed again is recognizable by name.

Derived names everywhere: an experiment added later on 2026-10-13

A switch, in a local build, under which statics' and the evaluator's ids are computed instead of minted: at IdTagged.fresh, at Exp.replace_all_ids, at a variable lookup, and at Environment.extend, a node's id is a hash of its content (its constructor, its children's ids, its literals), computed with ValueHash. Names then flow up from the editor's input names. This is the structural way to derive names, close to hash-consing, not the paper's positional fork. Corrected later on 2026-10-13: the paper's fork is not positional: it derives names from a name already given, an input's, or, in its interpreter, a position's. ^report(11) sets these choices out side by side, with Fumola's merge sort as a worked example. Counting the ids still minted (Id.mk calls), the same three slider edits as above:

• The ids a slider edit mints are the evaluator's, tens to hundreds of thousands; statics, analyzing the whole program again, mints thousands. With derived names, 92 to 97% of the evaluator's are gone; the rest are values the hash gives up on (too deep) and sites the switch does not reach.
• Values keep their names. The woods picture, evaluated twice, shares 33,846 of its 33,847 nodes' ids with the first run, against 26,266 as Hazel is. One node is still minted, so the two are not yet equal by hash; nearly are.
• Statics' renames do not go: 652 on Full Body, against 667. The nodes statics adds are built by FreshGrammar, whose constructors pick a node's annotation before its term exists, so a name from content cannot reach them; the two sites named by position in the earlier experiment can. In statics, a name is most naturally derived from where a node is made: the paper's way. Clarified later on 2026-10-13: one of the paper's ways, naming by position; ^report(11) compares it with naming by the data.
• It costs time, and as first measured, far too much: one evaluation of the woods took 44.2 s against 1.9 s, and Full Body from scratch 7,414 ms against 511. That was where the hashes were kept, a side table that grew through a long session of other measurements (below), not the names. Kept on the values, one evaluation of the woods takes 1.7 s against 1.5 s with fresh ids (Figure 10). A name from content still costs a hash of the content, once for each value; the paper's names are derived from a parent's name, at constant cost for each allocation. In the evaluator, that is a name from the step's own input name and the instance it runs in. Corrected later still on 2026-10-13: this point first said derived names were far too slow, and that a hash that gives up is not remembered and is tried again. It is remembered: ValueHash marks the value as having none.

Merkle names, kept on the values added later still on 2026-10-13

Was the slowdown something non-linear, and would merklizing help? Counting, for the woods' evaluation with derived names on, three times in one process:

• The hashing is linear. Each object is hashed once, then remembered, and every evaluation hashes the same: 1,033,746 objects, with 932,980 hashes found already made. Nothing is walked twice.
• But the time grew with the session: 2.3, 5.5, 6.3 s for the same work, while the heap grew from 685 MB to 1.2 GB; after analyzing two slides first, the third evaluation took 17.2 s. The garbage collector's own pauses stayed about the same (650 to 970 ms). What grew was the side table: ValueHash keeps every hash in a JavaScript WeakMap, about a million new entries an evaluation, and every lookup and insert paid for its size.
• Merklized, the hash lives in the value. Each value carries its own hash, in a hidden property of its JavaScript object, computed when it is built from its parts' hashes, which are already there: a few operations per field, no table, and the hash goes with the value when it is collected. The same objects are hashed, the same number of times, and the time holds still.

Timed in the protocol of the update at the top, each configuration and workload in its own process, medians of five (fastest to slowest in brackets):

That cost is still hashing a value's content, done once per value. The paper's names cost less: derived from a parent's name, not from the content. In statics, where FreshGrammar chooses an annotation before the term exists, that is the only way to name what it adds (the earlier experiment). In the evaluator, content names are what make two runs' values comparable by name, for an early cutoff; kept on the values, they are now affordable. The experiment is on a local branch and was not committed.

Following the paper: what it would take added later on 2026-10-13

1. Cached units below the top level, with names. Each call (and each let's right-hand side) a unit, named from its call site's id, the name of the unit it runs in, and its argument's name. Hazel's probes already key a sample by (syntax id, call-stack instance), which is this name made by position; the paper's lesson is to derive it from the argument's name instead, so that an inserted element does not shift every later name.
2. Record what each unit reads. In the evaluator, a variable lookup and a function application are the reads. Record each with the name of the result it saw; the provenance map already records where a variable came from, not what it held.
3. An early cutoff. A dirty dependency whose new result has its old name stops the invalidation there. This needs equal values to have equal names: the experiment above, at the paper's cost, not content's.
4. Inputs as named references. A slider's model is a literal with a tile id, so moving it is setting that reference: dirty what read it, ask for the result again, run again only what is dirty.
5. What Hazel can build on: the views' call memo is already a cache per call, by structure (classic Adapton's kind); entries already replay their probe samples and tests, which units inside calls would also have to do; probes already name call instances.
6. What is hard: replaying observations (probes, the stepper) for units deep in recursion; the memory of an edge for every read; and boundaries for units in an evaluator that steps a term on a trampoline (the call memo's boundary, at an application, is the place to start).

What next

1. Name what statics adds. The two sites measured here, the livelit use's dispatch and the inserted ascriptions, then the 85 left from the library. It removes most renames of an item analyzed again, so its unchanged parts pass the reuse check by hash; whether it closes the gap measured in requests is to be measured. A small change, with a test that two analyses give the same ids and two uses different ones.
2. Mint fewer ids in the evaluator. 461,422 for one picture, most for terms thrown away: minting an id only when a node is kept, or naming it by its provenance, is part of the per-step allocation the evaluator still has.
3. Names inside evaluation, for the reuse that would pay. Reusing the shapes a slider did not move, inside a part that is evaluated again, needs values that keep their identity from run to run: names for what evaluation allocates, in the sense of the 2015 paper. That is a design question, for a note with Cyrus before any code. Added later on 2026-10-13: the sections on Hazel's caching and on following the paper lay out that question, and ^report(10) takes its first step: calls named by position, and what a memo keyed by those names could skip.
4. Measure the worker's incremental run in the browser, against a fresh one, with per-item statics and shared requests as they are there.

How this was put together

• Build: #2635 (livelits × modular editors) at c4e64060f1, with measuring code on a local branch, not pushed: counters in the reuse check and in Id.mk, the naming experiment behind a switch, and the message counts in ShareCodec.
• Statics and reuse: node, the test build, the slides of the Livelit Playground. Each slide parsed once (FastParse, MakeTerm), analyzed with Statics.mk_unmemoized; the edit replaces one integer literal, a slider's model whose value occurs once in the slide, keeping its id. Renamed means the same position in both elaborations with different ids; a hash changed means Util.ValueHash.same was false for an expression whose structure was equal.
• Times: node's CPU time (Sys.time) after a full collection. Each configuration (fresh ids, the two statics sites named, derived names kept on the values) and each workload (a slide's edit, or the woods) runs in its own process, so that none inherits another's heap or side tables: five timed runs, a slide's alternating the incremental and the fresh evaluation, the median shown with the fastest and slowest. Earlier versions of this report mixed runs from long sessions; the growth in Figure 11 is why that matters.
• Evaluation: Evaluator.evaluate_open, as the page evaluates a view, of the Scenes slide cut at its picture and ending with the picture.
• Page and worker: headless Firefox over WebDriver, the Scenes slide (woods), eight moves of the "across" slider by input events, six seconds apart, the console copied to a file. A slot is a field of a value as js_of_ocaml lays it out (an array); a part counts as equal in structure by a hash that skips 16-character strings, taken for ids.
• 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 009/data/.