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)); }
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.
CC-ing rendering experts. eric: It looks like you added the FIXME comment. Do you have any idea of how to fix the issue?
Created attachment 190545 [details] Performance tests
Created attachment 190549 [details] Patch
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?
Created attachment 190554 [details] Patch
(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.
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.
(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.
(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.
Created attachment 190557 [details] Patch
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.
(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?
svn annotate is going to know better than my memory. :)
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)
Created attachment 190747 [details] Patch
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.
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
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
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
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())
Created attachment 190773 [details] Patch
(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
(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.
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()
(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.
Darin: would you review?
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?
Created attachment 191086 [details] Patch
(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.
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.
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
Created attachment 191094 [details] patch for landing
(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!
Committed r144526: <http://trac.webkit.org/changeset/144526>