WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
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
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.
Top of Page
Format For Printing
XML
Clone This Bug