RESOLVED FIXED 24201
WebCore::RenderBlock::layout taking superquadratic time
https://bugs.webkit.org/show_bug.cgi?id=24201
Summary WebCore::RenderBlock::layout taking superquadratic time
James Robinson
Reported 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
Attachments
reduction (takes ~2000ms to layout) (2.16 KB, text/html)
2009-02-26 09:21 PST, James Robinson
no flags
reduction (takes ~15s to layout) (2.23 KB, text/html)
2009-03-03 14:20 PST, James Robinson
no flags
Patch to fix bug (8.17 KB, patch)
2009-03-03 14:58 PST, Dave Hyatt
no flags
Patch to fix bug (47.54 KB, patch)
2009-03-03 16:08 PST, Dave Hyatt
mitz: review+
James Robinson
Comment 1 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
James Robinson
Comment 2 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.
Dave Hyatt
Comment 3 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).
Dave Hyatt
Comment 4 2009-03-03 15:43:47 PST
This patch fails 3 layout tests, so I will need to study those.
Dave Hyatt
Comment 5 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
Dave Hyatt
Comment 6 2009-03-03 15:57:45 PST
Looks like these test cases are failing on the buildbot, so this patch actually works.
Dave Hyatt
Comment 7 2009-03-03 16:08:43 PST
Created attachment 28244 [details] Patch to fix bug
Dave Hyatt
Comment 8 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).
mitz
Comment 9 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!
mitz
Comment 10 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.
James Robinson
Comment 11 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.
Dave Hyatt
Comment 12 2009-03-04 09:57:07 PST
Fixed in r41422.
Dave Hyatt
Comment 13 2009-03-04 10:17:08 PST
*** Bug 21469 has been marked as a duplicate of this bug. ***
Cameron Zwarich (cpst)
Comment 14 2009-03-21 21:35:09 PDT
*** Bug 23013 has been marked as a duplicate of this bug. ***
Note You need to log in before you can comment on or make changes to this bug.