Bug 13487 - Implement O(1) absoluteClippedOverflowRect and absoluteOutlineBox during layout for a possible speed gain
Summary: Implement O(1) absoluteClippedOverflowRect and absoluteOutlineBox during layo...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 523.x (Safari 3)
Hardware: Macintosh OS X 10.4
: P3 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks: 13351
  Show dependency treegraph
 
Reported: 2007-04-25 11:06 PDT by mitz
Modified: 2007-04-29 13:29 PDT (History)
2 users (show)

See Also:


Attachments
Cursory patch (22.20 KB, patch)
2007-04-25 11:23 PDT, mitz
no flags Details | Formatted Diff | Diff
A test (1.56 KB, text/html)
2007-04-26 00:32 PDT, mitz
no flags Details
Baseline test results (136 bytes, text/plain)
2007-04-26 00:33 PDT, mitz
no flags Details
Test results after applying the patch (130 bytes, text/plain)
2007-04-26 00:33 PDT, mitz
no flags Details
Patch r0.4 (29.45 KB, patch)
2007-04-26 16:13 PDT, mitz
no flags Details | Formatted Diff | Diff
Baseline test results for r21123 (140 bytes, text/plain)
2007-04-26 16:17 PDT, mitz
no flags Details
Test results after applying patch r0.4 to r21123 (130 bytes, text/plain)
2007-04-26 16:20 PDT, mitz
no flags Details
Keep track of absolute translation and clip during layout (41.10 KB, patch)
2007-04-27 12:55 PDT, mitz
hyatt: review-
Details | Formatted Diff | Diff
Keep track of absolute translation and clip during layout (102.96 KB, patch)
2007-04-28 10:44 PDT, mitz
hyatt: review-
Details | Formatted Diff | Diff
Keep track of absolute translation and clip during layout (103.10 KB, patch)
2007-04-29 06:47 PDT, mitz
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description mitz 2007-04-25 11:06:04 PDT
When a block nested n levels deep needs relayout, O(n) implementations of absoluteClippedOverflowRect() and absoluteOutlineBox() are invoked by each of the ancestors, making for O(n^2) complexity.

By keeping track of absolute coordinates and clip on the stack during layout, it should be possible to implement absoluteClippedOverflowRect() and absoluteOutlineBox() in O(1) during layout.
Comment 1 mitz 2007-04-25 11:23:26 PDT
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.
Comment 2 Geoffrey Garen 2007-04-25 11:44:00 PDT
Dave, can you check this with the nesting PLT?
Comment 3 mitz 2007-04-25 11:54:53 PDT
(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.
Comment 4 Dave Hyatt 2007-04-25 12:15:30 PDT
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.
Comment 5 mitz 2007-04-26 00:32:08 PDT
Created attachment 14194 [details]
A test
Comment 6 mitz 2007-04-26 00:33:05 PDT
Created attachment 14195 [details]
Baseline test results
Comment 7 mitz 2007-04-26 00:33:48 PDT
Created attachment 14196 [details]
Test results after applying the patch
Comment 8 mitz 2007-04-26 00:35:31 PDT
I don't know that the test is meaningful nor that the improvement is significant.
Comment 9 mitz 2007-04-26 00:50:56 PDT
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.
Comment 10 Dave Hyatt 2007-04-26 10:43:37 PDT
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.
Comment 11 Dave Hyatt 2007-04-26 10:53:29 PDT
Filed

http://bugs.webkit.org/show_bug.cgi?id=13503

on the invalidateContainingBlockPrefWidths issue
Comment 12 Dave Hyatt 2007-04-26 12:55:26 PDT
OK, after the two fixes I landed today, computeAbsoluteRepaintRect and absolutePosition now dominate the nesting PLT (20% of the time).

repaintObjectsBeforeLayout is 2%.
Comment 13 mitz 2007-04-26 16:13:54 PDT
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.
Comment 14 mitz 2007-04-26 16:17:25 PDT
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.
Comment 15 mitz 2007-04-26 16:20:20 PDT
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%.
Comment 16 mitz 2007-04-27 12:55:43 PDT
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 17 Dave Hyatt 2007-04-27 14:22:57 PDT
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%).
Comment 18 Dave Hyatt 2007-04-27 14:24:14 PDT
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. :)

Comment 19 mitz 2007-04-28 10:44:21 PDT
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 20 Darin Adler 2007-04-28 13:50:15 PDT
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.
Comment 21 mitz 2007-04-28 14:36:14 PDT
(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).
Comment 22 Dave Hyatt 2007-04-28 21:03:33 PDT
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 23 Dave Hyatt 2007-04-28 21:11:11 PDT
Comment on attachment 14243 [details]
Keep track of absolute translation and clip during layout

Please fix the 

LayuotState

typos and then I can r+.
Comment 24 mitz 2007-04-29 06:47:40 PDT
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 25 Darin Adler 2007-04-29 07:34:30 PDT
Comment on attachment 14265 [details]
Keep track of absolute translation and clip during layout

r=me
Comment 26 Sam Weinig 2007-04-29 13:29:52 PDT
Landed in r21183.