110786 – Style recalculation takes too long when adding whitespace text nodes

RESOLVED FIXED 110786

Style recalculation takes too long when adding whitespace text nodes

https://bugs.webkit.org/show_bug.cgi?id=110786

Summary Style recalculation takes too long when adding whitespace text nodes

Pete Blois

Reported 2013-02-25 13:01:29 PST

Created attachment 190110 [details] HTML repro file When a large number of whitespace text nodes are added to the document, interspersed with standard div elements, WebKit spends an excessive amount of time in 'Recalculate Style'. To reproduce, load the following HTML in a page: <!DOCTYPE html> <html> <body> <script> for (var i = 0; i < 1500; ++i) { document.body.appendChild(document.createTextNode(' ')); document.body.appendChild(document.createElement('div')); document.body.appendChild(document.createTextNode(' ')); } </script> </body> </html> Expected: Page loads in <300ms. Actual: Page loads in 20-30s, majority of time attributed by timeline to 'Recalculate Style'. Does not repro on FireFox and IE 9/10. Does not repro if any non-whitespace characters are added to the text nodes. Does not repro if spans of whitespace are inserted rather than text nodes. Also repros with document fragments: var fragment = document.createDocumentFragment(); fragment.appendChild(document.createTextNode(' ')); fragment.appendChild(document.createElement('div')); fragment.appendChild(document.createTextNode(' ')); for (var i = 0; i < 1500; ++i) { document.body.appendChild(fragment.cloneNode(true)); }

Attachments
HTML repro file (464 bytes, text/html) 2013-02-25 13:01 PST, Pete Blois	no flags	Details
Performance tests (476 bytes, text/html) 2013-02-27 09:47 PST, Kentaro Hara	no flags	Details
Patch (9.05 KB, patch) 2013-02-27 09:56 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Patch (8.27 KB, patch) 2013-02-27 10:46 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Patch (3.22 KB, patch) 2013-02-27 11:07 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Patch (7.71 KB, patch) 2013-02-28 10:15 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Patch (11.02 KB, patch) 2013-02-28 11:51 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Patch (7.20 KB, patch) 2013-03-01 18:30 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
patch for landing (11.94 KB, patch) 2013-03-01 21:17 PST, Kentaro Hara	no flags	Details Formatted Diff Diff
Show Obsolete (6) View All Add attachment proposed patch, testcase, etc.

Kentaro Hara

Comment 1 2013-02-25 18:00:23 PST

I profiled the benchmark and identified that the culprit is this FIXME: https://code.google.com/codesearch#OAMlx_jo-ck/src/third_party/WebKit/Source/WebCore/dom/Node.cpp&exact_package=chromium&q=node.cpp&type=cs&l=1065 Because an empty text does not have a renderer, we are hitting the O(n^2) case. I'll take a detailed look and consider how to address the issue.

Kentaro Hara

Comment 2 2013-02-25 18:26:00 PST

CC-ing rendering experts. eric: It looks like you added the FIXME comment. Do you have any idea of how to fix the issue?

Kentaro Hara

Comment 3 2013-02-27 09:47:39 PST

Created attachment 190545 [details] Performance tests

Kentaro Hara

Comment 4 2013-02-27 09:56:41 PST

Created attachment 190549 [details] Patch

Eric Seidel (no email)

Comment 5 2013-02-27 10:24:22 PST

Comment on attachment 190549 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=190549&action=review > Source/WebCore/dom/Node.cpp:-1071 > - // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached). Does this still apply? What about other nodes that we attach but intentionally don't have renderers (like display: none content) > Source/WebCore/dom/Node.cpp:1086 > + if (!toText(next)->createTextRendererIfNeeded()) > + next->setTextNodeIntentionallyWithoutRenderer(); I wonder if this should be done inside createTextRenderIfNeeded. It's a bit odd for that to have side-effects, but I worry there are other cases wher we'll need this call and fail to have it. > Source/WebCore/dom/Node.h:731 > + TextNodeIntentionallyWithoutRendererFlag = 1 << 27, Do we have enough space for this flag?

Kentaro Hara

Comment 6 2013-02-27 10:46:03 PST

Created attachment 190554 [details] Patch

Kentaro Hara

Comment 7 2013-02-27 10:46:32 PST

(In reply to comment #5) > (From update of attachment 190549 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=190549&action=review > > > Source/WebCore/dom/Node.cpp:-1071 > > - // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached). > > Does this still apply? What about other nodes that we attach but intentionally don't have renderers (like display: none content) Good point. The patch solves the problem for text nodes only. I restored and updated the FIXME. Also I renamed the flag to IntentionallyWithoutRenderer so that we can use it for other nodes as well. > > Source/WebCore/dom/Node.cpp:1086 > > + if (!toText(next)->createTextRendererIfNeeded()) > > + next->setTextNodeIntentionallyWithoutRenderer(); > > I wonder if this should be done inside createTextRenderIfNeeded. It's a bit odd for that to have side-effects, but I worry there are other cases wher we'll need this call and fail to have it. Fixed. > > Source/WebCore/dom/Node.h:731 > > + TextNodeIntentionallyWithoutRendererFlag = 1 << 27, > > Do we have enough space for this flag? Yes, we have 32 bit for flags.

Elliott Sprehn

Comment 8 2013-02-27 10:49:01 PST

Comment on attachment 190549 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=190549&action=review This patch doesn't look right. Why don't we bail out on the attached() check inside the loop? We should have finished attaching all the text nodes preventing this n^2 behavior. > Source/WebCore/dom/Node.cpp:1083 > + if (next->isTextNodeIntentionallyWithoutRenderer()) This doesn't look right. If you run into a text node that "intentionally" doesn't have a renderer you'll give up early when a later sibling may need one.

Elliott Sprehn

Comment 9 2013-02-27 10:50:38 PST

(In reply to comment #8) > (From update of attachment 190549 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=190549&action=review > > This patch doesn't look right. Why don't we bail out on the attached() check inside the loop? We should have finished attaching all the text nodes preventing this n^2 behavior. > Specifically, this bitfield doesn't seem needed. If you're attached() and renderer() is null, then you intentionally don't have a renderer.

Kentaro Hara

Comment 10 2013-02-27 10:54:01 PST

(In reply to comment #9) > > This patch doesn't look right. Why don't we bail out on the attached() check inside the loop? We should have finished attaching all the text nodes preventing this n^2 behavior. > > > > Specifically, this bitfield doesn't seem needed. If you're attached() and renderer() is null, then you intentionally don't have a renderer. Agreed. If attached() returns true, it means that we have already checked if a renderer should be created or not. So if attach() returns true and renderer() returns NULL, it means that we have already decided not to create a renderer. So we can bail out. Sounds reasonable. Will update the patch.

Kentaro Hara

Comment 11 2013-02-27 11:07:56 PST

Created attachment 190557 [details] Patch

Darin Adler

Comment 12 2013-02-27 11:19:04 PST

Comment on attachment 190557 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=190557&action=review The idea here seems basically right, but there is some kind of fundamental mistake. > Source/WebCore/dom/Node.cpp:1082 > if (next->renderer()) > break; > + // This means that we intentionally did not create a renderer for the node. > + if (next->attached() && !next->renderer()) > + break; > + // This means none of the following siblings are attached. > if (!next->attached()) > - break; // Assume this means none of the following siblings are attached. > + break; This can’t be right. It says: if (a) break; if (b && !a) break; if (!b) break; That’s the same as just: break; So what this patch does is remove the code entirely in a roundabout way. The createTextRendererIfNeeded function will never be called. Maybe that’s what we’re really learning. That this code is not needed! If so, we should be sure we examine test cases for why this code was originally added to confirm that.

Kentaro Hara

Comment 13 2013-02-27 11:29:27 PST

(In reply to comment #12) > This can’t be right. It says: > > if (a) > break; > if (b && !a) > break; > if (!b) > break; > > That’s the same as just: > > break; > > So what this patch does is remove the code entirely in a roundabout way. The createTextRendererIfNeeded function will never be called. > > Maybe that’s what we’re really learning. That this code is not needed! If so, we should be sure we examine test cases for why this code was originally added to confirm that. Great observation...! I think that 'if (!attached()) break' is not right and should be removed. Imagine the following case: parent(attached with renderer) -- child1(attached without renderer) When we try to insert child0 before child1, it can change the renderer of child1. So createTextRendererIfNeeded should be called for child1. mitz, eric, anttik: It looks like you've touched the code around it. Do you have any idea?

Eric Seidel (no email)

Comment 14 2013-02-27 12:17:40 PST

svn annotate is going to know better than my memory. :)

Kentaro Hara

Comment 15 2013-02-27 15:40:34 PST

Changes related to this patch: http://trac.webkit.org/changeset/29054 (The for loop was introduced) http://trac.webkit.org/changeset/80330 (The FIXME was added)

Kentaro Hara

Comment 16 2013-02-28 10:15:41 PST

Created attachment 190747 [details] Patch

Kentaro Hara

Comment 17 2013-02-28 10:18:09 PST

Darin: Thanks for review! I updated the patch. > we should be sure we examine test cases for why this code was originally added to confirm that. The for loop was introduced in r29054 five years ago. The test case is fast/dynamic/create-renderer-for-whitespace-only-text.html and other layout tests that was updated in r29054. I confirmed that these tests pass with my latest patch.

Build Bot

Comment 18 2013-02-28 10:57:01 PST

Comment on attachment 190747 [details] Patch Attachment 190747 [details] did not pass mac-ews (mac): Output: http://webkit-commit-queue.appspot.com/results/16675264 New failing tests: fast/html/details-nested-2.html

Build Bot

Comment 19 2013-02-28 11:09:22 PST

Comment on attachment 190747 [details] Patch Attachment 190747 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-commit-queue.appspot.com/results/16823369 New failing tests: fast/html/details-nested-2.html

WebKit Review Bot

Comment 20 2013-02-28 11:15:14 PST

Comment on attachment 190747 [details] Patch Attachment 190747 [details] did not pass chromium-ews (chromium-xvfb): Output: http://webkit-commit-queue.appspot.com/results/16801110 New failing tests: fast/html/details-nested-2.html

Elliott Sprehn

Comment 21 2013-02-28 11:49:09 PST

Comment on attachment 190747 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=190747&action=review Some of the failures look real, specifically fast/html/details-nested-2.html > Source/WebCore/dom/Node.cpp:1080 > + // At this point, next does not have a renderer. Just assert this :) ASSERT(!next->renderer())

Kentaro Hara

Comment 22 2013-02-28 11:51:15 PST

Created attachment 190773 [details] Patch

Kentaro Hara

Comment 23 2013-02-28 11:53:52 PST

(In reply to comment #21) > > Source/WebCore/dom/Node.cpp:1080 > > + // At this point, next does not have a renderer. > > Just assert this :) > > ASSERT(!next->renderer()) Done. > View in context: https://bugs.webkit.org/attachment.cgi?id=190747&action=review > > Some of the failures look real, specifically fast/html/details-nested-2.html I'm not sure if it is a real failure or not. One anonymous render block is removed with this patch. In the latest patch, I updated the test result for the time being. Maybe is it a wrong thing to do? - RenderBlock (anonymous) at (8,44) size 768x0

Elliott Sprehn

Comment 24 2013-02-28 11:58:37 PST

(In reply to comment #23) > (In reply to comment #21) > > > Source/WebCore/dom/Node.cpp:1080 > > > + // At this point, next does not have a renderer. > > > > Just assert this :) > > > > ASSERT(!next->renderer()) > > Done. > > > View in context: https://bugs.webkit.org/attachment.cgi?id=190747&action=review > > > > Some of the failures look real, specifically fast/html/details-nested-2.html > > I'm not sure if it is a real failure or not. One anonymous render block is removed with this patch. In the latest patch, I updated the test result for the time being. Maybe is it a wrong thing to do? > > - RenderBlock (anonymous) at (8,44) size 768x0 I think that's a real failure. You're not creating an anonymous block wrapper for some text now between the <summary> and the <details> that's right after it. In a real app this might cause two inline-block elements to suddenly run into each other: <div style="display: inline-block"></div>{ws} <div style="display: inline-block"></div> where {ws} is some whitespace. I think if you change the test to not be about <details> (which is magic) you'll see bugs.

Kentaro Hara

Comment 25 2013-02-28 13:45:21 PST

I discussed with Elliott and Morrita offline. - Removing the anonymous block is a right thing to do. The new test result is an expected behavior of details-nested-2.html. - So the question is why there had existed the anonymous block in trunk. According to morrita, redundant anonymous blocks can be sometimes left without being cleaned up. - I investigated the stack trace that creates the anonymous block, with my patch and without my patch. In both cases, the anonymous block is created inside Text::createTextRendererIfNeeded() (but in a different call path). Without my patch, the anonymous block is not cleaned up (for some reason). With my patch, the anonymous block is cleaned up (for some reason). [Without my patch] [0x7fd6f6945cb0] <unknown> [0x0000012eb771] WebCore::RenderBlock::addChildIgnoringAnonymousColumnBlocks() [0x0000006d8ffb] WebCore::NodeRenderingContext::createRendererForTextIfNeeded() [0x0000006fd4f7] WebCore::Text::createTextRendererIfNeeded() [0x0000006caefd] WebCore::Node::attach() [0x0000006bb41f] WebCore::Element::attach() [0x000000bc7d75] WebCore::InsertionPoint::attach() [0x0000006bb06e] WebCore::Element::recalcStyle() [0x000000725bbf] WebCore::ShadowRoot::recalcStyle() [0x00000071439a] WebCore::ElementShadow::recalcStyle() [0x0000006bac7e] WebCore::Element::recalcStyle() [0x0000006bad1c] WebCore::Element::recalcStyle() [0x0000006bad1c] WebCore::Element::recalcStyle() [0x000000696277] WebCore::Document::recalcStyle() [0x0000006969de] WebCore::Document::updateStyleIfNeeded() [0x000000696b04] WebCore::Document::finishedParsing() [With my patch] [0x0000012e8cb1] WebCore::RenderBlock::addChildIgnoringAnonymousColumnBlocks() [0x0000006d8774] WebCore::NodeRenderingContext::createRendererForTextIfNeeded() [0x0000006fcc88] WebCore::Text::createTextRendererIfNeeded() [0x0000006fcca9] WebCore::Text::attach() [0x000000bc70c5] WebCore::InsertionPoint::attach() [0x000000674d73] WebCore::ContainerNode::attach() [0x000000724e9e] WebCore::ShadowRoot::attach() [0x000000713a1e] WebCore::ElementShadow::attach() [0x0000006bab87] WebCore::Element::attach() [0x000000bc70c5] WebCore::InsertionPoint::attach() [0x0000006ba7de] WebCore::Element::recalcStyle() [0x00000072535f] WebCore::ShadowRoot::recalcStyle() [0x000000713b2a] WebCore::ElementShadow::recalcStyle() [0x0000006ba3ee] WebCore::Element::recalcStyle() [0x0000006ba48c] WebCore::Element::recalcStyle() [0x0000006ba48c] WebCore::Element::recalcStyle() [0x0000006959e7] WebCore::Document::recalcStyle() [0x00000069614e] WebCore::Document::updateStyleIfNeeded() [0x000000696274] WebCore::Document::finishedParsing()

Elliott Sprehn

Comment 26 2013-02-28 15:31:21 PST

(In reply to comment #25) > I discussed with Elliott and Morrita offline. > > - Removing the anonymous block is a right thing to do. The new test result is an expected behavior of details-nested-2.html. > > - So the question is why there had existed the anonymous block in trunk. According to morrita, redundant anonymous blocks can be sometimes left without being cleaned up. > Cool, thanks for investigating where this came from! LGTM on the patch.

Kentaro Hara

Comment 27 2013-02-28 15:33:41 PST

Darin: would you review?

Darin Adler

Comment 28 2013-03-01 18:10:06 PST

Comment on attachment 190773 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=190773&action=review The change to Node::attach seems fine, but I don’t think the other changes are needed. > Source/WebCore/dom/NodeRenderingContext.cpp:287 > +bool NodeRenderingContext::createRendererForTextIfNeeded() Why do we need this boolean return value? Why don’t callers just check if renderer() is 0?

Kentaro Hara

Comment 29 2013-03-01 18:30:11 PST

Created attachment 191086 [details] Patch

Kentaro Hara

Comment 30 2013-03-01 18:31:05 PST

(In reply to comment #28) > > Source/WebCore/dom/NodeRenderingContext.cpp:287 > > +bool NodeRenderingContext::createRendererForTextIfNeeded() > > Why do we need this boolean return value? Why don’t callers just check if renderer() is 0? Sounds reasonable. Updated the patch.

Darin Adler

Comment 31 2013-03-01 20:32:16 PST

Comment on attachment 191086 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=191086&action=review It would be better if this came with a test. The tests in LayoutTests/perf can be used to check for unwanted O(n^2) in a really nice clean way. I would love it if you’d add one of those tests. > Source/WebCore/dom/Node.cpp:1079 > + if (next->isTextNode()) { Might read nicer if this said: if (!next->isTextNode()) continue; Instead of nesting the rest of the loop inside an if.

Build Bot

Comment 32 2013-03-01 21:11:53 PST

Comment on attachment 191086 [details] Patch Attachment 191086 [details] did not pass mac-ews (mac): Output: http://webkit-commit-queue.appspot.com/results/16819620 New failing tests: editing/selection/selection-invalid-offset.html

Kentaro Hara

Comment 33 2013-03-01 21:17:33 PST

Created attachment 191094 [details] patch for landing

Kentaro Hara

Comment 34 2013-03-01 21:19:12 PST

(In reply to comment #31) > (From update of attachment 191086 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=191086&action=review > > It would be better if this came with a test. The tests in LayoutTests/perf can be used to check for unwanted O(n^2) in a really nice clean way. I would love it if you’d add one of those tests. Added perf/append-text-nodes-without-renderers.html. > > Source/WebCore/dom/Node.cpp:1079 > > + if (next->isTextNode()) { > > Might read nicer if this said: > > if (!next->isTextNode()) > continue; > > Instead of nesting the rest of the loop inside an if. Fixed. Thanks!

Kentaro Hara

Comment 35 2013-03-01 21:20:43 PST

Committed r144526: <http://trac.webkit.org/changeset/144526>

Note You need to log in before you can comment on or make changes to this bug.

Status RESOLVED

Resolution FIXED

Priority P2

Severity Normal

Classification Unclassified

Version 528+ (Nightly build)

Hardware All

OS All

Product WebKit

Component DOM

Assignee

Kentaro Hara

Reported

2013-02-25 13:01 PST

Modified

2013-03-01 21:20 PST History

CC List

20 users Show

URL

Keywords

Depends on

Blocks

buildbot
darin
dglazkov
ericbidelman
eric
esprehn+autocc
esprehn
haraken
hyatt
jchaffraix
kling
koivisto
mitz
morrita
ojan.autocc
ojan
paulirish
rniwa
syoichi
webkit.review.bot