• haraken@chromium.org's avatar
    Style recalculation takes too long when adding whitespace text nodes · e7b0b56c
    haraken@chromium.org authored
    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: http://svn.webkit.org/repository/webkit/trunk@144526 268f45cc-cd09-0410-ab3c-d52691b4dbfc
    e7b0b56c
Name
Last commit
Last update
..
accessibility-title-ui-element-expected.txt Loading commit data...
accessibility-title-ui-element.html Loading commit data...
adding-radio-buttons-expected.txt Loading commit data...
adding-radio-buttons.html Loading commit data...
append-text-nodes-without-renderers-expected.txt Loading commit data...
append-text-nodes-without-renderers.html Loading commit data...
array-binary-search-expected.txt Loading commit data...
array-binary-search.html Loading commit data...
array-nested-loop-expected.txt Loading commit data...
array-nested-loop.html Loading commit data...
array-push-pop-expected.txt Loading commit data...
array-push-pop.html Loading commit data...
array-reverse-expected.txt Loading commit data...
array-reverse.html Loading commit data...
class-list-remove-expected.txt Loading commit data...
class-list-remove.html Loading commit data...
clone-with-focus-expected.txt Loading commit data...
clone-with-focus.html Loading commit data...
document-contains-expected.txt Loading commit data...
document-contains.html Loading commit data...
htmlcollection-backwards-iteration-expected.txt Loading commit data...
htmlcollection-backwards-iteration.html Loading commit data...
htmlcollection-last-item-expected.txt Loading commit data...
htmlcollection-last-item.html Loading commit data...
mouse-event-expected.txt Loading commit data...
mouse-event.html Loading commit data...
nested-combined-selectors.html Loading commit data...
object-keys-expected.txt Loading commit data...
object-keys.html Loading commit data...
set-attribute-expected.txt Loading commit data...
set-attribute.html Loading commit data...
show-hide-table-rows-expected.txt Loading commit data...
show-hide-table-rows.html Loading commit data...
svg-path-appenditem-expected.txt Loading commit data...
svg-path-appenditem.html Loading commit data...
table-rows-length-caching-expected.txt Loading commit data...
table-rows-length-caching.html Loading commit data...
typing-at-end-of-line-expected.txt Loading commit data...
typing-at-end-of-line.html Loading commit data...