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)
commit91411bb8e029cfd4e8b8582f3260dab5daf39c29
tree0717bb69d000d5acfafec8625e4b7d4d8768d5a6
parente924c49ae1555a7ef4fdd0087537e9a9ed140aba
Style recalculation takes too long when adding whitespace text nodes
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