1865012 - Consider cache first continuation pointer in nsSplittableFrame so that accessing FirstContinuation()/FirstInFlow() is constant-time

Status: RESOLVED FIXED

(Core :: Layout, enhancement)

Description

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Per Daniel's review comment in https://phabricator.services.mozilla.com/D188532#inline-1074001, FirstInFlow() isn't constant-time; it's linear in length of our prev-in-flow chain.

We have many existing code dealing with fragmentation that need to store data in the first-in-flow. To name a few: SharedFlexData in flex container [1], cell map & layout strategy in table frame [2], and SharedGridData in grid container [3].

One way to ease the linear time traversal overhead is to cache first-in-flow pointer in a frame property, and assert the cached value matches FirstInFlow().

[1] https://searchfox.org/mozilla-central/rev/21001eee69767de5db95952154d49f01b72318ba/layout/generic/nsFlexContainerFrame.cpp#4727-4736
[2] https://searchfox.org/mozilla-central/rev/21001eee69767de5db95952154d49f01b72318ba/layout/tables/nsTableFrame.cpp#196-204
[3] https://searchfox.org/mozilla-central/rev/f78093864e287014db7ac9383bb76c45edbf8559/layout/generic/nsGridContainerFrame.cpp#9192-9198

Comment 1

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

nsTextFrame and nsContinuingTextFrame are not inherited from nsSplittableFrame, but we've implemented the similar idea in Bug 1725555 (specifically in Bug 1725555 Part 1)

Comment 2

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1865012 Part 1 - Change two if-statements to match coding style. r?dholbert

Comment 3

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1865012 Part 1 - Make accessing first-continuation and first-in-flow constant time. r?dholbert

This patch contains two major parts. The first part is in nsSplittableFrame,
implementing the first-in-flow and first-continuation cache. The second part
adds nsFrameList::RemoveLastChild, and converts callers that involve in
destroying the frame list.

With only the first part, layout/generic/crashtests/1683126.html will timeout.
It can be reproduced locally via

./mach crashtest layout/generic/crashtests/1683126.html

It is because if we destroy a frame list from the first child to the last child,
each time we destroy the first child [1], the second child become the new first
child, and we have to update the first-in-flow and first-continuation cache for
later continuations, which is a linear time operation. Therefore we need the
second part to avoid that.

[1] See nsSplittableFrame::RemoveFromFlow() with the argument being the first
child in a frame list.

Depends on D197756

Comment 4

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1865012 Part 3 - Remove FirstContinuation overrides for nsPageFrame and nsPageContentFrame. r?dholbert

The overrides were added in bug 1803861. With Part 2, they are no longer needed.

Actually, without this patch, the assertion "First descendent of
nsPageSequenceFrame should not have a previous continuation" in
nsPageFrame::FirstContinuation will be triggered when constructing frame tree,
because nsSplittableFrame::SetPrevContinuation now accesses
FirstContinuation(), but the parent-child relationship might not properly set
up yet.

Depends on D197757

Comment 5

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1865012 Part 4 - Remove PageValuesProperty copy in frame continuations. r?dholbert

It was added in bug 1804772. After Part 2, accessing FirstInFlow() is constant
time, so we don't need to duplicate PageValuesProperty in each frame
continuation.

Depends on D197758

Comment 6

[Phabricator Automation]

Comment on attachment 9371225 [details]
Bug 1865012 Part 1 - Change two if-statements to match coding style. r?dholbert

Revision D197756 was moved to bug 1873530. Setting attachment 9371225 [details] to obsolete.

Comment 7

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1865012 Part 2 - Add nsFrameList::RemoveLastChild, and destroy frame list in reverse order. r?dholbert

With only the Part 1, layout/generic/crashtests/1683126.html will timeout.
It can be reproduced locally via

./mach crashtest layout/generic/crashtests/1683126.html

It is because if we destroy a frame list from the first child to the last child,
each time we destroy the first child [1], the second child become the new first
child, and we have to update the first-in-flow and first-continuation cache for
later continuations, which is a linear time operation.

[1] See nsSplittableFrame::RemoveFromFlow() with the argument being the first
child in a frame list.

Depends on D197757

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/4fb71ff990ae
Part 1 - Make accessing first-continuation and first-in-flow constant time. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/30a3c356ebc9
Part 2 - Add nsFrameList::RemoveLastChild, and destroy frame list in reverse order. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/26f6c2765cb5
Part 3 - Remove FirstContinuation overrides for nsPageFrame and nsPageContentFrame. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/95d920859b91
Part 4 - Remove PageValuesProperty copy in frame continuations. r=dholbert

Comment 9

[Norisz Fay [:noriszfay]]

Backed out for causing mochitest failure on test_gencontent.html

Backout link

Push with failures

Failure log

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/38008e0bc349
Part 1 - Make accessing first-continuation and first-in-flow constant time. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/e8114275db22
Part 2 - Add nsFrameList::RemoveLastChild, and destroy frame list in reverse order. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/a54fc613ccde
Part 3 - Remove FirstContinuation overrides for nsPageFrame and nsPageContentFrame. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/a8758ae8e80d
Part 4 - Remove PageValuesProperty copy in frame continuations. r=dholbert

Comment 11

[Cosmin Sabou [:CosminS]]

https://hg.mozilla.org/mozilla-central/rev/38008e0bc349
https://hg.mozilla.org/mozilla-central/rev/e8114275db22
https://hg.mozilla.org/mozilla-central/rev/a54fc613ccde
https://hg.mozilla.org/mozilla-central/rev/a8758ae8e80d