Bug 49220 - REGRESSION: transform matrix applied too many times when nested
Summary: REGRESSION: transform matrix applied too many times when nested
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P1 Normal
Assignee: Dave Hyatt
URL: http://www.satine.org/research/webkit...
Keywords: InRadar
Depends on: 50970
Blocks: 50963
  Show dependency treegraph
 
Reported: 2010-11-08 16:12 PST by Nico Weber
Modified: 2011-03-03 03:56 PST (History)
9 users (show)

See Also:


Attachments
Testcase (7.20 KB, text/html)
2010-11-24 08:36 PST, Mihai Parparita
no flags Details
Testcase (simplified) (684 bytes, text/html)
2010-11-29 09:54 PST, Mihai Parparita
no flags Details
Work in progress. (109.27 KB, patch)
2010-12-03 23:09 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Work in progress (141.75 KB, patch)
2010-12-04 00:34 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Work in progress (142.22 KB, patch)
2010-12-04 12:21 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Work in progress (154.96 KB, patch)
2010-12-05 00:22 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch with updated test results (561.86 KB, patch)
2010-12-05 23:53 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch for review. (613.08 KB, patch)
2010-12-06 09:49 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch (fix tabs in ChangeLog) (614.41 KB, patch)
2010-12-06 10:09 PST, Dave Hyatt
simon.fraser: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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