Attachment 190557 Details for Bug 110786 – Patch

[patch] Patch

bug-110786-20130227110409.patch (text/plain), 3.22 KB, created by Kentaro Hara on 2013-02-27 11:07:56 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Kentaro Hara

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

Size: 3.22 KB

patch

obsolete

>Subversion Revision: 144194
>diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
>index f1c072444e80446ae3bceb3892cb0204b0171b85..91037597e997d2d15b32a534052f87adf643d9dc 100644
>--- a/Source/WebCore/ChangeLog
>+++ b/Source/WebCore/ChangeLog
>@@ -1,3 +1,40 @@
>+2013-02-27  Kentaro Hara  <haraken@chromium.org>
>+
>+        Style recalculation takes too long when adding 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 we do not create renderers for empty text
>+        nodes and thus we are hitting the worst O(N^2) case in Node::attach().
>+        (See FIXME in Node::attach().)
>+
>+        We can kill the O(N^2) case by bailing out the loop when we encounter
>+        a node for which we intentionally did not create a renderer.
>+        We can check it with 'if (attached() && !renderer())', because
>+        'attached()' means that we have tried to create a renderer before
>+        and '!renderer()' means that we did not create a renderer then.
>+
>+        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):
>+
> 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..f8a64a2b17dfae2365f8df43d74d5cdbdc87c60c 100644
>--- a/Source/WebCore/dom/Node.cpp
>+++ b/Source/WebCore/dom/Node.cpp
>@@ -1068,15 +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.
>     if (renderer()) {
>         for (Node* next = nextSibling(); next; next = next->nextSibling()) {
>             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;
>             if (next->isTextNode())
>                 toText(next)->createTextRendererIfNeeded();
>         }

Actions: View | Formatted Diff | Diff

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