Bug 49220 – REGRESSION: transform matrix applied too many times when nested

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Nico Weber]

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.

[Beth Dakin]

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)]

<rdar://problem/8644849>

[Simon Fraser (smfr)]

Lots of time in TransformationMatrix::multLeft()

[Mihai Parparita]

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)]

How does it behave if body has { overflow: hidden; } in your testcase?

[Mihai Parparita]

(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]

Created attachment 75038 [details]
Testcase (simplified)

[Simon Fraser (smfr)]

Right, we have some high-order perf issues here.

[Simon Fraser (smfr)]

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)]

Things are still very slow with a cached transformedFrameRect.

[Dave Hyatt]

Created attachment 75601 [details]
Work in progress.

[Dave Hyatt]

Created attachment 75604 [details]
Work in progress

Still working on passing everything but getting pretty close.

[Dave Hyatt]

Created attachment 75613 [details]
Work in progress

[Dave Hyatt]

Created attachment 75626 [details]
Work in progress

[Dave Hyatt]

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]

Created attachment 75708 [details]
Patch for review.

[Dave Hyatt]

Created attachment 75709 [details]
Patch (fix tabs in ChangeLog)

[Simon Fraser (smfr)]

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]

(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]

Fixed in r73885.

[Eric Seidel (no email)]

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]

I think this change caused Bug 51328.

[Kenneth Rohde Christiansen]

No'am this might be why Snowstack was so slow on our branch