Repository navigation
Commit 78d0d4c
authored
perf(html): stream the SourceProcessor walk and recycle completed subtrees (#21595)
* perf(html): stream the SourceProcessor walk and recycle completed subtrees
Visit and release each completed subtree during tree construction instead of
materializing the whole document first, so peak node storage tracks the open
subtree rather than the document. Flushing is gated on an empty active
formatting elements list, which also covers table markers, so neither the
adoption agency nor foster parenting can reach an already-flushed node;
unsafe stretches buffer and the next catch-up sees the final tree.
Skip the input-length column pre-sizing when streaming — it allocated orders
of magnitude more than a streamed parse ever uses.
Only walk-only passes stream; printing holds every node's text until its
parent prints, so `minimize` still builds the tree and walks it. `parseHtml`
itself is unchanged.
On the 2.33 MiB benchmark document with `skip.text`: peak live AST
10.19 -> 1.26 MiB, parse+walk 125.1 -> 104.6 ms.
INCOMPLETE — do not merge. A pre-order `enter` cannot observe post-order
facts, so an element still on the open stack reports a provisional `end`,
`firstChild` and `nextSibling`. HtmlGenerator and HtmlParser read `end` on
Element enter for the head/body injection anchors and must move to `exit`,
and HtmlSyntax.unittest.js currently has 1 failing case (`firstChild`).
* perf(html): cut the per-token cost of the streamed walk
Bail out of the sync before the safety check on the common token shape (open
stack untouched, nothing completed under the current element), and replace the
O(depth) reconcile scan with a suffix scan, falling back to the full scan only
when a mid-stack open.splice marks the stack dirty.
Corrects the measurement in the previous commit. That 125.1 -> 104.6 ms
compared two separate process runs and does not survive a controlled A/B; in
child-process runs (median of 7) the streamed walk is still slower than the
buffered one, by ~8-25% depending on document shape, after these two fixes cut
it from ~25-35%. Memory is a large win: peak column bytes drop 54-85%.
Still INCOMPLETE - the provisional-end breakage is unfixed.
* fix(html): read post-order node facts on exit in the streamed walk
An element is entered while it is still open, so its end offset and child
links are not final there. Move HtmlGenerator's head/body injection anchors
and its script/link/style/meta collection to exit, where end is final;
script/link/style/meta never nest in each other, so source order is kept.
Cover the streamed contract in the path-accessor test: a completed child
subtree is visited and unlinked while its parent is still open, so child
links read empty from either half of an element's visit - structure is read
from parseHtml's materialized tree instead.
HtmlParser's headLastEnd still reads end on enter. Moving it to exit
regressed 25 CSS-link injection cases, so it needs its own investigation.
* perf(html): batch streamed flushes behind a clamped allocator rewind
A flush only earns its walk setup once enough has piled up under the current
element, so the per-token cost drops from a flush attempt to a subtraction.
Batching alone corrupted the tree: deferring flushes let the allocator rewind
below an element that was still open, so the next mkEl aliased a live node and
produced self-referential links (parent === firstChild === itself), which spun
the walk forever. Route every rewind through _streamRewind, which never
reclaims an id at or below the deepest open element, and only relocate a
held-back trailing text node when it is the sole survivor above its parent so
the id space keeps no gaps.
Found with a temporary link validator (cycle / bad-parent / open-above-count)
run over the html5lib tokenizer corpus plus 6000 seeded fuzz documents:
25612 parses, 0 violations. The differential against the buffered walk is
unchanged at 590 mismatches, now all the inherent end-at-enter class.
* perf(html): enter lazily and flush whole sibling runs in one walk
Key the per-token gate on the deepest *entered* element rather than the
deepest open one. The open stack changes on every start and end tag, so the
old gate never engaged on shallow markup; keyed this way, an element that
opens and closes inside the batch window is never entered at all and is later
walked as one completed subtree. That is both cheaper and gives its visitors a
final end offset - the differential against the buffered walk drops from 590
mismatches to 14.
Flush a run of children with a single walk instead of a call per child, pick
the run's stop node in O(1) from lastChild, and inline the gate into dispatch
so an idle token costs three loads and a compare.
Batch 4096 balances the two: on the nested benchmark document 6-15% faster
than the buffered walk with ~85% less peak column memory; deep nesting is
neutral. Pathologically flat markup (60k siblings under body) is still 5-13%
slower - what is left there is the per-token gate itself, which stays even
when the batch is raised until the memory win is gone.
* perf(html): pre-size streamed columns up to one batch
A streamed parse recycles each flushed subtree, so it was left to grow from
the default capacity by doubling. A document that keeps everything open (deep
nesting) still reaches the document's size, and doubling into it overshoots
where one exact allocation would not - 5000 nested divs peaked at 0.74 MiB of
columns against the buffered walk's 0.43 MiB.
Apply the same input-length estimate, capped at what one batch can hold, so
deep nesting matches the buffered peak exactly and wide documents keep the
small streamed footprint.
* refactor(html): drop the duplicate subtree walker and the held-node relocate
_walkSubtree was _walkRun restricted to a single subtree - the printing path
now calls _walkRun directly with the node's own parent and next sibling as the
run bounds, so one walker covers both.
The relocate existed to close the id-space gap a held-back trailing text node
left behind. Since every rewind is clamped by _streamRewind that gap can no
longer be reused by a live node, and dropping it changes nothing measurable:
same 14 differential mismatches, same 2.35 MiB peak, same timings.
* perf(html): drive the streamed walk from the open-stack pops
Route every open-stack pop through popOpen, which marks the walk dirty, and
have dispatch do one boolean test per token instead of re-deriving the whole
gate. Only a stack change can complete a subtree, so the four-term gate was
being recomputed on every token to answer a question that popOpen already
knows - the CSS grammar gets the same effect from its onRule sink.
The mark cannot do the work itself: an element's end offset is assigned after
it is popped, so syncing inside popOpen visits it with a provisional end (it
regressed the differential to a new mismatch class). The flag defers to the
end of the token, where the end is final.
This closes the flat-markup regression - 60k siblings under body go from
~13-20% slower than the buffered walk to ~6% faster, with peak columns still
roughly halved.
* test(html): cover final end offsets in the streamed walk
HtmlParser folds a head element's end into its injection anchor at enter and
consumes that anchor in the same visit, so a provisional end there would
misplace injected tags. The streamed walk only starts once the parse reaches
in-body, which is what keeps every head element a completed subtree with a
final end - assert it directly so a change to that guard cannot silently
break head injection.
Restore the path-accessor test to its original enter-only form: entering
lazily and driving the walk from the pops means an element is walked as a
completed subtree, so its child links are live again at enter.
* refactor(html): state the streamed walk's model and drop redundant flags
Collapse _streaming / _streamRequested into one flag whose lifetime grammar
owns through try/finally, so a thrown parse can no longer leak streaming into
a later direct parseHtml call and the consume-once dance disappears.
_openSpliced already implies a stack change, so the five sites that set both
now set one and dispatch ORs them.
Split _streamSync into named steps (prefix, close, open, flush) behind a
comment that states the model up front: the walk follows the open element
stack, an element is entered only when something beneath it must be flushed,
and nothing is visited unless _canFlush() holds. Rename _streamSafe to
_canFlush and _streamDirty to _openStackChanged so the vocabulary matches.
No behaviour change: differential unchanged at 14, 452 unit tests pass,
timings within noise.
* fix(html): pair enter and exit under skipChildren in the streamed walk
A descendant of a skipChildren() element is tracked on _entered without being
entered, but the close path called _exitNode on it anyway, so exit fired with
no matching enter once nesting was deep enough to stream mid-parse. The
buffered walk fires exit for the skipped element itself and nothing below it;
match that in both the sync and the EOF paths. Reported by Cursor Bugbot.
Reattach the _streamFlush and _streamRewind JSDoc blocks, which an earlier
edit left stacked above _walkRun - tsc reported five implicit-any parameters
and failed lint.
Add streamed-walk tests sized past the flush batch so the enter, flush,
detach and recycle paths are exercised by the unit suite rather than only by
integration: element visits stay balanced across batches, skipChildren pairs
correctly (this case fails with 3635 unmatched exits without the fix above),
adjacent text stays merged, and forms and tables stream.
* fix(html): stop streaming when a splice removes an entered element
A mid-stack open.splice takes an element off the stack without ending its
subtree - </form> with a div still open inside it leaves the div live, nested
in the form. Reconciling the entered stack against the open stack there treats
the div as finished: it exits and detaches a live element, then enters it
again, so visitors see a false close/reopen and later inserts hang off a
detached subtree. Reported by Cursor Bugbot.
Those splices are rare, so stop streaming for the rest of the parse instead of
teaching the reconcile to model an insertion point that outlives its stack
entry: what is already visited stays visited, and the remainder is walked at
EOF. The same handling covers the adoption agency's splices, which drops the
differential against the buffered walk from 14 mismatches to 0 - the streamed
walk now matches it exactly across 25612 parses.
The regression test asserts visit counts, not enter/exit pairing: the faulty
sequence (+div -div -form +div) is balanced, so pairing alone cannot see it.
* fix(html): only halt streaming for entered mid-stack removals
The halt was set at every open.splice, which was far broader than the problem
it guards. Two common shapes lost subtree recycling for the whole parse:
</form> (any form, even when it is the stack top after implied end tags) and
the afterHead reopen for a late link/meta/script/style. Both reported by
Cursor Bugbot; the form case also showed up in a form-vs-form-free benchmark,
where peak columns went 0.76 -> 4.58 MiB, cancelling the entire win.
Route every stack removal through removeOpenAt, which halts only when the
removed element was actually entered and still has open descendants above it.
Removing the stack top is just a pop, and an element the walk never entered
(anything opened while the active formatting elements list was non-empty, and
everything in the head) costs it nothing.
Forms and late head tags now stream again - both back to 0.76 MiB - and the
re-visit regression test still passes, so the false close/reopen stays fixed.
The differential goes back from 0 to 14 mismatches: the broad halt had masked
them by not streaming at all. They are the inherent enter-time end offset on
misnested li, and event counts match everywhere (0 cases differ), so no
element is visited a different number of times.
* perf(html): only stream the walk once a document is big enough
Streaming every walk cost more than it saved on ordinary pages: a 72 KiB
page is ~4.5k nodes, so the per-token sync and the flushes ran with nothing
to reclaim. Measured against main on a realistic page shape, that was +6.6%
at 142 KiB and +7.1% at 568 KiB, while the memory win only appeared past
~1 MiB per page.
Start the walk unstreamed and switch it on once the document passes
`_STREAM_MIN_NODES`; the first sync enters the open stack and flushes what
already finished. Below the threshold a page is walked once at EOF, which
is what it wanted anyway.
Also stop capping the attribute estimate for a streamed parse. Attribute
ids are never recycled (`_attrCount` only resets between parses), so the
cap just forced the columns through the doubling cascade. The node cap
stays under `_COLUMN_SHRINK_CAPACITY` so a streamed parse's columns are
still reusable by the next parse.
Peak parser columns over six 2.4 MiB pages: 19.2 MiB -> 5.8 MiB. Ordinary
pages are byte-identical to main in both time and memory.
* fix(html): release strings and walk state a streamed parse left behind
Two retention regressions from hoisting the walk to module scope.
`_releaseAstColumns` cleared `_nodeStrings` only up to `_nodeCount`, but
streaming rewinds that counter as it recycles ids, so every string written
above the final count stayed reachable. The streamed capacity is kept under
`_COLUMN_SHRINK_CAPACITY` so the drop-the-array path never ran either.
Measured on a 60k-paragraph document: 49,148 strings / 270,314 characters
pinned after the parse returned, against zero on main. Track the id
high-water mark and clear up to that instead.
`grammar` also left the caller's compiled visitor map and print context in
the module-scope `_visitors` / `_writer` after returning, keeping those
closures alive until the next parse; they used to fall away with the call.
Clear both in the `finally`.
* fix(html): honour skipChildren() on the document root
The walk-only path called `_enterNode(doc)` for its side effect and threw
the return value away, then finished with `_streamFinish`, which flushes
the root's children with visiting forced on. A `skipChildren()` in the
document's `enter` was therefore ignored and the whole tree was visited —
on every document, not just streamed ones. Against main, a four-element
page went from 2 visits to 12, and a 120k-node one from 2 to 160,008.
Stop the walk when the root's `enter` declines its children, leaving only
the document's own `exit` to fire, which is what the pre-stream walk did.
* fix(html): halt streaming on any mid-stack open-stack removal
`removeOpenAt` only halted when the removed element was already entered.
An element the walk had not entered yet is just as unsafe: it leaves the
stack while descendants stay open, and the next sync enters those
descendants against an open stack that no longer describes their parent.
A document that crosses the streaming threshold before reaching
`<form><div></form><p>y</p></div>` lost the div and its paragraph
entirely — main visits eight nodes there, the streamed walk visited four.
Key the halt on the mid-stack test alone. Removing the top of the stack,
which is the common `</form>` after implied end tags, still streams: 40k
forms retain 2.80 MiB against main's 9.50 MiB.
* perf(html): print the document in pieces instead of composing it whole
The printer built each node's text from its children's, so the print store
held every node's string until the root was taken — several times the output
for a document of any size, and the reason this branch's walk streaming is
limited to walk-only passes.
A node whose text is exactly `open + children + close` now emits its opener
as it opens and its closer as it exits, and each child goes straight out as
it finishes; the store only ever holds the subtrees that are not of that
shape (a `<pre>` leading newline to round-trip, a `<template>`'s content
fragment, a `/>` whose end tag depends on what printed inside it). An
omitted `<html>` / `<body>` waits in the writer's pending stack, since it
materializes only when the first thing inside it is whitespace.
The walk is unchanged apart from carrying the open path's depth, which is
what lets a node reach the frame its opener was emitted from.
Output is unchanged: byte-identical over the 225 fixture documents and
50,000 random ones, plus the same source map.
Retained heap at the walk's end, and CPU per print (20k-node documents):
table 12.51 -> 1.47 MiB 105 -> 77 ms
flat 5.33 -> 0.03 MiB 33 -> 27 ms
lists 5.23 -> 0.69 MiB 62 -> 51 ms
deep 1.54 -> 0.62 MiB 5.5 -> 4.7 ms
* test(html): benchmark the printer, not just the parser
`html-parser-document-unit` stops at the parse, so nothing measured
serialization — the half this branch changes. This covers both paths a node
can take (emitted in pieces as the walk reaches them, or composed from its
children and read back) and the tree shapes they cost differently on:
fan-out and depth are separate axes for a walk that carries one frame per
open element.
Against this branch's merge base every case separates well clear of its
spread, so a regression in either path shows up rather than hiding in the
document total:
document 278.7 -> 68.8 ms
fragment (tr) 50.6 -> 27.6 ms
wide table 79.7 -> 35.9 ms
flat siblings 21.9 -> 13.7 ms
nested lists 30.3 -> 24.1 ms
deep nesting 34.1 -> 25.1 ms
composed subtrees 21.8 -> 18.2 ms
implied start tags 13.2 -> 10.9 ms
* test(html): benchmark each printer fixture unminimized too
A build that is not minimizing still parses and walks, and that pass is the
floor the printer sits on. Running every fixture both ways makes the pair the
measurement: the difference is what printing costs on that shape, which
neither number shows alone.
fixture walk minify
document 25.6 -> 61.2 ms
fragment (tr) 13.4 -> 27.9 ms
wide table 15.4 -> 32.8 ms
flat siblings 6.7 -> 13.6 ms
nested lists 10.8 -> 23.5 ms
deep nesting 12.7 -> 26.9 ms
composed subtrees 7.2 -> 15.8 ms
implied start tags 3.9 -> 9.9 ms
The fixtures move to a table so the two modes cannot drift apart; the
`minify (...)` names are unchanged, so their history carries over.
* feat(html): make the printer's mode reachable and support beautifying
`PrintOptions.mode` has always been typed `"minify" | "beautify"` and both
printers branch on it, but `process()` hardcoded `"minify"`, so half of it
was unreachable. `process(src, { mode })` now selects it; `minimize: true`
keeps working as the shorthand for `mode: "minify"` it reads as.
Beautifying re-serializes rather than rewrites: the source's own attribute
quoting, its comments and its end tags all come back, and nothing is dropped
for re-parsing the same. It is deliberately still ugly — nothing is
re-indented — but it must not be lossy, and on the CSS side two things were:
kept license comments were only collected when minifying, and a custom
property's value claimed them from the writer only on the minifying path, so
each was emitted twice. Both are fixed here.
Minify output is unchanged, byte-for-byte, over the 843-file css/html
fixture corpus and 24,000 random inputs. On the same inputs
`minify(beautify(x)) === minify(x)` holds everywhere minify is itself
idempotent.
Each printer benchmark fixture now runs in all three modes, so
`minify - beautify` shows what the rewrites cost on top of serializing:
fixture walk beautify minify
document 26.4 -> 48.2 -> 57.8 ms
fragment (tr) 12.3 -> 22.1 -> 25.1 ms
wide table 14.1 -> 25.4 -> 34.3 ms
flat siblings 6.4 -> 12.9 -> 14.8 ms
nested lists 10.8 -> 17.5 -> 23.9 ms
deep nesting 12.3 -> 17.5 -> 23.9 ms
composed subtrees 7.1 -> 13.9 -> 16.3 ms
implied start tags 3.9 -> 7.5 -> 9.6 ms
* fix(html): refuse a nested parse, and pin the streamed walk's offsets
Three review findings on the walk streaming:
- The JSDoc describing `popOpen` sat above `removeOpenAt`, so one helper was
documented by a block declaring a return value it does not have and the
other had none. Moved onto the function it describes.
- Hoisting the walk's state (`_visitors`, `_writer`, the open path, the AST
columns) to module scope for monomorphic call sites made the grammar
non-reentrant: a visitor that started another HTML parse would take this
one's state over and release its columns on the way out, silently. It used
to work, because the state was per-call. Refuse it with a clear error
instead. Nesting the other language is untouched — a `<style>`'s CSS has
its own module state — and an `<iframe srcdoc>` is a separate module
webpack parses on its own, which is why every `configCases/html` case
still passes.
- The offsets test was a few dozen nodes against a 49152-node threshold, so
it never reached the streamed walk it described, and its comment credited
the wrong mechanism: head elements do not keep final offsets because
streaming starts in body, but because a flush only ever visits children
that are already complete, and `HtmlParser` reads `tagEnd()` — assigned at
insertion — for the still-open `<html>` / `<head>`. Replaced with the
contrast that does pin the streamed path: the same markup below and above
the threshold, asserting an entered element reports a provisional `end` at
`enter` and a final one at `exit`. Verified it bites — pushing the
threshold out of reach fails it, where the old test passed.
Output is unchanged: the fuzz corpus hashes identically with and without
these commits.1 parent 57f8dcf commit 78d0d4c
6 files changed
Lines changed: 1403 additions & 186 deletions
File tree
- lib
- html
- util
- test
- benchmarkCases/html-printer-document-unit
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
704 | 704 | | |
705 | 705 | | |
706 | 706 | | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
707 | 720 | | |
708 | 721 | | |
709 | 722 | | |
710 | | - | |
711 | | - | |
| 723 | + | |
712 | 724 | | |
713 | 725 | | |
714 | 726 | | |
| |||
749 | 761 | | |
750 | 762 | | |
751 | 763 | | |
752 | | - | |
753 | | - | |
754 | | - | |
755 | | - | |
756 | | - | |
757 | | - | |
758 | | - | |
759 | | - | |
760 | 764 | | |
761 | 765 | | |
762 | 766 | | |
| |||
0 commit comments