Style recalculation takes too long when adding whitespace text nodes
authorharaken@chromium.org <haraken@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 2 Mar 2013 05:18:43 +0000 (05:18 +0000)
committerharaken@chromium.org <haraken@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 2 Mar 2013 05:18:43 +0000 (05:18 +0000)
https://bugs.webkit.org/show_bug.cgi?id=110786

Reviewed by Darin Adler.

Source/WebCore:

// This takes 216 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.3 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().)

This patch adds a logic to bail out the loop to avoid the O(N^2) case.
Specifically, the patch bails out the loop if we encounter a text node
for which we again decided not to create a renderer. This bail out is
reasonable because the fact that we again decided not to create a renderer
for the text node indicates that there will be no affect of the result
of Text::textRendererIsNeeded() of the rest of the sibling nodes.

Performance test: https://bugs.webkit.org/attachment.cgi?id=190545
Performance result in Chromium/Linux: 25.3 sec => 48 msec !

Test: perf/append-text-nodes-without-renderers.html (for performance)
      fast/dynamic/create-renderer-for-whitespace-only-text.html (for correctness)

The loop was introduced in r29054. We have to make sure that
all layout tests that were updated in r29054 pass with this patch.
See http://trac.webkit.org/changeset/29054.

* dom/Node.cpp:
(WebCore::Node::attach):

LayoutTests:

* fast/html/details-nested-2-expected.txt: Sometimes anonymous blocks are left without
being cleaned up (for some reason). With this patch, one anonymouse block is removed at
the clean-up phase (for some reason). Anyway the new behavior is an expected behavior.
* platform/chromium-mac/fast/html/details-nested-2-expected.txt: Ditto.
* platform/chromium-win/fast/html/details-nested-2-expected.txt: Ditto.
* platform/efl/fast/html/details-nested-2-expected.txt: Ditto.
* platform/mac/fast/html/details-nested-2-expected.txt: Ditto.
* platform/qt/fast/html/details-nested-2-expected.txt: Ditto.
* perf/append-text-nodes-without-renderers-expected.txt: Added. For performance test.
* perf/append-text-nodes-without-renderers.html: Added. Ditto.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@144526 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/html/details-nested-2-expected.txt
LayoutTests/perf/append-text-nodes-without-renderers-expected.txt [new file with mode: 0644]
LayoutTests/perf/append-text-nodes-without-renderers.html [new file with mode: 0644]
LayoutTests/platform/chromium-mac/fast/html/details-nested-2-expected.txt
LayoutTests/platform/chromium-win/fast/html/details-nested-2-expected.txt
LayoutTests/platform/efl/fast/html/details-nested-2-expected.txt
LayoutTests/platform/mac/fast/html/details-nested-2-expected.txt
LayoutTests/platform/qt/fast/html/details-nested-2-expected.txt
Source/WebCore/ChangeLog
Source/WebCore/dom/Node.cpp

index 0449cbb..9d230ae 100644 (file)
@@ -1,3 +1,21 @@
+2013-03-01  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 Darin Adler.
+
+        * fast/html/details-nested-2-expected.txt: Sometimes anonymous blocks are left without
+        being cleaned up (for some reason). With this patch, one anonymouse block is removed at
+        the clean-up phase (for some reason). Anyway the new behavior is an expected behavior.
+        * platform/chromium-mac/fast/html/details-nested-2-expected.txt: Ditto.
+        * platform/chromium-win/fast/html/details-nested-2-expected.txt: Ditto.
+        * platform/efl/fast/html/details-nested-2-expected.txt: Ditto.
+        * platform/mac/fast/html/details-nested-2-expected.txt: Ditto.
+        * platform/qt/fast/html/details-nested-2-expected.txt: Ditto.
+        * perf/append-text-nodes-without-renderers-expected.txt: Added. For performance test.
+        * perf/append-text-nodes-without-renderers.html: Added. Ditto.
+
 2013-03-01  Jason Anderssen  <janderssen@gmail.com>
 
         Move markerTextForListItem from TestRunner to Internals
index 6faa110..afd2123 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 62x19
             text run at (24,8) width 4: " "
             text run at (28,8) width 58: "summary"
-        RenderBlock (anonymous) at (8,42) size 768x0
         RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,13) size 10x10: down
diff --git a/LayoutTests/perf/append-text-nodes-without-renderers-expected.txt b/LayoutTests/perf/append-text-nodes-without-renderers-expected.txt
new file mode 100644 (file)
index 0000000..5cb5ed4
--- /dev/null
@@ -0,0 +1,3 @@
+Tests that style recalculation time is linear when adding text nodes that do not have renderers. See https://bugs.webkit.org/show_bug.cgi?id=110786
+PASS
+
diff --git a/LayoutTests/perf/append-text-nodes-without-renderers.html b/LayoutTests/perf/append-text-nodes-without-renderers.html
new file mode 100644 (file)
index 0000000..b9e42a0
--- /dev/null
@@ -0,0 +1,23 @@
+<html>
+<body>
+<script src="../resources/magnitude-perf.js"></script>
+<script>
+function setupFunction(magnitude)
+{
+}
+
+function test(magnitude)
+{
+    for (var i = 0; i < magnitude; i++) {
+        document.body.appendChild(document.createTextNode(' '));
+        document.body.appendChild(document.createElement('div'));
+        document.body.appendChild(document.createTextNode(' '));
+    }
+    document.body.innerHTML = "";
+}
+
+Magnitude.description("Tests that style recalculation time is linear when adding text nodes that do not have renderers. See https://bugs.webkit.org/show_bug.cgi?id=110786");
+Magnitude.run(setupFunction, test, Magnitude.LINEAR);
+</script>
+</body>
+</html>
index c1fc47f..2b92b0b 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 63x18
             text run at (24,8) width 5: " "
             text run at (28,8) width 59: "summary"
-        RenderBlock (anonymous) at (8,42) size 768x0
         RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,12) size 11x11: down
index b336ed0..f682515 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 59x19
             text run at (24,8) width 5: " "
             text run at (28,8) width 55: "summary"
-        RenderBlock (anonymous) at (8,44) size 768x0
         RenderBlock {DETAILS} at (8,44) size 768x72 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x36 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,13) size 11x11: down
index 3c2bffc..de49293 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 63x17
             text run at (24,8) width 5: " "
             text run at (28,8) width 59: "summary"
-        RenderBlock (anonymous) at (8,42) size 768x0
         RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,12) size 11x11: down
index c1fc47f..2b92b0b 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 63x18
             text run at (24,8) width 5: " "
             text run at (28,8) width 59: "summary"
-        RenderBlock (anonymous) at (8,42) size 768x0
         RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,12) size 11x11: down
index 6d1dac2..f69c07e 100644 (file)
@@ -9,7 +9,6 @@ layer at (0,0) size 800x600
           RenderText {#text} at (24,8) size 58x19
             text run at (24,8) width 4: " "
             text run at (28,8) width 54: "summary"
-        RenderBlock (anonymous) at (8,43) size 768x0
         RenderBlock {DETAILS} at (8,43) size 768x70 [border: (8px solid #995555)]
           RenderBlock {SUMMARY} at (8,8) size 752x35 [border: (8px solid #CC9999)]
             RenderDetailsMarker {DIV} at (8,13) size 10x10: down
index 6fce734..2905082 100644 (file)
@@ -1,3 +1,48 @@
+2013-03-01  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 Darin Adler.
+
+        // This takes 216 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.3 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().)
+
+        This patch adds a logic to bail out the loop to avoid the O(N^2) case.
+        Specifically, the patch bails out the loop if we encounter a text node
+        for which we again decided not to create a renderer. This bail out is
+        reasonable because the fact that we again decided not to create a renderer
+        for the text node indicates that there will be no affect of the result
+        of Text::textRendererIsNeeded() of the rest of the sibling nodes.
+
+        Performance test: https://bugs.webkit.org/attachment.cgi?id=190545
+        Performance result in Chromium/Linux: 25.3 sec => 48 msec !
+
+        Test: perf/append-text-nodes-without-renderers.html (for performance)
+              fast/dynamic/create-renderer-for-whitespace-only-text.html (for correctness)
+
+        The loop was introduced in r29054. We have to make sure that
+        all layout tests that were updated in r29054 pass with this patch.
+        See http://trac.webkit.org/changeset/29054.
+
+        * dom/Node.cpp:
+        (WebCore::Node::attach):
+
 2013-03-01  Jason Anderssen  <janderssen@gmail.com>
 
         Moved markerTextForListItem from TestRunner to Internals
index e7c4650..1445a00 100644 (file)
@@ -1068,7 +1068,6 @@ 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()) {
@@ -1076,9 +1075,16 @@ void Node::attach()
             if (next->renderer())
                 break;
             if (!next->attached())
-                break;  // Assume this means none of the following siblings are attached.
-            if (next->isTextNode())
-                toText(next)->createTextRendererIfNeeded();
+                break; // Assume this means none of the following siblings are attached.
+            if (!next->isTextNode())
+                continue;
+            ASSERT(!next->renderer());
+            toText(next)->createTextRendererIfNeeded();
+            // If we again decided not to create a renderer for next, we can bail out the loop,
+            // because it won't affect the result of Text::textRendererIsNeeded() for the rest
+            // of sibling nodes.
+            if (!next->renderer())
+                break;
         }
     }