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+

Nico Weber
Reported 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.
Attachments
Testcase (7.20 KB, text/html)
2010-11-24 08:36 PST, Mihai Parparita
no flags
Testcase (simplified) (684 bytes, text/html)
2010-11-29 09:54 PST, Mihai Parparita
no flags
Work in progress. (109.27 KB, patch)
2010-12-03 23:09 PST, Dave Hyatt
no flags
Work in progress (141.75 KB, patch)
2010-12-04 00:34 PST, Dave Hyatt
no flags
Work in progress (142.22 KB, patch)
2010-12-04 12:21 PST, Dave Hyatt
no flags
Work in progress (154.96 KB, patch)
2010-12-05 00:22 PST, Dave Hyatt
no flags
Patch with updated test results (561.86 KB, patch)
2010-12-05 23:53 PST, Dave Hyatt
no flags
Patch for review. (613.08 KB, patch)
2010-12-06 09:49 PST, Dave Hyatt
no flags
Patch (fix tabs in ChangeLog) (614.41 KB, patch)
2010-12-06 10:09 PST, Dave Hyatt
simon.fraser: review+
Beth Dakin
Comment 1 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.
Simon Fraser (smfr)
Comment 2 2010-11-08 17:23:47 PST
Simon Fraser (smfr)
Comment 3 2010-11-08 17:25:41 PST
Lots of time in TransformationMatrix::multLeft()
Mihai Parparita
Comment 4 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).
Simon Fraser (smfr)
Comment 5 2010-11-26 10:34:41 PST
How does it behave if body has { overflow: hidden; } in your testcase?
Mihai Parparita
Comment 6 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.
Mihai Parparita
Comment 7 2010-11-29 09:54:44 PST
Created attachment 75038 [details] Testcase (simplified)
Simon Fraser (smfr)
Comment 8 2010-11-29 11:20:06 PST
Right, we have some high-order perf issues here.
Simon Fraser (smfr)
Comment 9 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.
Simon Fraser (smfr)
Comment 10 2010-11-29 15:45:12 PST
Things are still very slow with a cached transformedFrameRect.
Dave Hyatt
Comment 11 2010-12-03 23:09:33 PST
Created attachment 75601 [details] Work in progress.
Dave Hyatt
Comment 12 2010-12-04 00:34:03 PST
Created attachment 75604 [details] Work in progress Still working on passing everything but getting pretty close.
Dave Hyatt
Comment 13 2010-12-04 12:21:29 PST
Created attachment 75613 [details] Work in progress
Dave Hyatt
Comment 14 2010-12-05 00:22:56 PST
Created attachment 75626 [details] Work in progress
Dave Hyatt
Comment 15 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.
Dave Hyatt
Comment 16 2010-12-06 09:49:26 PST
Created attachment 75708 [details] Patch for review.
Dave Hyatt
Comment 17 2010-12-06 10:09:44 PST
Created attachment 75709 [details] Patch (fix tabs in ChangeLog)
Simon Fraser (smfr)
Comment 18 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.
Dave Hyatt
Comment 19 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.
Dave Hyatt
Comment 20 2010-12-06 12:10:59 PST
Fixed in r73885.
Eric Seidel (no email)
Comment 21 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.
Shinichiro Hamaji
Comment 22 2010-12-20 04:56:08 PST
I think this change caused Bug 51328.
Kenneth Rohde Christiansen
Comment 23 2011-03-03 03:56:12 PST
No'am this might be why Snowstack was so slow on our branch
Note You need to log in before you can comment on or make changes to this bug.