Bug 49220

Summary: REGRESSION: transform matrix applied too many times when nested
Product: WebKit Reporter: Nico Weber <thakis>
Component: Layout and RenderingAssignee: Dave Hyatt <hyatt>
Status: RESOLVED FIXED    
Severity: Normal CC: bdakin, eric, hamaji, hyatt, kenneth, mihaip, noam, simon.fraser, tonikitoo
Priority: P1 Keywords: InRadar
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
URL: http://www.satine.org/research/webkit/snowleopard/snowstack.html
Bug Depends on: 50970    
Bug Blocks: 50963    
Attachments:
Description Flags
Testcase
none
Testcase (simplified)
none
Work in progress.
none
Work in progress
none
Work in progress
none
Work in progress
none
Patch with updated test results
none
Patch for review.
none
Patch (fix tabs in ChangeLog) simon.fraser: review+

Description Nico Weber 2010-11-08 16:12:01 PST
Go to http://www.satine.org/research/webkit/snowleopard/snowstack.html

It is very very slow both with compositing enabled and disabled, both in the webkit nightly and in chrome. This regressed in chromium r63327, which was a webkit roll from r70157 to r70206.

http://trac.webkit.org/changeset/70170 looks most related in that range.

http://trac.webkit.org/changeset/70172 and http://trac.webkit.org/changeset/70198 might also be related.
Comment 1 Beth Dakin 2010-11-08 16:50:32 PST
According to my testing, http://trac.webkit.org/changeset/70170 is definitely to blame for some (and likely all) of the regression.
Comment 2 Simon Fraser (smfr) 2010-11-08 17:23:47 PST
<rdar://problem/8644849>
Comment 3 Simon Fraser (smfr) 2010-11-08 17:25:41 PST
Lots of time in TransformationMatrix::multLeft()
Comment 4 Mihai Parparita 2010-11-24 08:36:04 PST
Created attachment 74763 [details]
Testcase

Here's a reduced testcase based on the Snowstack markup. In ToT, the time to layout based on number of enclosing containers:

0: 3ms
1: 4ms
2: 10ms
3: 28ms
4: 103ms
5: 406ms
6: 1632ms
7: 6641ms

Safari 5.0.2 always has constant time (~3 ms).
Comment 5 Simon Fraser (smfr) 2010-11-26 10:34:41 PST
How does it behave if body has { overflow: hidden; } in your testcase?
Comment 6 Mihai Parparita 2010-11-29 09:54:08 PST
(In reply to comment #5)
> How does it behave if body has { overflow: hidden; } in your testcase?

Doesn't change anything.

We still end up in RenderView::layout, which calls docWidth() and docHeight(), which in turn call rightmostPosition() and lowestPosition(). Looking at RenderBlock::rightmostPosition, we call transformedFrameRect once at the start, once for each child. But then we also recurse for each child, and we also call topmost/lowest/leftmostPosition at the end, which do their own recursing. An even simpler test case (two nested containers, three leaf nodes; attachment to follow) ends up calling RenderBox::applyLayerTransformToRect 1272 times.
Comment 7 Mihai Parparita 2010-11-29 09:54:44 PST
Created attachment 75038 [details]
Testcase (simplified)
Comment 8 Simon Fraser (smfr) 2010-11-29 11:20:06 PST
Right, we have some high-order perf issues here.
Comment 9 Simon Fraser (smfr) 2010-11-29 13:20:27 PST
The plan of action here:

1. Clean up RenderBox::applyLayerTransformToRect():
     a) no need for transform.makeIdentity();
     b) layer()->updateTransform(); should not be necessary here: i filed bug 50175 on that issue.

2. Cache the transformedFrameRect() on the layer.
3. See what's left.
Comment 10 Simon Fraser (smfr) 2010-11-29 15:45:12 PST
Things are still very slow with a cached transformedFrameRect.
Comment 11 Dave Hyatt 2010-12-03 23:09:33 PST
Created attachment 75601 [details]
Work in progress.
Comment 12 Dave Hyatt 2010-12-04 00:34:03 PST
Created attachment 75604 [details]
Work in progress

Still working on passing everything but getting pretty close.
Comment 13 Dave Hyatt 2010-12-04 12:21:29 PST
Created attachment 75613 [details]
Work in progress
Comment 14 Dave Hyatt 2010-12-05 00:22:56 PST
Created attachment 75626 [details]
Work in progress
Comment 15 Dave Hyatt 2010-12-05 23:53:46 PST
Created attachment 75651 [details]
Patch with updated test results

No ChangeLog yet.  Flagging just to make sure it builds on other platforms and to get style checks.
Comment 16 Dave Hyatt 2010-12-06 09:49:26 PST
Created attachment 75708 [details]
Patch for review.
Comment 17 Dave Hyatt 2010-12-06 10:09:44 PST
Created attachment 75709 [details]
Patch (fix tabs in ChangeLog)
Comment 18 Simon Fraser (smfr) 2010-12-06 11:38:56 PST
Comment on attachment 75709 [details]
Patch (fix tabs in ChangeLog)

View in context: https://bugs.webkit.org/attachment.cgi?id=75709&action=review

> WebCore/ChangeLog:82
> +        Blocks now have a computeOverflow function called at the end that adds in all the types of overflow.  The addOverflowFromChildren

Called at the end of what?

> WebCore/ChangeLog:99
> +        (WebCore::RenderBlock::addOverhangingFloats):
> +        The propagation of float overflow has changed substantially.  The basic rules are:
> +            (1) The float must be in our floating objects list to contribute to overflow.
> +            (2) The float must be a descendant to contribute to overflow.
> +            (3) The block must have the outermost list that contains the float, or it has a self-painting layer and
> +                so the float needs to be included in its overflow.

Are these covered by layout tests?

> WebCore/rendering/RenderTreeAsText.cpp:621
> +    // FIXME: Apply overflow to the root layer to not break every test.  Complete hack.  Sigh.

Maybe file a bug on this and reference it in the comment?

> LayoutTests/ChangeLog:33
> +        Fix for https://bugs.webkit.org/show_bug.cgi?id=49220 <<rdar://problem/8644849>, REGRESSION: transforms now
> +        O(n^3) from pathological behavior in lowestPosition, rightmostPosition, leftmostPosition and topmostPosition.
> +
> +        This patch throws out the lowest/rightmost/leftmost/topmostPosition functions and re-architects layout overflow
> +        in the engine to cache all the information required to properly handle scrolling.
> +
> +        In the old code, there were two types of overflow: layout overflow and visual overflow.  The former could
> +        affect scrolling and the latter could not.  The distinction was largely meaningless, since layout overflow
> +        wasn't actually used to determine scroll width or scroll height.  It didn't propagate across self-painting layer
> +        boundaries either.  In the old code, the term visible overflow meant the union of the layout overflow and
> +        visual overflow rects.
> +
> +        In the new code, the two types of overflow remain, but the distinction between the two is now clear.  Visual overflow
> +        is used purely for painting and hit testing checks and layout overflow is used specifically for scrolling.  It has
> +        been expanded to propagate across self-painting layers, to factor in relative positioning and transforms, and to
> +        work with writing modes.
> +
> +        In order to minimize layout test changes, layers no longer incorporate right/bottom overflow into their width/height members.
> +        Doing so uncovered two bugs where left/top overflow was ignored (proof that even having layer dimensions is harmful).
> +        A render tree dump hack has been put into the code to keep this overflow dumping for the RenderView's layer, since otherwise
> +        a huge number of tests would change.
> +
> +        Added fast/overflow/overflow-rtl-vertical.html to test vertical writing-mode overflow.  Existing tests cover the rest.
> +
> +        * page/FrameView.cpp:
> +        (WebCore::FrameView::adjustViewSize):
> +        (WebCore::FrameView::forceLayoutForPagination):
> +        Changed to use RenderView's docTop/Left/Width/Height accessors, which simply grab the overflow and properly flip it
> +        to account for writing modes.

You can just describe the LayoutTests changes here.
Comment 19 Dave Hyatt 2010-12-06 11:43:18 PST
(In reply to comment #18)
w.  The addOverflowFromChildren
> 
> Called at the end of what?
> 

End of layout.  I fixed the comment.

> > WebCore/ChangeLog:99
> > +        (WebCore::RenderBlock::addOverhangingFloats):
> > +        The propagation of float overflow has changed substantially.  The basic rules are:
> > +            (1) The float must be in our floating objects list to contribute to overflow.
> > +            (2) The float must be a descendant to contribute to overflow.
> > +            (3) The block must have the outermost list that contains the float, or it has a self-painting layer and
> > +                so the float needs to be included in its overflow.
> 
> Are these covered by layout tests?
> 

Very well yes.  Visual overflow stays essentially the same and is tested by repaint tests. Layout overflow is tested by the root layer's scroll dimensions in the dumps.

> > WebCore/rendering/RenderTreeAsText.cpp:621
> > +    // FIXME: Apply overflow to the root layer to not break every test.  Complete hack.  Sigh.
> 
> Maybe file a bug on this and reference it in the comment?
> 

Yeah I'm going  to file a bug about just rebaselining the whole render tree and removing all of the FIXMEs.
des.
> 
> You can just describe the LayoutTests changes here.

Ok, snipped that out of the layout tests changelog.
Comment 20 Dave Hyatt 2010-12-06 12:10:59 PST
Fixed in r73885.
Comment 21 Eric Seidel (no email) 2010-12-13 02:07:30 PST
I think this broke fast/blockflow/broken-ideograph-small-caps.html on leopard.  It seems to have broken between about r73379 and 73390 and this seems to be the most likely commit.
Comment 22 Shinichiro Hamaji 2010-12-20 04:56:08 PST
I think this change caused Bug 51328.
Comment 23 Kenneth Rohde Christiansen 2011-03-03 03:56:12 PST
No'am this might be why Snowstack was so slow on our branch