Bug 13487

Created attachment 14178 [details] Cursory patch Implements the suggested optimization with some caveats: (1) only the root layer is optimized (2) subtree layout is disabled (3) SVG is not patched (4) some other RenderObject subclasses are not patched yet (5) it is not thoroughly tested (it passes existing repaint tests) (6) some code duplication. Before I address those I'd like to know if it's worth it. Perhaps someone with access to the PLT and/or interesting test cases would like to help.

Dave, can you check this with the nesting PLT?

(In reply to comment #2) > Dave, can you check this with the nesting PLT? > Hyatt mentioned on IRC a page that was "getting pwned by absolutePosition" and that computeAbsoluteRepaintRect was the "top offender for deeply nested inlines" (after applying some of his optimizations). I suppose it was in reference to non-cached pages, where image loading causes a ton of incremental relayout. In fact, for initial layout this patch may turn out to be bad, since it pushes state even if !checkForRepaint. Perhaps that can be avoided.

Your patch to RenderObject could be landed separately (the fixed position thing). By the way, my lazy minmaxwidth patch does fix the common O(n^2) problem with absoluteClippedOverflowRect (normal document construction) by making sure it does no work if inlines have no line boxes.

Created attachment 14194 [details] A test

Created attachment 14195 [details] Baseline test results

Created attachment 14196 [details] Test results after applying the patch

I don't know that the test is meaningful nor that the improvement is significant.

In unscientific Shark profiles of the test, absolutePositon and computeAbsoluteRepaintRect come up at the top in TOT with 11.6% and 10.2%, respectively. With the patch they are down to 0.4% and 0.6%, resp.

Here are the top offenders on the nesting PLT: 15% WebCore::RenderObject::containingBlock() const 11% WebCore::RenderFlow::dirtyLinesFromChangedChild(WebCore::RenderObject*) 11% WebCore::RenderObject::repaint(bool) 9% WebCore::RenderBox::computeAbsoluteRepaintRect(WebCore::IntRect&, bool) 4% WebCore::RenderBox::absolutePosition(int&, int&, bool) const Excluding containingBlock turns into: 15% WebCore::RenderObject::invalidateContainingBlockPrefWidths() Which breaks down into 10% appendChildNode and 5% removeChildNode. It's clear from that profile that this change to make these O(1) will be a win. I think I should probably fix invalidatePrefWidths to use container() so that intermediate inlines are not skipped, since not dirtying the inlines is introducing O(n^2) behavior into this method as inlines nest deeply.

Filed http://bugs.webkit.org/show_bug.cgi?id=13503 on the invalidateContainingBlockPrefWidths issue

OK, after the two fixes I landed today, computeAbsoluteRepaintRect and absolutePosition now dominate the nesting PLT (20% of the time). repaintObjectsBeforeLayout is 2%.

Created attachment 14215 [details] Patch r0.4 Moved LayoutState from the stack to the RenderArena and eliminated some duplicate code. (1)-(5) of comment #1 are mostly still not addressed.

Created attachment 14216 [details] Baseline test results for r21123 The baseline results are worse than before (attachment 14195 [details]). I suspect that's a result of removing the setLayout(false) from layoutBlockChildren in one of the recent revisions.

Created attachment 14217 [details] Test results after applying patch r0.4 to r21123 Shark shows absolutePosition and computeAbsoluteRepaintRect down from 11.4% and 9.9% to 0.5% and 0.5%.

Created attachment 14236 [details] Keep track of absolute translation and clip during layout No change log yet, but ready for review. No layout/pixel test regressions.

Comment on attachment 14236 [details] Keep track of absolute translation and clip during layout I don't think you need to add the boxLayer() method. The cost of layer() is completely negligible if you get the O(n^2) stuff out of the way. I know it looks like it mattered because I added that hasLayer() stuff recently, but it was really only showing up because it was being called a ludicrous number of times (and even then it was only like 1%).

I know it breaks encapsulation, but IMO you can just use m_layer directly if you want. That's what I do in other places. This isn't a situation where that's going to change anyway. :)

Created attachment 14243 [details] Keep track of absolute translation and clip during layout Includes change log, new test results (eliminated some excessive repainting) and one new test.

Comment on attachment 14243 [details] Keep track of absolute translation and clip during layout LayoutState should inherit from Noncopyable. + struct LayoutState* m_next; LayoutState is a class not a struct, but also, just LayoutState* should work here. + // Our layuot state is not valid for the repaints we are going to trigger by Typo, layuot. + bool layoutOnlyPositionedObjects(); The verb form is "layOut" and the noun form is "layout". I know that the layout() function violates this, but layOutAxis() respects it. I'm not sure others would agree with my take on this. + void offsetUnderRelPositionedInline(RenderObject*, int& x, int& y) const; I'm not completely comfortable with the verb use of offset here either. Ideally long-term something like this would return an IntSize that you would then add to your existing local IntPoint variable with +=. + // FIXME: Optimize using LayuotState and remove the disableLayoutState() call Typo here, LayuoutState. Given the paired nature of push/pop and disable/enable, perhaps we should use stack-based objects with destructors to ensure we don't forget to match them up. We could even make ones with features to cleanly deal with cases like the ones that currently have pushedLayoutState booleans. + void pushLayoutState(RenderBox* renderer, const IntSize& offset) { + if (m_layoutStateDisableCount || m_frameView->needsFullRepaint()) + return; + m_layoutState = new (renderArena()) LayoutState(m_layoutState, renderer, offset); + } I think we should put braces on separate lines for multiline functions, even ones that are inlines in a header. The style guidelines should say something about this if they don't already. I think Hyatt should review this too; I'm not sure I understand the optimization well enough.

(In reply to comment #20) > (From update of attachment 14243 [details] [edit]) > Typo, layuot. Oops :-) > + bool layoutOnlyPositionedObjects(); > > The verb form is "layOut" and the noun form is "layout". I know that the > layout() function violates this, but layOutAxis() respects it. I'm not sure > others would agree with my take on this. It's not just layout(), it's layoutBlock(), layoutPositionedObjects(), layout{Block,Inline}Children() and maybe a few others. I agree that layOut is better but I would prefer not to introduce apparent inconsistency with this patch, and perhaps rename all such functions in a separate rename-only patch. > + void offsetUnderRelPositionedInline(RenderObject*, int& x, int& y) const; > > I'm not completely comfortable with the verb use of offset here either. I'm not comfortable with the entire name. I think "under" can be confusing. > Ideally > long-term something like this would return an IntSize that you would then add > to your existing local IntPoint variable with +=. I might just change it to return IntSize. I'm trying to use IntSize and IntPoint in new code. I started writing this function to return an IntSize but then I realized that the three existing callers had separate ints and decided not to bother with it. > Typo here, LayuoutState. Oops again :-} > I think we should put braces on separate lines for multiline functions, even > ones that are inlines in a header. I agree. This was unintentional. (Comments that I didn't quote and reply to I'm going to address, or at least try to address).

While "lay out" is correct English for the verb form, I still don't think we should use "layOut" anywhere in our code base. We should fix the frame function name to be "layout" instead. I think we basically have an established "web engine" colloquialism that treats layout as a single-word verb, and it would create an annoying inconsistency if we had methods like "setNeedsLayout" vs. "layOut."

Comment on attachment 14243 [details] Keep track of absolute translation and clip during layout Please fix the LayuotState typos and then I can r+.

Created attachment 14265 [details] Keep track of absolute translation and clip during layout Changes from the previous patch: * renamed offsetUnderRelPositionedInline to offsetForPositionedInContainer and changed it return an IntSize. * Made LayoutState NonCopyable and removed the "struct" in the definition. * Fixed embarrassing typos! * Moved opening braces in multiline functions to a separate line.

Comment on attachment 14265 [details] Keep track of absolute translation and clip during layout r=me

Landed in r21183.