Keep track of multiple layout roots

Keep track of multiple layout roots

Prior to this patch, we'd only keep track of one subtree layout
root, and always dirty layout up the tree to the shared common
ancestor when another was added. This can result in a lot of extra
tree walking in certain cases.

This patch instead keeps a HashSet of subtree layout roots, clearing
them only when layout occurs, a full layout is scheduled, or the roots
themselves are cleared.

BUG=454255
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=191035

[leviw_travelin_and_unemployed, 2015-02-20 01:17:22]

leviw@chromium.org changed reviewers:
+ dsinclair@chromium.org, eae@chromium.org, jchaffraix@chromium.org,
pdr@chromium.org

[leviw_travelin_and_unemployed, 2015-02-20 22:42:24]

PTAL

https://codereview.chromium.org/927773002/diff/160001/LayoutTests/TestExpecta...
File LayoutTests/TestExpectations (left):

https://codereview.chromium.org/927773002/diff/160001/LayoutTests/TestExpecta...
LayoutTests/TestExpectations:1824: crbug.com/458420 [ Win Debug ]
virtual/threaded/fast/scroll-behavior/overflow-scroll-animates.html [ Timeout ]
These are just here because the linter was complaining about this test not
existing.

https://codereview.chromium.org/927773002/diff/160001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/160001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:864: static void
gatherDebugLayoutRects(LayoutObject& layoutRoot)
This is just being moved up in the file.

[leviw_travelin_and_unemployed, 2015-02-20 23:00:37]

FWIW: the compiler error is unrelated :(

[eae, 2015-02-20 23:16:13]

Change looks good but the test change doesn't really make sense to me.

https://codereview.chromium.org/927773002/diff/160001/LayoutTests/fast/layout...
File LayoutTests/fast/layout/common-ancestor-relayout-boundary.html (right):

https://codereview.chromium.org/927773002/diff/160001/LayoutTests/fast/layout...
LayoutTests/fast/layout/common-ancestor-relayout-boundary.html:35:
shouldBe("window.internals.needsLayoutCount()", "4");
Shouldn't this be 5? Also, this really needs a comment.

[leviw_travelin_and_unemployed, 2015-02-20 23:41:25]

Added a comment. Thanks EAE!

[eae, 2015-02-20 23:42:16]

LGTM

[leviw_travelin_and_unemployed, 2015-02-20 23:58:51]

The CQ bit was checked by leviw@chromium.org

[commit-bot: I haz the power, 2015-02-20 23:59:50]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/927773002/180001

[Julien - ping for review, 2015-02-21 00:13:16]

Cancelling the commit bit as I have some doubt about the change and would like
the time get them resolved before landing.

[Julien - ping for review, 2015-02-21 00:13:19]

The CQ bit was unchecked by jchaffraix@chromium.org

[Julien - ping for review, 2015-02-21 00:33:20]

jchaffraix@chromium.org changed reviewers:
+ esprehn@chromium.org, ojan@chromium.org

[Julien - ping for review, 2015-02-21 00:33:21]

+Elliott/Ojan as they are big proponent of simplicity.

I think this patch makes a strong statement that subtree layout are pretty
frequent. It would be interesting to have better data on that (Elliott might
have had some IIRC). Also having better performance data would explain why this
changes.

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:917: if (!root.needsLayout())
That looks terribly wrong. This means that we have a race condition between 2
descendant / ancestor layout roots. This condition catches the good situation.

However the bad situation is when layout the descendant before laying out the
containing layout root. This would result in a *double layout* of the descendant
subtree.

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:725: HashSet<LayoutObject*> m_layoutSubtreeRoots;
Note that HashSet has no notion of tree order or insertion order. It basically
means that the layout order is going to be different on different machine.

[leviw_travelin_and_unemployed, 2015-02-21 00:39:09]

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:917: if (!root.needsLayout())
On 2015/02/21 00:33:21, Julien Chaffraix - PST wrote:
> That looks terribly wrong. This means that we have a race condition between 2
> descendant / ancestor layout roots. This condition catches the good situation.
> 
> However the bad situation is when layout the descendant before laying out the
> containing layout root. This would result in a *double layout* of the
descendant
> subtree.

This will *only* occur when both the descendant and ancestor are isolated layout
roots themselves, and hence the ordering shouldn't matter.

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:725: HashSet<LayoutObject*> m_layoutSubtreeRoots;
On 2015/02/21 00:33:21, Julien Chaffraix - PST wrote:
> Note that HashSet has no notion of tree order or insertion order. It basically
> means that the layout order is going to be different on different machine.

Right. As long as these are only ever layout boundaries we shouldn't care.

[dsinclair, 2015-02-21 01:07:12]

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1092: m_layoutSubtreeRoot = nullptr;
Remove?

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:724: LayoutObject* m_layoutSubtreeRoot;
It seems like this should be removed now?

[leviw_travelin_and_unemployed, 2015-02-23 18:45:48]

New patchsets have been uploaded after l-g-t-m from eae@chromium.org

[leviw_travelin_and_unemployed, 2015-02-23 18:47:00]

Good calls. Fixed.

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1092: m_layoutSubtreeRoot = nullptr;
On 2015/02/21 01:07:12, dsinclair wrote:
> Remove?

Acknowledged.

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/180001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:724: LayoutObject* m_layoutSubtreeRoot;
On 2015/02/21 01:07:12, dsinclair wrote:
> It seems like this should be removed now?

Acknowledged.

[ojan, 2015-02-23 19:23:57]

I'm definitely supportive of making the codebase as simple as possible in
general. This specific patch doesn't seem to add undue complexity to me since,
a) it's mostly just moving code around and b) any added complexity is contained
to RenderView and c) it removes a bit of complexity around merging layout roots.

I have one tiny performance concern, but I don't know how valid it is or that it
needs to block the patch landing.

I'll also add that, in general, I think we should move in the direction of
making layout boundaries more common and more strict, even going so far as
giving web developers an explicit way of marking elements as layout boundaries.
This is something that web developers do hit in high performance applications
and go through painful contortions to achieve today (e.g. sencha uses iframes).

Even before adding new APIs, there are some cop-outs in the check for whether
something is a layout root that could be improved to make this case more common
(e.g. with percentages).

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1086: for (auto root =
m_layoutSubtreeRoots.begin(); root != end; ++root) {
for (auto& root : m_layoutSubtreeRoots)

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1867: for (auto iter =
m_layoutSubtreeRoots.begin(); iter != end; ++iter)
for (auto& root : m_layoutSubtreeRoots)

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1867: for (auto iter =
m_layoutSubtreeRoots.begin(); iter != end; ++iter)
for (auto& root : m_layoutSubtreeRoots)

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1915: m_layoutSubtreeRoots.add(relayoutRoot);
The only technical concern I have with this patch is right here. You've replaced
setting a pointer with inserting into a hashtable. I honestly don't know if this
will matter at all, but it's a tiny red flag since we do know that this is a
relatively hot function. I assume you ran some basic perf tests?

[Julien - ping for review, 2015-02-23 19:33:44]

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1088: container->setMayNeedPaintInvalidation();
Is this code executed? You're removing pointers from m_layoutSubtreeRoots in
performLayout.

I think that's the cause of the test change (and probably a regression :().

https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1876: m_isSubtreeLayout = false;
There is a window in which we could leave pointers into m_layoutSubtreeRoots
with m_isSubtreeLayout set false.

I would like us to have some of the following ASSERTs peppered where it makes
sense in the code:

ASSERT(m_isSubtreeLayout || !m_layoutSubtreeRoots.isEmpty());

[leviw_travelin_and_unemployed, 2015-02-23 23:05:30]

On 2015/02/23 at 19:33:44, jchaffraix wrote:
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> File Source/core/frame/FrameView.cpp (right):
> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1088:
container->setMayNeedPaintInvalidation();
> Is this code executed? You're removing pointers from m_layoutSubtreeRoots in
performLayout.
> 
> I think that's the cause of the test change (and probably a regression :().

I moved that code up into the performLayout method. I still believe that
LayoutTest's invalidations are correct.

>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1876: m_isSubtreeLayout = false;
> There is a window in which we could leave pointers into m_layoutSubtreeRoots
with m_isSubtreeLayout set false.
> 
> I would like us to have some of the following ASSERTs peppered where it makes
sense in the code:
> 
> ASSERT(m_isSubtreeLayout || !m_layoutSubtreeRoots.isEmpty());

Done.

[leviw_travelin_and_unemployed, 2015-02-23 23:07:08]

On 2015/02/23 at 19:23:57, ojan wrote:
> I'm definitely supportive of making the codebase as simple as possible in
general. This specific patch doesn't seem to add undue complexity to me since,
a) it's mostly just moving code around and b) any added complexity is contained
to RenderView and c) it removes a bit of complexity around merging layout roots.
> 
> I have one tiny performance concern, but I don't know how valid it is or that
it needs to block the patch landing.
> 
> I'll also add that, in general, I think we should move in the direction of
making layout boundaries more common and more strict, even going so far as
giving web developers an explicit way of marking elements as layout boundaries.
This is something that web developers do hit in high performance applications
and go through painful contortions to achieve today (e.g. sencha uses iframes).
> 
> Even before adding new APIs, there are some cop-outs in the check for whether
something is a layout root that could be improved to make this case more common
(e.g. with percentages).

> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> File Source/core/frame/FrameView.cpp (right):
> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1086: for (auto root =
m_layoutSubtreeRoots.begin(); root != end; ++root) {
> for (auto& root : m_layoutSubtreeRoots)
> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1867: for (auto iter =
m_layoutSubtreeRoots.begin(); iter != end; ++iter)
> for (auto& root : m_layoutSubtreeRoots)
> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1867: for (auto iter =
m_layoutSubtreeRoots.begin(); iter != end; ++iter)
> for (auto& root : m_layoutSubtreeRoots)
> 
>
https://codereview.chromium.org/927773002/diff/200001/Source/core/frame/Frame...
> Source/core/frame/FrameView.cpp:1915: m_layoutSubtreeRoots.add(relayoutRoot);
> The only technical concern I have with this patch is right here. You've
replaced setting a pointer with inserting into a hashtable. I honestly don't
know if this will matter at all, but it's a tiny red flag since we do know that
this is a relatively hot function. I assume you ran some basic perf tests?

Agreed. I ran the benchmarks and have submitted a number of perf tryjobs that
haven't shown any regressions, but the results are really noisy. I'm pretty
confident this won't negatively impact us.

[esprehn, 2015-02-24 02:31:33]

https://codereview.chromium.org/927773002/diff/220001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/220001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:105: bool isLayoutRoot(const LayoutObject*) const;
reference.

https://codereview.chromium.org/927773002/diff/220001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:109: void countObjectsNeedingLayout(unsigned&
needsLayoutObjects, unsigned& totalObjects, bool& isPartial);
This should really use a struct, but we can fix that later.

https://codereview.chromium.org/927773002/diff/220001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:725: bool m_isSubtreeLayout;
It seems like we should be able to get rid of this bool, either the HashSet is
non-empty and it's a subtree layout or it's a full layout. The bool is just a
proxy for !isEmpty().

[leviw_travelin_and_unemployed, 2015-02-27 00:22:27]

PTAL

[dsinclair, 2015-02-27 16:12:09]

This is good to me, but I'll defer to the people with more knowledge.

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:758: static inline void
countObjectsNeedingLayoutInRoot(const LayoutObject* root, unsigned&
needsLayoutObjects, unsigned& totalObjects)
Can the root be null? If not, can we make this LayoutObject&?

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1085: // FIXME: Could find the common ancestor
layer of all dirty subtrees and mark from there.
crbug link?

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:1842: void
FrameView::clearLayoutSubtreeRoot(const LayoutObject* root)
Can this be a reference?

[Julien - ping for review, 2015-02-27 16:38:09]

lgtm

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:776: isSubtree = false;
IMHO that would be more readable if it was outside the branch:

isSubtree = isSubtreeLayout();

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:911: layoutFromRootObject(root);
We could unify the 2 code paths by inserting the RenderView into the
m_layoutSubtreeRoots. This would require removing completely the concept of
subtree layout, which should be fine. This would reduce the complexity of layout
greatly but increase the layoutRoot insertion logic. It's better done in a
follow-up patch anyway.

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
File Source/core/frame/FrameView.h (right):

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.h:106: void clearLayoutSubtreeRoot(const
LayoutObject*);
Should we also use a reference here for API coherency? (we also don't expect
nullptr)

[leviw_travelin_and_unemployed, 2015-02-27 20:09:28]

Thanks for the review!

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
File Source/core/frame/FrameView.cpp (right):

https://codereview.chromium.org/927773002/diff/280001/Source/core/frame/Frame...
Source/core/frame/FrameView.cpp:911: layoutFromRootObject(root);
On 2015/02/27 16:38:09, Julien Chaffraix - PST wrote:
> We could unify the 2 code paths by inserting the RenderView into the
> m_layoutSubtreeRoots. This would require removing completely the concept of
> subtree layout, which should be fine. This would reduce the complexity of
layout
> greatly but increase the layoutRoot insertion logic. It's better done in a
> follow-up patch anyway.

That's my ultimate goal :)

[leviw_travelin_and_unemployed, 2015-02-27 21:28:46]

The CQ bit was checked by leviw@chromium.org

[leviw_travelin_and_unemployed, 2015-02-27 21:28:46]

The patchset sent to the CQ was uploaded after l-g-t-m from eae@chromium.org,
jchaffraix@chromium.org
Link to the patchset: https://codereview.chromium.org/927773002/#ps320001
(title: "Add bug link")

[commit-bot: I haz the power, 2015-02-27 21:29:07]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/927773002/320001

[commit-bot: I haz the power, 2015-02-28 00:22:13]

Committed patchset #17 (id:320001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=191035