Bug 24201

Summary:

WebCore::RenderBlock::layout taking superquadratic time

Product:

WebKit

Reporter:

James Robinson <jamesr>

Component:

Layout and Rendering

Assignee:

Dave Hyatt <hyatt>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

asbjorn, bksening, bugs, hyatt, mitz

Priority:

Version:

528+ (Nightly build)

Hardware:

OS:

All

URL:

http://compsci.ca/blog/if-a-programming-language-was-a-boat/

Attachments:

Description	Flags
reduction (takes ~2000ms to layout)	none
reduction (takes ~15s to layout)	none
Patch to fix bug	none
Patch to fix bug	mitz: review+

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	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
Show Obsolete (2) View All Add attachment proposed patch, testcase, etc.

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.