Bug 24201 - WebCore::RenderBlock::layout taking superquadratic time
Summary: WebCore::RenderBlock::layout taking superquadratic time
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC All
: P2 Normal
Assignee: Dave Hyatt
URL: http://compsci.ca/blog/if-a-programmi...
Keywords:
: 21469 23013 (view as bug list)
Depends on:
Blocks:
 
Reported: 2009-02-26 09:20 PST by James Robinson
Modified: 2009-03-21 21:35 PDT (History)
5 users (show)

See Also:


Attachments
reduction (takes ~2000ms to layout) (2.16 KB, text/html)
2009-02-26 09:21 PST, James Robinson
no flags Details
reduction (takes ~15s to layout) (2.23 KB, text/html)
2009-03-03 14:20 PST, James Robinson
no flags Details
Patch to fix bug (8.17 KB, patch)
2009-03-03 14:58 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch to fix bug (47.54 KB, patch)
2009-03-03 16:08 PST, Dave Hyatt
mitz: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description James Robinson 2009-02-26 09:20:21 PST
The linked page essentially hangs WebKit (and thus Safari 4 beta and Chromium) indefinitely.  Profiling reveals that WebCore::RenderBlock::layout() and children are taking an extremely long time.  The dom looks like this:

<body>
 <ol>
  <li>
   <div style="float:left">
    <img height='64' width='64' />
   </div>
   <div style="clear:both;" />
  </li>
 </ol>
</body>

Replicate the <li> to see the growth in time.  Here's the layout time against # of <li>s on my machine:

# of <li>s | layout time (ms)
-----------+-----------------
 4         | 4
 6         | 11
 8         | 42
10         | 171
12         | 678
14         | 2712
16         | 176319
Comment 1 James Robinson 2009-02-26 09:21:31 PST
Created attachment 28018 [details]
reduction (takes ~2000ms to layout)

This testcase has 16 <li> nodes and takes about 2000ms to lay out on my machine.  It renders ~instantly on FF3.0
Comment 2 James Robinson 2009-03-03 14:20:52 PST
Created attachment 28239 [details]
reduction (takes ~15s to layout)

The dom structure is:

<div style="float:left">
  <img height='64' width='64'>
</div>
<div style="clear:both;">
  <div style="float:left">
    <img height='64' width='64'>
  </div>
  <div style="clear:both;">
    ... repeat

Nesting more deeply triggers exponential behavior.
Comment 3 Dave Hyatt 2009-03-03 14:58:20 PST
Created attachment 28241 [details]
Patch to fix bug

This patch changes our yPosEstimate when doing block layout to factor in clear.  It also gets rid of the early adjustment of the y-position of the child prior to clearing, thus saving a redundant layout delta application (and a redundant layout when a clear is just going to happen anyway later).
Comment 4 Dave Hyatt 2009-03-03 15:43:47 PST
This patch fails 3 layout tests, so I will need to study those.

Comment 5 Dave Hyatt 2009-03-03 15:50:22 PST
The following tests fail:

fast/block/float/t0905-c414-flt-fit-01-d-g.html
fast/block/float/t0905-c5525-fltblck-00-d-ag.html
fast/block/float/t0905-c5526-flthw-00-c-g.html

Comment 6 Dave Hyatt 2009-03-03 15:57:45 PST
Looks like these test cases are failing on the buildbot, so this patch actually works.
Comment 7 Dave Hyatt 2009-03-03 16:08:43 PST
Created attachment 28244 [details]
Patch to fix bug
Comment 8 Dave Hyatt 2009-03-03 16:10:08 PST
Note, the bug reporter will probably want to file a followup about the fact that the page renders incorrectly (because of </li> not closing up the inner divs).
Comment 9 mitz 2009-03-03 21:19:42 PST
Comment on attachment 28244 [details]
Patch to fix bug

Wow. You're leaving me no choice but to pick nits:

> +            if (child->shrinkToAvoidFloats())
> +                // The child's width depends on the line width.
> +                // When the child shifts to clear an item, its width can
> +                // change (because it has more available line width).
> +                // So go ahead and mark the item as dirty.
> +                child->setChildNeedsLayout(true, false);

Need braces around this multi-line if block.

> +        Test case for https://bugs.webkit.org/attachment.cgi?id=28239

Should link to the bug, not to the attachment.

r=me!
Comment 10 mitz 2009-03-03 21:21:55 PST
(In reply to comment #8)
> Note, the bug reporter will probably want to file a followup about the fact
> that the page renders incorrectly (because of </li> not closing up the inner
> divs).

I think that's bug 14939. And I think bug 21469 may be a duplicate of this bug.
Comment 11 James Robinson 2009-03-04 08:59:24 PST
(In reply to comment #10)
> (In reply to comment #8)
> > Note, the bug reporter will probably want to file a followup about the fact
> > that the page renders incorrectly (because of </li> not closing up the inner
> > divs).
> 
> I think that's bug 14939. And I think bug 21469 may be a duplicate of this bug.
> 

I filed 24338 for the </li> not closing inner divs issue along with </dd> and </dt>.  Bug 14939 is a less-specific duplicate.

Bug 21469 is a duplicate of this bug.
Comment 12 Dave Hyatt 2009-03-04 09:57:07 PST
Fixed in r41422.

Comment 13 Dave Hyatt 2009-03-04 10:17:08 PST
*** Bug 21469 has been marked as a duplicate of this bug. ***
Comment 14 Cameron Zwarich (cpst) 2009-03-21 21:35:09 PDT
*** Bug 23013 has been marked as a duplicate of this bug. ***