Performance improvements

[brainkim]

Make TermDOM blazing fast.

(Below is essentially a devlog from Claude I’m not really writing any of it)

[brainkim]

Notes from rendering COMPATIBILITY.md (a paragraph with 301 inline <code> spans), which found three O(n²) walks in inline layout. All three are fixed, but they share a root cause worth recording.

Fixed:

• Finding a node's run head walked backward to the start of the run, for every node in it. Now memoized, and the walk adopts the first already-resolved head it meets.
• Adding an element computed its sibling index (a backward walk) before the check that run members never insert their own layout node. Moved after the check.
• Painting located a text node's line fragments by scanning every segment of the run's break result. Each break result now carries a text → fragments index, built once.

Numbers. The 301-span paragraph: never finished → 255ms → 152ms across the three fixes. Full COMPATIBILITY.md (≈3,000 nodes, 11 tables): ~500ms first build. A warm rebuild-and-repaint of the 301-span paragraph is ~85ms. The remaining cost is linear in document size; profiling a warm pass puts it roughly:

• ~40ms painting — the per-frame element walk, dominated by computed-style reads per painted node
• ~15% of everything in getPropertyValue — each read goes through cssstyle's parse/serialize machinery
• a long tail of jsdom per-node overhead: webidl type checks, getter indirection, SymbolTree traversal for every parent/sibling hop
• ~300ms of process startup is jsdom module loading, before any document exists

Root cause of the quadratics: the layout engine only allows a measure function on a leaf, so a contiguous run of inline content hangs its measurement off its first node — the "run head". Everything expensive here was bookkeeping for that choice. Real engines anchor inline layout at the block container: the parent owns line breaking for all its inline children, and "which run does this node belong to" is just the nearest block ancestor.

More generally, every cache-plus-epoch mechanism in the engine (the run-head memo above included) exists because the engine observes a foreign DOM from the outside: it can't know what changed, only that a mutation batch happened, so it recomputes and diffs. That framing drives the plan.

Plan:

1. Anonymous boxes. The structural fix for inline layout, and what CSS specifies: a block container with a run of inline children gets an anonymous child node carrying the run's measure function. Membership becomes a parent lookup, head promotion disappears, block-in-inline falls out as run/block/run anonymous siblings. Also sets up exposing line fragments through standard Range geometry instead of private break results, letting selection, caret placement, and hit testing share one API.

2. Replace cssstyle/CSSOM. The cascade and selector matching are already ours; property storage is cssstyle's, which re-parses and re-serializes strings on every read and write. Computed styles become interned structs resolved once per element per generation, with getComputedStyle as a view — string conversion only at the API boundary. Cleanly separable from jsdom: the only jsdom CSS surface the engine needs is the style attribute, and the cascade can read the attribute text with our own parser while authors keep writing through element.style. Deletes the accumulated cssstyle workarounds on net (the border: none erasure shim, the !important priority-key workaround, manual shorthand expansion, prototype patching).

3. Replace jsdom — purpose-built, not general-purpose. The engine only uses DOM read APIs plus its own cascade, so the target surface is what the compatibility matrix already enumerates: node tree, traversal, events, observers, selectors, custom elements, shadow/slot composition. The probe suite is the acceptance test; jsdom stays in the test rig as the reference implementation. The HTML parser stays external (parse5 — spec conformance there has no performance payoff).

   What owning the DOM buys beyond dropping jsdom's per-node overhead and ~300ms startup:

   • Invalidation moves to the mutation site, where perfect information lives: setAttribute consults an attribute → selector index and dirties exactly the elements whose match set could change; a style write dirties layout or paint but not both; a child insertion dirties one run in one container. The observe-recompute-diff machinery — and its caches and epochs — stops existing as a category.
   • Every element is an upgrading custom element. The spec's reaction machinery is already a fine-grained observation system: attributeChangedCallback is per-attribute observation, connected/disconnectedCallback are tree membership, upgrade is lazy init. The form widgets are already custom-element-shaped with internal shadow trees; this promotes that to the element model everywhere — one registry, one lifecycle, and the engine subscribes to reactions instead of tailing a mutation queue.
   • The injectable-document seam (Browser playground: injectable DOM + xterm.js as ProcessLike #15) is step one, and the same seam the browser playground needs.

Each step is independently shippable, in that order: anonymous boxes unblock the inline-layout half, the CSS store removes the biggest flat-profile cost without touching jsdom, and the DOM replacement then has a smaller, cleaner engine to land under.

(An earlier version of this plan had a "cache computed-style reads per pass" stopgap step; dropped — interned computed structs strictly dominate it, and building throwaway caches first is waste. Incremental painting survives as independent future work.)

[brainkim]

Progress on the plan above, landed on main:

Step 1, first half. Run membership is a parent-side lookup: a block container enumerates its flow children once into an ordered box list (block boxes plus one per anonymous inline run), and every run-head question reads that enumeration. The backward sibling walk, its per-node memo, and the epoch short-circuit are deleted (−90 lines net in layout.ts). Still to do: the anonymous box as a stable object owning the flex node and break result — today they still key on the head DOM node, so head promotion and the block-in-inline flex handoff survive. That half is a rewrite of the build model (per-container reconciliation instead of per-node adds) and lands separately.

Step 2. Computed styles are owned structs; cssstyle is no longer imported by the engine. One DeclarationBlock shape across cascade levels, one shorthand-expansion table, computed values interned per property, pseudo-element styles on the same store. Deleted: the priority-key workaround, the manual shorthand fallbacks (which also cascaded with wrong specificity — fixed by expansion), and most of the none-erasure shim. A 25-line write-time shim remains because upstream cssstyle erases inline border: none from both the CSSOM and the attribute text — unfixable from outside; the real fix is an upstream PR.

Numbers. The 301-inline-code paragraph, warm: ~150ms → 110ms with both landed. The remaining style cost is rule matching itself — #getMatchingRules runs element.matches() over every parsed rule per element; bucketing rules by rightmost simple selector is the next lever.

[brainkim]

Steps 1 and 2 of the plan are now fully landed on main.

Anonymous boxes, complete. An InlineBox object owned by its container holds the run's flex node and break result; containers reconcile their box lists by ordinal, so a run survives its first node being removed, edited, or blockified — it re-measures instead of being re-identified. Deleted outright: head promotion, #addSplitFragments and the block-in-inline hand-off, and the per-run break-result orphaning. breakResultMap narrows to one well-defined population (blockified element children of flex containers, which own their boxes per css-display-3 §2.7). Two rendering bugs died in passing: a run's first node flipping to display:block or display:none used to lose the whole paragraph.

Inline CSSOM, complete. element.style is the engine's own object — declarations stored as authored, !important preserved, writes serialized through setAttribute so invalidation rides ordinary mutation records, and the cascade consumes the parsed block directly. cssstyle is out of package.json entirely; the none-erasure shim is deleted rather than shrunk. Inline declarations pass the same validity checks as stylesheet rules, and inset joined the compatibility table (cssstyle had been dropping it as unknown).

Numbers (warm, quiet machine): the 301-inline-code paragraph is 76ms, from 110ms before these landed, ~150ms after the first quadratic fixes, and never-finishes before those.

What remains rented: rrweb-cssom for stylesheet rule parsing, nwsapi (via element.matches) for the cascade's rule matching, and jsdom itself. The selector engine — with rules bucketed by rightmost simple selector and class/attribute → selector inverted indexes for precise invalidation — moves to the own-DOM project, where it also becomes querySelector so the cascade and query APIs can never disagree.

[brainkim]

Architecture research: what production engines do that we should steal. Two of three reports in (style invalidation pending); condensed here so it survives any session.

Paint (vs Blink RenderingNG / WebKit / WebRender / terminal libs). We already have three of Blink's four tiers (invalidation scoping, incremental old∪new rect damage, full-repaint fallback with WebKit's 75% heuristic). Missing tier: identity-based retained painting — nothing remembers a clean subtree's cells, so the walk is O(on-screen) even for one changed span. Steal list, ordered: (S5) cache-skipper inventory — the never-cacheable list is exactly the painter's non-DOM reaches (checked/selection/caret/markers); (S2) descendant dirty stamps via ancestor-chain epoch marks — removes the >24-damage-set cliff; (S1) retained cell strips cached per stacking context — the boundary is sound because siblings cannot interleave there, and #renderStackingContext + positionedElements is already that boundary; strips in document coordinates make camera scrolls free; (S4) pseudo-class state (:hover/:focus/:checked) folded into the strip cache key (Textual's trick) — ends mouse-move full frames; (S3) translate-only strip revalidation — list insertion stops costing a full frame. Non-transfers: GPU/compositor/layerization; occlusion culling (our background-inheritance paint order is load-bearing). Among terminal libraries only Textual avoids the full walk, and it converged on Blink's shape independently.

Layout (vs LayoutNG / Gecko / Yoga / Taffy). Ranked: (D) prefix-width Float64Array per inline run — cell widths are context-free and additive, so measureText becomes subtraction and line building stops rescanning; the one big win a browser cannot have; (E) Yoga's three non-exact measure-cache acceptances (measures only, never layout); (F) Taffy's shape-keyed deterministic cache slots replacing the eviction-fragile ring; (A) cache the layout OUTPUT not just the size — closes a latent wrong-wrap bug (breakResult is a side effect the cachedLayout hit doesn't restore; sibling-churn eviction can paint min-content lines in a full-width box — second entry to the bug class flex.ts already documents fixing once); (B+C) Gecko's two-tier dirty bits (self vs descendant) then SlideLine — a keystroke in a 5000-row list stops costing 5000 cache probes; (H) per-container enumeration generations instead of the global epoch — prerequisite for (G) persistent inline item lists (Blink CollectInlines split: identity once per mutation, breaking per width) and (I) prefix line reuse. Poor fits, stated: Blink relayout roots (every emulated block is a flex item, disqualified by their own predicate — slide instead); shaping caches (no shaping — D is strictly better); fragment immutability (no threads). A/D/E/F are delegated and running now.

Also in flight: struct-of-arrays typed-array cell buffer (owner's proposal; xterm.js precedent — packed uint32 planes, grapheme intern table, copyWithin scrolls, memcpy strip blits), gated on byte-identical ANSI fixtures.

[brainkim]

Style invalidation research (third and final report; deepest of the three). Condensed:

How the engines split. Blink compiles selectors to per-key invalidation sets (membership tests, cheap, over-invalidates: .a .b span keyed under a dirties every span). Stylo stores the original selector + offset and re-matches old-vs-new against a pre-mutation snapshot (precise across combinators, degrades badly on universal cases; their >150-descendants fallback is commented "completely made-up"). WebKit builds per-key mini rule sets lazily on first mutation of that key and runs the real matcher over a relation-scoped walk (Subject/Parent/Ancestor/Sibling) — viable because their JIT made matching cheap. The published head-to-head (emilio, bug 1368240): narrow class flip 40ms Stylo / 42ms Blink vs 800ms+ coarse; universal rule 925ms Blink vs 2.3s Stylo. The transferable principle: going into the DOM with a few selectors beats a subtree restyle except when everything matches anyway — our current design assumes it always does.

Where we stand (audited): matching is a linear filter (every rule × every element via nwsapi); the reach analysis is two global booleans set by substring tests (one ~ anywhere makes every attribute change invalidate all following siblings; .has-icon trips the :has detector and nukes the document); every resize reparses all sheets and clears the whole cascade; the css-tree selector ASTs are built and then discarded in favor of regexes (the specificity regex miscounts inside :not()/:is()); #invalidateSubtree re-attaches pseudos across all descendants; and over-invalidation converts banded frames to full frames at the 24-element damage cliff.

Steal order: (S6) media-query result caching on resize — cheapest, kills the resize nuke; (S4) skip invalidation when the interned computed struct is pointer-equal — best ratio, protects the damage budget; (S1) keep the css-tree AST on ParsedCSSRule — prerequisite, fixes specificity/:has bugs; (S2) Stylo-style rule buckets by most-selective rightmost key incl. the rare-pseudo-class bucket — biggest steady-state win, helps every resolution; (S3) WebKit-style per-key invalidation rule sets with MatchElement relations, lazily built, old-vs-new flip test from MutationRecord.oldValue (we get Stylo's snapshot for free — records carry oldValue), stage classes → attributes → decline ids (WebKit's own judgment); (S5) AffectedBy bits for :hover/:focus-within + WebKit's InvalidationScope chain trick — ends the every-mouse-event full frame; (S7) structural parent flags with the append special case, generalizing the hand-written list-marker invalidation. Do NOT build: the ancestor Bloom filter (wrong scale; false positives punish the damage budget), snapshots-as-such, style sharing cache, count-based fallbacks.

WebKit's warning to carry: precision removes the safety net — every mutation site must declare what it changed (their bug 315828). Land S3 with the coarse path behind a test-time assertion and burn it down deliberately.

[brainkim]

Landed: the ANSI cell buffer is struct-of-arrays, and an unbounded leak it exposed is fixed.

Typed-array cell buffer (b689989). CellGrid holds five planes indexed row * cols + col: char (code point, or an intern-table id for a multi-code-point grapheme), fg and bg (24-bit RGB, zero meaning the terminal default — the only stored form, so no tag bits were needed), attrs (style bits plus the glyph's width), and the border encoding unchanged. Grids are allocated per size and pointer-swapped, scroll shifts are copyWithin, the diff skips a row when no column differs, and the SGR emitter reads cells by index rather than materializing them. DrawingContext's surface is unchanged; painter.ts and termdom.ts were not touched. Gated on ANSI fixtures recorded from the previous implementation before converting — 19 scenarios pinning the emitted bytes of every cell attribute, extended first for background inheritance, unbounded clip axes and the resize park measurement, with re-recording at HEAD changing zero existing bytes. Full-screen diff −62.4%, scroll −32.1%, typing −8.9%, inline builds −2 to −4%; no regression anywhere.

The leak that work surfaced (f9c6622). Reported as a hang; it is not. A document rebuilt in place degraded linearly and without bound — 36ms → 104ms over 200 rebuilds, still climbing, ~140ms by round 250. Profile: 42% of the time in appendChild + bumpTreeVersion. A change to a tree's shape resynchronized every materialized collection in the realm, filtering each by walking its root back to the mutation point, so an insertion's cost grew with the number of collections the process had ever read — and a discarded tree's collections were never unregistered. Fix: a node holds the collections it is the root of, and a shape change walks its own inclusive ancestors instead (the same shape syncAttributeCollections already used for attributes). Rebuild time is now flat at ~25ms across 300 rounds; adoption also carries a collection's registration with the node rather than stranding it under the document it was first read in. WPT dom byte-identical (94804/1540), suites 955/980, examples 17/17, tmux 6/6, fuzzy-finder case at parity.

Any long-running TUI that re-renders its content — a log viewer, a dashboard, a list that rebuilds — was getting permanently slower. Worth noting how it was found: a benchmark harness wedged, the agent reported it honestly as pre-existing rather than dismissing it as its own harness's fault, and it reproduced on a HEAD from before that work.