Attachment 190554 Details for Bug 110786 – Patch

[patch] Patch

bug-110786-20130227104217.patch (text/plain), 8.27 KB, created by Kentaro Hara on 2013-02-27 10:46:03 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Kentaro Hara

Created: 2013-02-27 10:46:03 PST

Size: 8.27 KB

patch

obsolete

>Subversion Revision: 144194
>diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
>index f1c072444e80446ae3bceb3892cb0204b0171b85..2aa4fbe518e66542261be78a16691c1d5c5f8b9b 100644
>--- a/Source/WebCore/ChangeLog
>+++ b/Source/WebCore/ChangeLog
>@@ -1,3 +1,57 @@
>+2013-02-27  Kentaro Hara  <haraken@chromium.org>
>+
>+        Performance issues adding large numbers of whitespace text nodes
>+        https://bugs.webkit.org/show_bug.cgi?id=110786
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        // This takes 98 msec.
>+        for (var i = 0; i < 1500; ++i) {
>+          document.body.appendChild(document.createTextNode('x'));
>+          document.body.appendChild(document.createElement('div'));
>+          document.body.appendChild(document.createTextNode('x'));
>+        }
>+
>+        // But this takes 25 seconds.
>+        for (var i = 0; i < 1500; ++i) {
>+          document.body.appendChild(document.createTextNode(' '));
>+          document.body.appendChild(document.createElement('div'));
>+          document.body.appendChild(document.createTextNode(' '));
>+        }
>+
>+        The reason is that because we do not create renderers for empty text
>+        nodes, we are hitting the worst O(N^2) case in Node::attach().
>+        (See the FIXME in Node::attach().)
>+
>+        To fix the issue, we need to distinguish the following two cases:
>+
>+          - we have not yet tried to create a renderer for the text node.
>+          - we have tried to create a renderer for the text node and
>+            decided not to create a renderer.
>+
>+        To distinguish the two situations, this patch adds an IntentionallyWithoutRenderer
>+        flag and uses the flag for text nodes. The patch reduces the worst-case
>+        loop cost from O(N^2) to O(N).
>+
>+        Performance tests: https://bugs.webkit.org/attachment.cgi?id=190545
>+        Results in Chromium/Linux: 25.3 sec => 98 msec
>+
>+        * dom/Node.cpp:
>+        (WebCore::Node::attach):
>+        (WebCore::Node::detach):
>+        * dom/Node.h:
>+        (WebCore::Node::isTextNodeIntentionallyWithoutRenderer):
>+        (WebCore::Node::setTextNodeIntentionallyWithoutRenderer):
>+        (WebCore::Node::clearTextNodeIntentionallyWithoutRenderer):
>+        * dom/NodeRenderingContext.cpp:
>+        (WebCore::NodeRenderingContext::createRendererForTextIfNeeded):
>+        * dom/NodeRenderingContext.h:
>+        (NodeRenderingContext):
>+        * dom/Text.cpp:
>+        (WebCore::Text::createTextRendererIfNeeded):
>+        * dom/Text.h:
>+        (Text):
>+
> 2013-02-25  Kentaro Hara  <haraken@chromium.org>
> 
>         [V8] Generate a wrapper function for ReplaceableAttrSetter()
>diff --git a/Source/WebCore/dom/Node.cpp b/Source/WebCore/dom/Node.cpp
>index e7c46501d219a1d48db8bb9cc0d30dca3d99ec34..fae113c74eb966997cdbbde1af53953bd453888b 100644
>--- a/Source/WebCore/dom/Node.cpp
>+++ b/Source/WebCore/dom/Node.cpp
>@@ -1068,12 +1068,18 @@ void Node::attach()
>     ASSERT(!attached());
>     ASSERT(!renderer() || (renderer()->style() && renderer()->parent()));
> 
>-    // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached).
>     // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the
>     // result of Text::textRendererIsNeeded() for those nodes.
>+    //
>+    // FIXME: Call setIntentionallyWithoutRenderer() for nodes for which
>+    // we have tried to create a renderer but decided not to create a
>+    // renderer (e.g. display:none content). Without the call, we will end
>+    // up running the loop O(N^2) times in a case where all of the children
>+    // are nodes without renderers. Currently we call setIntentionallyWithoutRenderer()
>+    // correctly only for text nodes.
>     if (renderer()) {
>         for (Node* next = nextSibling(); next; next = next->nextSibling()) {
>-            if (next->renderer())
>+            if (next->renderer() || next->isIntentionallyWithoutRenderer())
>                 break;
>             if (!next->attached())
>                 break;  // Assume this means none of the following siblings are attached.
>@@ -1109,6 +1115,7 @@ void Node::detach()
>     if (renderer())
>         renderer()->destroyAndCleanupAnonymousWrappers();
>     setRenderer(0);
>+    clearIntentionallyWithoutRenderer();
> 
>     Document* doc = document();
>     if (isUserActionElement()) {
>diff --git a/Source/WebCore/dom/Node.h b/Source/WebCore/dom/Node.h
>index a836bf06c706e04c3623171caa41b6cc7d01dfdd..edc9ed2d0f5053225b173f82f07f312093b646ab 100644
>--- a/Source/WebCore/dom/Node.h
>+++ b/Source/WebCore/dom/Node.h
>@@ -362,6 +362,9 @@ public:
>     void setHasName(bool f) { ASSERT(!isTextNode()); setFlag(f, HasNameOrIsEditingTextFlag); }
>     void setChildNeedsStyleRecalc() { setFlag(ChildNeedsStyleRecalcFlag); }
>     void clearChildNeedsStyleRecalc() { clearFlag(ChildNeedsStyleRecalcFlag); }
>+    bool isIntentionallyWithoutRenderer() const { return getFlag(IntentionallyWithoutRendererFlag); }
>+    void setIntentionallyWithoutRenderer() { setFlag(IntentionallyWithoutRendererFlag); }
>+    void clearIntentionallyWithoutRenderer() { clearFlag(IntentionallyWithoutRendererFlag); }
> 
>     void setNeedsStyleRecalc(StyleChangeType changeType = FullStyleChange);
>     void clearNeedsStyleRecalc() { m_nodeFlags &= ~StyleChangeMask; }
>@@ -725,6 +728,7 @@ private:
> #endif
>         NeedsShadowTreeWalkerFlag = 1 << 25,
>         IsInShadowTreeFlag = 1 << 26,
>+        IntentionallyWithoutRendererFlag = 1 << 27,
> 
>         DefaultNodeFlags = IsParsingChildrenFinishedFlag
>     };
>diff --git a/Source/WebCore/dom/NodeRenderingContext.cpp b/Source/WebCore/dom/NodeRenderingContext.cpp
>index bae51a74b8bb72b2c17b63ac72f659054cf95d07..0a32d95d371edcd7d35b5441e0a3feaab5e13e55 100644
>--- a/Source/WebCore/dom/NodeRenderingContext.cpp
>+++ b/Source/WebCore/dom/NodeRenderingContext.cpp
>@@ -284,14 +284,14 @@ void NodeRenderingContext::createRendererForElementIfNeeded()
>     parentRenderer->addChild(newRenderer, nextRenderer);
> }
> 
>-void NodeRenderingContext::createRendererForTextIfNeeded()
>+bool NodeRenderingContext::createRendererForTextIfNeeded()
> {
>     ASSERT(!m_node->renderer());
> 
>     Text* textNode = toText(m_node);
> 
>     if (!shouldCreateRenderer())
>-        return;
>+        return false;
> 
>     RenderObject* parentRenderer = this->parentRenderer();
>     ASSERT(parentRenderer);
>@@ -303,13 +303,14 @@ void NodeRenderingContext::createRendererForTextIfNeeded()
>         m_style = parentRenderer->style();
> 
>     if (!textNode->textRendererIsNeeded(*this))
>-        return;
>+        return false;
>+
>     RenderText* newRenderer = textNode->createTextRenderer(document->renderArena(), m_style.get());
>     if (!newRenderer)
>-        return;
>+        return true;
>     if (!parentRenderer->isChildAllowed(newRenderer, m_style.get())) {
>         newRenderer->destroy();
>-        return;
>+        return true;
>     }
> 
>     // Make sure the RenderObject already knows it is going to be added to a RenderFlowThread before we set the style
>@@ -321,6 +322,7 @@ void NodeRenderingContext::createRendererForTextIfNeeded()
>     // Parent takes care of the animations, no need to call setAnimatableStyle.
>     newRenderer->setStyle(m_style.release());
>     parentRenderer->addChild(newRenderer, nextRenderer);
>+    return true;
> }
> 
> }
>diff --git a/Source/WebCore/dom/NodeRenderingContext.h b/Source/WebCore/dom/NodeRenderingContext.h
>index c079776dc82082d4d5dff1595219855556fbd16b..e965d6acbf756b884c117485d0edf904c1ef68b8 100644
>--- a/Source/WebCore/dom/NodeRenderingContext.h
>+++ b/Source/WebCore/dom/NodeRenderingContext.h
>@@ -49,7 +49,7 @@ public:
>     NodeRenderingContext(Node*, RenderStyle*);
>     ~NodeRenderingContext();
> 
>-    void createRendererForTextIfNeeded();
>+    bool createRendererForTextIfNeeded();
>     void createRendererForElementIfNeeded();
> 
>     Node* node() const;
>diff --git a/Source/WebCore/dom/Text.cpp b/Source/WebCore/dom/Text.cpp
>index dbf35a45e3c13d7e458e4d761e7d2bffd5644b0e..0b2ece3047201b1a087a9079933307614dc93013 100644
>--- a/Source/WebCore/dom/Text.cpp
>+++ b/Source/WebCore/dom/Text.cpp
>@@ -260,7 +260,8 @@ static bool isSVGText(Text* text)
> 
> void Text::createTextRendererIfNeeded()
> {
>-    NodeRenderingContext(this).createRendererForTextIfNeeded();
>+    if (!NodeRenderingContext(this).createRendererForTextIfNeeded())
>+        setIntentionallyWithoutRenderer();
> }
> 
> RenderText* Text::createTextRenderer(RenderArena* arena, RenderStyle* style)

Actions: View | Formatted Diff | Diff

Attachments on bug 110786: 190110 | 190545 | 190549 | 190554 | 190557 | 190747 | 190773 | 191086 | 191094