Diff
Modified: trunk/LayoutTests/ChangeLog (144525 => 144526)
--- trunk/LayoutTests/ChangeLog 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/ChangeLog 2013-03-02 05:18:43 UTC (rev 144526)
@@ -1,3 +1,21 @@
+2013-03-01 Kentaro Hara <[email protected]>
+
+ 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 <[email protected]>
Move markerTextForListItem from TestRunner to Internals
Modified: trunk/LayoutTests/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Added: trunk/LayoutTests/perf/append-text-nodes-without-renderers-expected.txt (0 => 144526)
--- trunk/LayoutTests/perf/append-text-nodes-without-renderers-expected.txt (rev 0)
+++ trunk/LayoutTests/perf/append-text-nodes-without-renderers-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -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
+
Added: trunk/LayoutTests/perf/append-text-nodes-without-renderers.html (0 => 144526)
--- trunk/LayoutTests/perf/append-text-nodes-without-renderers.html (rev 0)
+++ trunk/LayoutTests/perf/append-text-nodes-without-renderers.html 2013-03-02 05:18:43 UTC (rev 144526)
@@ -0,0 +1,23 @@
+<html>
+<body>
+<script src=""
+<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>
Modified: trunk/LayoutTests/platform/chromium-mac/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/platform/chromium-mac/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/platform/chromium-mac/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Modified: trunk/LayoutTests/platform/chromium-win/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/platform/chromium-win/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/platform/chromium-win/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Modified: trunk/LayoutTests/platform/efl/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/platform/efl/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/platform/efl/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Modified: trunk/LayoutTests/platform/mac/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/platform/mac/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/platform/mac/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Modified: trunk/LayoutTests/platform/qt/fast/html/details-nested-2-expected.txt (144525 => 144526)
--- trunk/LayoutTests/platform/qt/fast/html/details-nested-2-expected.txt 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/LayoutTests/platform/qt/fast/html/details-nested-2-expected.txt 2013-03-02 05:18:43 UTC (rev 144526)
@@ -9,7 +9,6 @@
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
Modified: trunk/Source/WebCore/ChangeLog (144525 => 144526)
--- trunk/Source/WebCore/ChangeLog 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/Source/WebCore/ChangeLog 2013-03-02 05:18:43 UTC (rev 144526)
@@ -1,3 +1,48 @@
+2013-03-01 Kentaro Hara <[email protected]>
+
+ 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 <[email protected]>
Moved markerTextForListItem from TestRunner to Internals
Modified: trunk/Source/WebCore/dom/Node.cpp (144525 => 144526)
--- trunk/Source/WebCore/dom/Node.cpp 2013-03-02 05:17:53 UTC (rev 144525)
+++ trunk/Source/WebCore/dom/Node.cpp 2013-03-02 05:18:43 UTC (rev 144526)
@@ -1068,7 +1068,6 @@
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 @@
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;
}
}
