Make updateLayoutAndStyleForPainting() O(N) in terms of frame number in LayoutView::hitTest()

Make updateLayoutAndStyleForPainting() O(N) in terms of frame number in LayoutView::hitTest()

In LayoutView::hitTest, we call updateLayoutAndStyleForPainting() before
actual hitTesting. updateLayoutAndStyleForPainting() will do the update
on all the iframes in the document even if the originating update is
issued from one particular iframe. This makes hit testing expensive for
page that has many iframes since LayoutView::hitTest() is also called on
every iframe, which makes the layout and style update O(N^2) in terms
of iframe numbers.

This CL moves the call of updateLayoutAndStyleForPainting() one level up
so recursive hit testing on iframe won't trigger updateLayoutAndStyleForPainting()
again.


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

[Yufeng Shen (Slow to review), 2015-06-17 00:50:04]

miletus@chromium.org changed reviewers:
+ chrishtr@chromium.org, esprehn@chromium.org

[esprehn, 2015-06-17 01:17:51]

We should move the call up a level instead into Document or FrameView
instead of having this bit in the recursion state.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[Yufeng Shen (Slow to review), 2015-06-17 14:50:22]

On 2015/06/17 01:17:51, esprehn wrote:
> We should move the call up a level instead into Document or FrameView
> instead of having this bit in the recursion state.
> 
> To unsubscribe from this group and stop receiving emails from it, send an
email
> to mailto:blink-reviews+unsubscribe@chromium.org.

So here is the complication:

In LayoutView::hitTest(), we first call
frameView()->updateLayoutAndStyleForPainting()
and then do actual hitTest, which will recursively do the hit test in its
children
through LayoutObject::nodeAtPoint(), and if there are LayoutPart(iframes),
LayoutPart::nodeAtPoint() will call into the iframe's LayoutView::hitTest(), in
which
frameView()->updateLayoutAndStyleForPainting() is called again.

Ideally, say if EventHandler::foo() -> LayoutView::hitTest(), we want it to be
EventHandelr::foo() -> updateLayoutAndStyleForPainting() ->
LayoutView::hitTest*NoUpdate*()

But the problem is that for LayoutPart::nodeAtPoint. If we do
LayoutPart::nodeAtPoint() -> updateLayoutAndStyleForPainting() ->
LayoutView::hitTest*NoUpdate*()
but LayoutPart::nodeAtPoint() is still called on every iframe, so this does not
avoid the extra
updateLayoutAndStyleForPainting().

So we have to move updateLayoutAndStyleForPainting() to be before calling
LayoutPart::nodeAtPoint().
But LayoutPart::nodeAtPoint is a virtual function inheriting from
LayoutObject::nodeAtPoint(), which
will have so many caller site which could make the change not trackable.

That's why I came up with the HitTestRequest::SkipUpdateLayoutAndStyle solution
in this CL.
If we can't be sure to track all the calling path, lets at least select some
important calling
path, do the updateLayoutAndStyleForPainting() first, then pass the flag down so
that
we can avoid unnecessary updateLayoutAndStyleForPainting() down the recursion
chain.

Any suggestion on how this can be done more cleanly ?

[dtapuska, 2015-06-17 15:02:58]

On 2015/06/17 14:50:22, Yufeng Shen wrote:
> On 2015/06/17 01:17:51, esprehn wrote:
> > We should move the call up a level instead into Document or FrameView
> > instead of having this bit in the recursion state.
> > 
> > To unsubscribe from this group and stop receiving emails from it, send an
> email
> > to mailto:blink-reviews+unsubscribe@chromium.org.
> 
> So here is the complication:
> 
> In LayoutView::hitTest(), we first call
> frameView()->updateLayoutAndStyleForPainting()
> and then do actual hitTest, which will recursively do the hit test in its
> children
> through LayoutObject::nodeAtPoint(), and if there are LayoutPart(iframes),
> LayoutPart::nodeAtPoint() will call into the iframe's LayoutView::hitTest(),
in
> which
> frameView()->updateLayoutAndStyleForPainting() is called again.
> 
> Ideally, say if EventHandler::foo() -> LayoutView::hitTest(), we want it to be
> EventHandelr::foo() -> updateLayoutAndStyleForPainting() ->
> LayoutView::hitTest*NoUpdate*()
> 
> But the problem is that for LayoutPart::nodeAtPoint. If we do
> LayoutPart::nodeAtPoint() -> updateLayoutAndStyleForPainting() ->
> LayoutView::hitTest*NoUpdate*()
> but LayoutPart::nodeAtPoint() is still called on every iframe, so this does
not
> avoid the extra
> updateLayoutAndStyleForPainting().
> 
> So we have to move updateLayoutAndStyleForPainting() to be before calling
> LayoutPart::nodeAtPoint().
> But LayoutPart::nodeAtPoint is a virtual function inheriting from
> LayoutObject::nodeAtPoint(), which
> will have so many caller site which could make the change not trackable.
> 
> That's why I came up with the HitTestRequest::SkipUpdateLayoutAndStyle
solution
> in this CL.
> If we can't be sure to track all the calling path, lets at least select some
> important calling
> path, do the updateLayoutAndStyleForPainting() first, then pass the flag down
so
> that
> we can avoid unnecessary updateLayoutAndStyleForPainting() down the recursion
> chain.
> 
> Any suggestion on how this can be done more cleanly ?

I'm not debating this change; pros vs cons; aside from I think are other call
sites that call directly into the LayoutView::hit test like
Internals.nodesFromRect that won't benefit from this change.

But I'd rather discuss https://codereview.chromium.org/1126883002

In that we should be setting bits on the parent layout views indicating a walk
is necessary. The real problem with this page is the explosion of iframes and
the walks that are necessary. Can we avoid the walks all together but passing
information up the tree as opposed to doing a walk to find out something is
necessary?

[Yufeng Shen (Slow to review), 2015-06-17 15:42:05]

On 2015/06/17 15:02:58, Dave Tapuska wrote:
> On 2015/06/17 14:50:22, Yufeng Shen wrote:
> > On 2015/06/17 01:17:51, esprehn wrote:
> > > We should move the call up a level instead into Document or FrameView
> > > instead of having this bit in the recursion state.
> > > 
> > > To unsubscribe from this group and stop receiving emails from it, send an
> > email
> > > to mailto:blink-reviews+unsubscribe@chromium.org.
> > 
> > So here is the complication:
> > 
> > In LayoutView::hitTest(), we first call
> > frameView()->updateLayoutAndStyleForPainting()
> > and then do actual hitTest, which will recursively do the hit test in its
> > children
> > through LayoutObject::nodeAtPoint(), and if there are LayoutPart(iframes),
> > LayoutPart::nodeAtPoint() will call into the iframe's LayoutView::hitTest(),
> in
> > which
> > frameView()->updateLayoutAndStyleForPainting() is called again.
> > 
> > Ideally, say if EventHandler::foo() -> LayoutView::hitTest(), we want it to
be
> > EventHandelr::foo() -> updateLayoutAndStyleForPainting() ->
> > LayoutView::hitTest*NoUpdate*()
> > 
> > But the problem is that for LayoutPart::nodeAtPoint. If we do
> > LayoutPart::nodeAtPoint() -> updateLayoutAndStyleForPainting() ->
> > LayoutView::hitTest*NoUpdate*()
> > but LayoutPart::nodeAtPoint() is still called on every iframe, so this does
> not
> > avoid the extra
> > updateLayoutAndStyleForPainting().
> > 
> > So we have to move updateLayoutAndStyleForPainting() to be before calling
> > LayoutPart::nodeAtPoint().
> > But LayoutPart::nodeAtPoint is a virtual function inheriting from
> > LayoutObject::nodeAtPoint(), which
> > will have so many caller site which could make the change not trackable.
> > 
> > That's why I came up with the HitTestRequest::SkipUpdateLayoutAndStyle
> solution
> > in this CL.
> > If we can't be sure to track all the calling path, lets at least select some
> > important calling
> > path, do the updateLayoutAndStyleForPainting() first, then pass the flag
down
> so
> > that
> > we can avoid unnecessary updateLayoutAndStyleForPainting() down the
recursion
> > chain.
> > 
> > Any suggestion on how this can be done more cleanly ?
> 
> I'm not debating this change; pros vs cons; aside from I think are other call
> sites that call directly into the LayoutView::hit test like
> Internals.nodesFromRect that won't benefit from this change.
> 
> But I'd rather discuss https://codereview.chromium.org/1126883002
> 
> In that we should be setting bits on the parent layout views indicating a walk
> is necessary. The real problem with this page is the explosion of iframes and
> the walks that are necessary. Can we avoid the walks all together but passing
> information up the tree as opposed to doing a walk to find out something is
> necessary?

I like this idea. Solving the problem of unnecessary calls of
updateLayoutAndStyleForPainting() in general is beyond the scope of
this CL and presumably a harder problem since you would need to maintain a
layout_and_style_is_valid bit in the root frame and adding logic for when
it becomes dirty.

But if we limit our scope just to hit testing, then there is this clean to 
do so:

FrameView {
  bool layout_and_sytle_updated_for_hit_test_;
}

ScopedLayoutAndSytleUpdateForHitTestReset {
    
   ScopedLayoutAndSytleUpdateForHitTestReset() {}
   ~ScopedLayoutAndSytleUpdateForHitTestReset() {
      if (frame_view_)
         frame_view_->set_layout_and_sytle_updated_for_hit_test(false);
   }
    
   SetFrameView(FrameView* frame_view) {
      frame_view_ = frame_view;
   }    
private:
   FrameView* frame_view_;
  
}

LayoutView::hitTest {

   ScopedLayoutAndSytleUpdateForHitTestReset resetter;

   if (!root_frameView->layout_and_sytle_updated_for_hit_test()) {
       frameView()->updateLayoutAndStyleForPainting();
       root_frameView->set_layout_and_sytle_updated_for_hit_test(true);
       resetter.SetFrameView(root_frameView);
   }

   ....
}


So a direct all into LayoutView::hitTest() will call
frameView()->updateLayoutAndStyleForPainting()
while recursive call into LayoutView::hitTest() will avoid that.

What do you guys think ?

[esprehn, 2015-06-17 17:47:22]

That's a separate issue that needs a more global fix, I think you're making this
change too complicated. LayoutView has two methods for hit testing:

A)    bool hitTest(HitTestResult&);
B)    bool hitTest(const HitTestRequest&, const HitTestLocation&,
HitTestResult&);

A calls B.
B currently does frameView()->updateLayoutAndStyleForPainting();

There's only two callers of B. A calling B, and the recursion into LayoutParts.

So we move the updateLayoutAndStyleForPainting call into A and the n^2 goes
away. Should be a very tiny change.

[Yufeng Shen (Slow to review), 2015-06-17 20:32:26]

On 2015/06/17 17:47:22, esprehn wrote:
> That's a separate issue that needs a more global fix, I think you're making
this
> change too complicated. LayoutView has two methods for hit testing:
> 
> A)    bool hitTest(HitTestResult&);
> B)    bool hitTest(const HitTestRequest&, const HitTestLocation&,
> HitTestResult&);
> 
> A calls B.
> B currently does frameView()->updateLayoutAndStyleForPainting();
> 
> There's only two callers of B. A calling B, and the recursion into
LayoutParts.
> 
> So we move the updateLayoutAndStyleForPainting call into A and the n^2 goes
> away. Should be a very tiny change.


Alright, I was being conservative in assuming LayoutPart::nodeAtPoint() can be
called not through A so we miss the updateLayoutAndStyleForPainting. Elliott's
view is that if that happens, then it is a bug that the caller is at fault not
doing the updateLayoutAndSytlePainting. That makes sense, if some code path
misses updateLayoutAndSytlePainting, DeprecatedPaintLayer::hitTest() will crash
on having pendingLayout() so it is fine to let it crash and fix it.

I have simplified the CL. PTAL, thanks.


not through A)

[esprehn, 2015-06-17 20:34:32]

lgtm

[Yufeng Shen (Slow to review), 2015-06-17 20:38:02]

The CQ bit was checked by miletus@chromium.org

[commit-bot: I haz the power, 2015-06-17 20:39:07]

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

[commit-bot: I haz the power, 2015-06-17 20:43:47]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-06-17 20:43:48]

Try jobs failed on following builders:
  mac_blink_compile_dbg on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/mac_blink_compile_dbg/bu...)
  mac_blink_rel on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/59332)

[Yufeng Shen (Slow to review), 2015-06-17 21:15:15]

The CQ bit was checked by miletus@chromium.org

[Yufeng Shen (Slow to review), 2015-06-17 21:15:15]

The patchset sent to the CQ was uploaded after l-g-t-m from esprehn@chromium.org
Link to the patchset: https://codereview.chromium.org/1194473003/#ps40001
(title: "rebase")

[Yufeng Shen (Slow to review), 2015-06-17 21:15:59]

On 2015/06/17 20:43:48, commit-bot: I haz the power wrote:
> Try jobs failed on following builders:
>   mac_blink_compile_dbg on tryserver.blink (JOB_FAILED,
>
http://build.chromium.org/p/tryserver.blink/builders/mac_blink_compile_dbg/bu...)
>   mac_blink_rel on tryserver.blink (JOB_FAILED,
>
http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/59332)

Dave's recent hit-test cache CL merged the 2 LayoutView::hitTest() into one, I
have
to unmerge them.

[commit-bot: I haz the power, 2015-06-17 21:16:11]

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

[commit-bot: I haz the power, 2015-06-17 23:05:08]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-06-17 23:05:09]

Try jobs failed on following builders:
  mac_blink_rel on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/59345)

[Yufeng Shen (Slow to review), 2015-06-18 00:17:10]

The CQ bit was checked by miletus@chromium.org

[Yufeng Shen (Slow to review), 2015-06-18 00:17:10]

The patchset sent to the CQ was uploaded after l-g-t-m from esprehn@chromium.org
Link to the patchset: https://codereview.chromium.org/1194473003/#ps60001
(title: "rebasae layout test result because the order of the when the tracing
runs changed")

[commit-bot: I haz the power, 2015-06-18 00:17:43]

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

[commit-bot: I haz the power, 2015-06-18 01:50:05]

Committed patchset #4 (id:60001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=197305