1344139 - stylo: Coalesce all sibling reconstructs when processing nsChangeLists

Status: ASSIGNED

(Core :: CSS Parsing and Computation, enhancement, P4)

Description

[Bobby Holley (:bholley)]

With my patches in bug 1338921, we coalesce lazy frame construction for siblings in ProcessRestyledFrames. However, we don't coalesce arbitrary reconstructs, since that would require doing all the teardown and state-saving that ReconstructFramesForContent does in the case where there's a pre-existing frame.

Fixing this might have a modest performance benefit when doing frame construction during restyles, since we can amortize the cost of all the setup we do for insertion.


bz's proposal is as follows:

[22:10:49]  <bz>	So we could do that, I think....
[22:10:56]  <bz>	Capture state for all of them up front
[22:10:59]  <bz>	remove them all
[22:11:29]  <bz>	Keeping an eye out for aDestroyedFramesFor, possibly
[22:11:58]  <bz>	And then do a single range insert

Comment 1

[Boris Zbarsky [:bzbarsky]]

> Fixing this might have a modest performance benefit when doing frame construction during restyles,
> since we can amortize the cost of all the setup we do for insertion.

Actually, it can have a _huge_ performance benefit in some cases.  Specifically, there cases when each of the individual reconstructions forces reframing of something higher up the tree.  In that case, we would be effectively converting an O(N^2) algorithm into an O(N) one.

That said, textnodes might throw a wrench into the mix here anyway, since they wouldn't have reconstruct hints, so if your elements to be reconstructed are separated by textnodes (which they are!) then you can't coalesce.  Though maybe in realistic cases the textframes would all be suppressed, and then you _can_ coalesce with the tetxnodes, I think.

Anyway, I'm pretty sure I can write a synthetic testcase where this is a big win, but I have no idea how much it would matter in the wild.

Comment 2

[Chris Peterson [:cpeterson]]

status-firefox57=wontfix unless someone thinks this bug should block 57

Comment 3

[Mayank Bansal]

Worth re-analyzing for SP3?

Comment 4

[Mayank Bansal]

Attachment: Bug 1344139 - Coalesce sibling reframes in ProcessRestyledFrames. r?emilio

We already coalesce adjacent siblings for lazy frame construction, but
nsChangeHint_ReconstructFrame on elements that already have frames is still
handled one element at a time. Each of those does its own insertion, and
nsBlockFrame::AddFrames searches the line list for every one of them, so
reframing N adjacent children of a block is quadratic in the number of lines
(bug 2023352).

Collect a run of adjacent siblings that all want a plain, synchronous reframe,
remove their frames, and then rebuild them with a single insertion, which is
what bug 1338921 left as a follow-up. Since the run is appended in DOM order,
removal walks the line list front to back on a shrinking list, and the single
insertion either appends or does one line search instead of N.

Only content taking the straightforward path in RecreateFramesForContent can be
batched. Anything that reconstructs an ancestor instead, defers to an async
reframe, or deliberately doesn't re-insert (display: none) is excluded up front
by CanBatchReframe. A run can still discover mid-removal that it has to
reconstruct an ancestor, and in that case we stop: every ancestor that
MaybeRecreateContainerForFrameRemoval reframes is at or above the parent the
siblings share, so it also rebuilds the frames we already removed.

Comment 5

[Mayank Bansal]

Attachment: WIP: Bug 1344139 - Also batch reframes of out-of-flow siblings. r?emilio

Out-of-flow reframes take the same path as in-flow ones: ContentWillBeRemoved
removes the placeholder, which tears down the out-of-flow frame with it, and
the insertion constructs both again. The placeholder is what sits in the
parent's line list, so a run of absolutely positioned or floated siblings
hits the same quadratic line list search when reframed one at a time.

Comment 6

[Mayank Bansal]

Attachment: Bug 1344139 - Let the reframe run scan step over non-element change list entries. r?emilio

Text nodes only get change list entries of their own when their parent is
display: contents (see the assertion in nsStyleChangeList::AppendChange), and
those entries land between the entries of their reconstructed element
siblings, breaking the run. Any hint on a frame that the batched reframe is
about to remove and rebuild is subsumed by the rebuild, so the scan can step
over such entries. They are consumed only when a later sibling actually
extends the run past them; a trailing entry with no member after it keeps its
frame and is processed normally.

Comment 7

[Mayank Bansal]

mach try auto: https://treeherder.mozilla.org/jobs?repo=try&revision=b76e0beebccbb3c02491c9fd6cdded291ee20ea0

Comment 8

[Mayank Bansal]

sp3 perfcompare: https://perf.compare/compare-results?baseRev=74b838b5cde3ad53fc511d7f9b8bba6091ea3249&baseRepo=try&newRev=12d5249db99e33d7da06e4dd9fbcf823ecd7d478&newRepo=try&framework=13
(all regressions)

Comment 9

[Mayank Bansal]

Emilio, woud you mind taking a look at the patches and give feedback on what look wrong or what can be improved? All comments would be helpful.
Alternately, please redirect to someone more appropriate.

Comment 10

[Emilio Cobos Álvarez [:emilio]]

So at a glance:

• I don't understand why we need the special-case here. Seems like RecreateFramesForContent could be implemented in terms of RecreateFramesForContentRange
• I don't think CanBatchReframe is generally sound, it doesn't deal with shadow dom and what not. It should use the same mechanism that we use for inserts (e.g. IssueSingleInsertNofications).
• I don't get why the mathml or out-of-flow special cases either.

Comment 11

[Mayank Bansal]

Thanks. I've folded in the first and third points; on the second I'd like to check what you mean before rewriting.

I don't understand why we need the special-case here. Seems like RecreateFramesForContent could be implemented in terms of RecreateFramesForContentRange

Done. Its tail was already exactly that, so it now ends with

RecreateFramesForContentRange(aContent, aContent->GetNextSibling(), aInsertionKind);

and the cases above it that reframe something other than the content itself (NAC root, MathML, leaf parent, MaybeRecreateContainerForFrameRemoval, display: none, async) stay where they are. display: none and async keep their own ContentWillBeRemoved call since neither re-inserts. RecreateFramesForContentRange also lost its ContentAppended branch, since ContentAppended is ContentRangeInserted(x, nullptr) anyway.

I don't get why the mathml or out-of-flow special cases either.

The out-of-flow one is my fault: the first patch excluded out-of-flows and the second removed the exclusion, so there was never one in the end state. I've squashed the two, and D314252 can be abandoned.

MathML is only there because RecreateFramesForContent hoists to the topmost MathML element for bug 397518, so a run of MathML siblings would each redirect to a shared ancestor rather than reframe themselves. If CanBatchReframe goes away it goes with it.

I don't think CanBatchReframe is generally sound, it doesn't deal with shadow dom and what not. It should use the same mechanism that we use for inserts (e.g. IssueSingleInsertNofications).

Agreed on the general shape: it hand-mirrors RecreateFramesForContent's preconditions and will drift out of sync with them.

On shadow DOM specifically, I think the batch path is already going through that mechanism, and I'd like to confirm I'm not missing a case. RecreateFramesForContentRange ends in ContentRangeInserted, and a multi-node range there goes to GetRangeInsertionPoint, which bails to IssueSingleInsertNofications for any parent with a shadow root (nsCSSFrameConstructor.cpp:6042) and returns an empty insertion point, so the run degrades to single inserts. I've added coverage to the crashtest and mochitest for hosts with named slots, a default slot, nothing slotted, and a run inside a shadow tree.

So before I rewrite : do you want CanBatchReframe deleted outright, with RecreateFramesForContentRange splitting the range itself on the first node needing one of the escape paths, the way GetRangeInsertionPoint splits? That's what I'd write if the up-front predicate is the objection, but it rewrites the first patch so I'd rather check first.

---

sp3 perfcompare: https://perf.compare/compare-results?baseRev=74b838b5cde3ad53fc511d7f9b8bba6091ea3249&baseRepo=try&newRev=cbec5d47f462a39bd48335670ada0bb4835f6ebf&newRepo=try&framework=13
layout preset tests debug: https://treeherder.mozilla.org/jobs?repo=try&revision=10d166bb1944a86c9276949d3abb1bfdd91edfea
Layout preset opt tests: https://treeherder.mozilla.org/jobs?repo=try&revision=3df40958f88d3ead552d0d4f11abade897821104

---

Profile of the testcase from bug 023352
Toggle: https://share.firefox.dev/45AbEIY (1s/1.5s)

Comment 12

[Mayank Bansal]

Emilio, there is a question in comment 11.

Comment 13

[Emilio Cobos Álvarez [:emilio]]

do you want CanBatchReframe deleted outright, with RecreateFramesForContentRange splitting the range itself on the first node needing one of the escape paths, the way GetRangeInsertionPoint splits? That's what I'd write if the up-front predicate is the objection, but it rewrites the first patch so I'd rather check first.

Yeah, that's what I was envisioning fwiw. But I don't know why we need a bunch of those "escape paths".

Comment 14

[Mayank Bansal]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #13)

do you want CanBatchReframe deleted outright, with RecreateFramesForContentRange splitting the range itself on the first node needing one of the escape paths, the way GetRangeInsertionPoint splits? That's what I'd write if the up-front predicate is the objection, but it rewrites the first patch so I'd rather check first.

Yeah, that's what I was envisioning fwiw. But I don't know why we need a bunch of those "escape paths".

Yeah, that's what I was envisioning fwiw. But I don't know why we need a bunch of those "escape paths".

The second sentence is a new question, and it's aimed at pre-existing code, not mine. I traced all seven:

Escape	Load-bearing?
!GetComposedDoc()	Yes — bug 157322, chrome frame tree
NAC root	Emilio's own TODO at nsCSSFrameConstructor.cpp:7940 already asks if it's removable
MathML hoist	Yes — bug 397518, exponential blowup
parent->IsLeaf()	Yes — editor NAC; insert would create no frame
MaybeRecreateContainerForFrameRemoval	Yes — only discoverable during removal
display:none	Efficiency only (earlier a11y notifications), not correctness
Async	Emilio's own TODO asks if lazy FC made it redundant

Two of the ones he's questioning he already flagged himself years ago.

---

Both patches rewritten. Branch bug1344139-coalesce-reframes: 48e8cba + bcfadde.

Patch 1 — CanBatchReframe is gone

RecreateFramesForContent is now literally:

RecreateFramesForContentRange(aContent, aContent->GetNextSibling(), aInsertionKind);

All escapes moved into one MaybeRecreateFramesForSomethingElse that both entry points share, so there's no second copy of the conditions to drift. The range function splits at any node that hits one. RestyleManager lost the predicate and the if/else — it always calls the range function now.

A correctness trap I hit and had to design around: escapes aren't uniform. MaybeRecreateContainerForFrameRemoval, the NAC hoist and the leaf-parent hoist all reframe an ancestor, which subsumes siblings whose frames I'd already removed — inserting the pending run afterward would double-insert. A bool return would have shipped that bug. Hence the three-valued ReframeOutcome (Plain / Handled / ReframedAncestor), where only Handled flushes the pending run and ReframedAncestor abandons it. I also verified GetTopmostMathMLElement is idempotent (nsCSSFrameConstructor.cpp:7854 — it breaks immediately when already topmost), so the MathML redirect can't recurse forever.

One accepted nuance: for Handled outcomes inside a multi-node range, the escape runs before the pending run is re-inserted. No ancestor is destroyed on those paths, so it's safe, but it is an ordering difference from the unbatched path.

Patch 2 — the hint bug is fixed by the restructure

Emilio's two comments turned out to be the same fix. Folding into the sibling walk deletes the separate non-element branch, so non-element entries now pass through the existing nsChangeHint_ReconstructFrame check — which is precisely the guarantee he asked for. IsNonElementSiblingInReframeRun is gone.

It's also strictly better than before: a non-element entry is now consumed directly and its node lands inside the reframed range, instead of only being consumed when a later element happened to extend past it.

I did not remove the two TODO'd escapes — here's why

You asked me to, and I'm flagging this rather than doing it silently, because the evidence went the other way:

NAC escape. ShouldRecreateContainerForNativeAnonymousContentRoot justifies each of its exclusions in-code with "it's all abspos, so relative insertion order doesn't really matter". That's a direct statement that for everything not excluded, insertion order does matter — which confirms the first TODO's stated premise (the insertion-point rework is still needed) rather than the "maybe we can just remove this" concession. Emilio also refined this exact function in Nov 2022 (bug 1802533) and kept the escape.

Async escape. Emilio restructured this exact block in Nov 2025 (2dab799, bug 1948933 — itself a quadratic-display:none fix) and carried the TODO forward rather than acting on it. And 27 of 28 RecreateFramesForContent call sites pass Async, so deleting it changes the dominant reframe path across all of frame construction — a blast radius unrelated to this bug, and one that would make any regression here un-bisectable against the batching.

The restructure makes both easier to remove later: each is now a single block in one shared function. The async one is the more tractable follow-up, since non-elements already take the lazy path today, so ConstructLazily is already exercised.

---

debug try: https://treeherder.mozilla.org/jobs?repo=try&revision=ea0fed544ad2e5632c30279c47da1daba9601ade
opt try: https://treeherder.mozilla.org/jobs?repo=try&revision=7a465cc4a539d718f9e551fc89fe0aa17bb68f68

Comment 15

[Mayank Bansal]

Patches updated and pushed to try.
See the reasoning in comment 14. Let me know if this was not the direction you meant.

Comment 16

[Emilio Cobos Álvarez [:emilio]]

The change looks about right but I don't know why the in-out parameter is needed. Isn't the mathml case basically equivalent to "reframed an ancestor"?

Comment 17

[Mayank Bansal]

try opt: https://treeherder.mozilla.org/jobs?repo=try&revision=9cf5dd9e5b389411c403077f147054161fe760da
try debug: https://treeherder.mozilla.org/jobs?repo=try&revision=ae83b29722a18e5eaea6cfd1235905e63f3a78f7

Comment 18

[Mayank Bansal]

Please take another look.

Comment 19

[Mayank Bansal]

Try debug: https://treeherder.mozilla.org/jobs?repo=try&revision=3d4b3d4783b79ea62bbd2cf040ae9fb0f82609ef
Try Opt: https://treeherder.mozilla.org/jobs?repo=try&revision=1237ddc78508c669d1555ce83d17492be2b987b9

Comment 20

[Mayank Bansal]

Try debug: https://treeherder.mozilla.org/jobs?repo=try&revision=66c6fb85e9881035eff96a7ac1c8f45ec9d9922e
Try opt: https://treeherder.mozilla.org/jobs?repo=try&revision=9b07f319e6f74adf70423d3391a729ed88c55923