Changeset 144526 in webkit


Ignore:
Timestamp:
Mar 1, 2013 9:18:43 PM (11 years ago)
Author:
haraken@chromium.org
Message:

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(N2) case in Node::attach().
(See FIXME in Node::attach().)

This patch adds a logic to bail out the loop to avoid the O(N2) 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.
Location:
trunk
Files:
2 added
9 edited

Legend:

Unmodified
Added
Removed
  • trunk/LayoutTests/ChangeLog

    r144524 r144526  
     12013-03-01  Kentaro Hara  <haraken@chromium.org>
     2
     3        Style recalculation takes too long when adding whitespace text nodes
     4        https://bugs.webkit.org/show_bug.cgi?id=110786
     5
     6        Reviewed by Darin Adler.
     7
     8        * fast/html/details-nested-2-expected.txt: Sometimes anonymous blocks are left without
     9        being cleaned up (for some reason). With this patch, one anonymouse block is removed at
     10        the clean-up phase (for some reason). Anyway the new behavior is an expected behavior.
     11        * platform/chromium-mac/fast/html/details-nested-2-expected.txt: Ditto.
     12        * platform/chromium-win/fast/html/details-nested-2-expected.txt: Ditto.
     13        * platform/efl/fast/html/details-nested-2-expected.txt: Ditto.
     14        * platform/mac/fast/html/details-nested-2-expected.txt: Ditto.
     15        * platform/qt/fast/html/details-nested-2-expected.txt: Ditto.
     16        * perf/append-text-nodes-without-renderers-expected.txt: Added. For performance test.
     17        * perf/append-text-nodes-without-renderers.html: Added. Ditto.
     18
    1192013-03-01  Jason Anderssen  <janderssen@gmail.com>
    220
  • trunk/LayoutTests/fast/html/details-nested-2-expected.txt

    r126923 r144526  
    1010            text run at (24,8) width 4: " "
    1111            text run at (28,8) width 58: "summary"
    12         RenderBlock (anonymous) at (8,42) size 768x0
    1312        RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
  • trunk/LayoutTests/platform/chromium-mac/fast/html/details-nested-2-expected.txt

    r132121 r144526  
    1010            text run at (24,8) width 5: " "
    1111            text run at (28,8) width 59: "summary"
    12         RenderBlock (anonymous) at (8,42) size 768x0
    1312        RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
  • trunk/LayoutTests/platform/chromium-win/fast/html/details-nested-2-expected.txt

    r132135 r144526  
    1010            text run at (24,8) width 5: " "
    1111            text run at (28,8) width 55: "summary"
    12         RenderBlock (anonymous) at (8,44) size 768x0
    1312        RenderBlock {DETAILS} at (8,44) size 768x72 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x36 [border: (8px solid #CC9999)]
  • trunk/LayoutTests/platform/efl/fast/html/details-nested-2-expected.txt

    r140250 r144526  
    1010            text run at (24,8) width 5: " "
    1111            text run at (28,8) width 59: "summary"
    12         RenderBlock (anonymous) at (8,42) size 768x0
    1312        RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
  • trunk/LayoutTests/platform/mac/fast/html/details-nested-2-expected.txt

    r133351 r144526  
    1010            text run at (24,8) width 5: " "
    1111            text run at (28,8) width 59: "summary"
    12         RenderBlock (anonymous) at (8,42) size 768x0
    1312        RenderBlock {DETAILS} at (8,42) size 768x68 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x34 [border: (8px solid #CC9999)]
  • trunk/LayoutTests/platform/qt/fast/html/details-nested-2-expected.txt

    r126849 r144526  
    1010            text run at (24,8) width 4: " "
    1111            text run at (28,8) width 54: "summary"
    12         RenderBlock (anonymous) at (8,43) size 768x0
    1312        RenderBlock {DETAILS} at (8,43) size 768x70 [border: (8px solid #995555)]
    1413          RenderBlock {SUMMARY} at (8,8) size 752x35 [border: (8px solid #CC9999)]
  • trunk/Source/WebCore/ChangeLog

    r144524 r144526  
     12013-03-01  Kentaro Hara  <haraken@chromium.org>
     2
     3        Style recalculation takes too long when adding whitespace text nodes
     4        https://bugs.webkit.org/show_bug.cgi?id=110786
     5
     6        Reviewed by Darin Adler.
     7
     8        // This takes 216 msec.
     9        for (var i = 0; i < 1500; ++i) {
     10          document.body.appendChild(document.createTextNode('x'));
     11          document.body.appendChild(document.createElement('div'));
     12          document.body.appendChild(document.createTextNode('x'));
     13        }
     14
     15        // But this takes 25.3 seconds.
     16        for (var i = 0; i < 1500; ++i) {
     17          document.body.appendChild(document.createTextNode(' '));
     18          document.body.appendChild(document.createElement('div'));
     19          document.body.appendChild(document.createTextNode(' '));
     20        }
     21
     22        The reason is that we do not create renderers for empty text
     23        nodes and thus we are hitting the worst O(N^2) case in Node::attach().
     24        (See FIXME in Node::attach().)
     25
     26        This patch adds a logic to bail out the loop to avoid the O(N^2) case.
     27        Specifically, the patch bails out the loop if we encounter a text node
     28        for which we again decided not to create a renderer. This bail out is
     29        reasonable because the fact that we again decided not to create a renderer
     30        for the text node indicates that there will be no affect of the result
     31        of Text::textRendererIsNeeded() of the rest of the sibling nodes.
     32
     33        Performance test: https://bugs.webkit.org/attachment.cgi?id=190545
     34        Performance result in Chromium/Linux: 25.3 sec => 48 msec !
     35
     36        Test: perf/append-text-nodes-without-renderers.html (for performance)
     37              fast/dynamic/create-renderer-for-whitespace-only-text.html (for correctness)
     38
     39        The loop was introduced in r29054. We have to make sure that
     40        all layout tests that were updated in r29054 pass with this patch.
     41        See http://trac.webkit.org/changeset/29054.
     42
     43        * dom/Node.cpp:
     44        (WebCore::Node::attach):
     45
    1462013-03-01  Jason Anderssen  <janderssen@gmail.com>
    247
  • trunk/Source/WebCore/dom/Node.cpp

    r143940 r144526  
    10691069    ASSERT(!renderer() || (renderer()->style() && renderer()->parent()));
    10701070
    1071     // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached).
    10721071    // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the
    10731072    // result of Text::textRendererIsNeeded() for those nodes.
     
    10771076                break;
    10781077            if (!next->attached())
    1079                 break;  // Assume this means none of the following siblings are attached.
    1080             if (next->isTextNode())
    1081                 toText(next)->createTextRendererIfNeeded();
     1078                break; // Assume this means none of the following siblings are attached.
     1079            if (!next->isTextNode())
     1080                continue;
     1081            ASSERT(!next->renderer());
     1082            toText(next)->createTextRendererIfNeeded();
     1083            // If we again decided not to create a renderer for next, we can bail out the loop,
     1084            // because it won't affect the result of Text::textRendererIsNeeded() for the rest
     1085            // of sibling nodes.
     1086            if (!next->renderer())
     1087                break;
    10821088        }
    10831089    }
Note: See TracChangeset for help on using the changeset viewer.