Changeset 110992 in webkit


Ignore:
Timestamp:
Mar 16, 2012 5:31:57 AM (12 years ago)
Author:
haraken@chromium.org
Message:

[Performance] Optimize innerHTML and outerHTML
​https://bugs.webkit.org/show_bug.cgi?id=81214

Reviewed by Adam Barth.

This patch makes innerHTML and outerHTML 2.4 times faster.

Performance test: ​https://bugs.webkit.org/attachment.cgi?id=132034
The performance test measures body.innerHTML for 3000 lines of HTML,
which is copied from the HTML spec.

  • Chromium/Mac without the patch

div.innerHTML: 1658.6 ms
div.outerHTML: 4859.6 ms
body.innerHTML: 640.2 ms
body.outerHTML: 641.8 ms

  • Chromium/Mac with the patch

div.innerHTML: 751.0 ms
div.outerHTML: 2096.0 ms
body.innerHTML: 271.2 ms
body.outerHTML: 271.2 ms

  • Chromium/Linux without the patch

div.innerHTML: 950.4 ms
div.outerHTML: 2257.8 ms
body.innerHTML: 452.8 ms
body.outerHTML: 457.6 ms

  • Chromium/Linux with the patch

div.innerHTML: 582.4 ms
div.outerHTML: 1283.0 ms
body.innerHTML: 233.0 ms
body.outerHTML: 233.4 ms

  • AppleWebKit/Mac without the patch

div.innerHTML: 900.6 ms
div.outerHTML: 2245.2 ms
body.innerHTML: 462.6 ms
body.outerHTML: 468.0 ms

  • AppleWebKit/Mac with the patch

div.innerHTML: 529.8 ms
div.outerHTML: 1090.2 ms
body.innerHTML: 239.2 ms
body.outerHTML: 239.2 ms

This patch applies the following two optimizations:

(a) Remove redundant copies between Vector<String> and StringBuilders
in MarkupAccumulator::serializeNodes(), MarkupAccumulator::appendStartTag(),
and MarkupAccumulator::appendEndTag().

(Previous behavior)

  • Create a StringBuilder for each tag.
  • Append a created string in each StringBuilder to Vector<String>, parsing the DOM tree.
  • After the parsing, allocate a StringBuilder whose size is the sum of all Strings in Vector<String>.
  • Append all Strings in Vector<String> to the StringBuilder. (New behavior)
  • Allocate a StringBuilder with a default buffer size.
  • Append created strings to the StringBuilder, incrementally parsing the DOM tree.

(b) Optimize stringBuilder.append().

(b-1) Replace stringBuilder.append("A") with stringBuilder.append('A').

stringBuilder.append("A") requires to cast the characters to LChar*,
and then call strlen("A"). stringBuilder.append('A') is faster.

(b-2) Replace stringBuilder.append("AB") with stringBuilder.append('A')

and stringBuilder.append('B'). In my experiment, appending characters
one by one is faster than appending the characters at a breath if the
number of characters is less than 3.

(b-3) Hard-code a string length; i.e. replace stringBuilder.append("ABCDE")

with stringBuilder.append("ABCDE", 5). While the former requires to call
strlen("ABCDE"), the latter does not.

(a) improves performance by 170% ~ 200%. (b) improves performance by 30 ~ 40%.

Tests: fast/dom/Range/range-extract-contents.html

fast/dom/serialize-nodes.xhtml
fast/dom/XMLSerializer.html
and all other tests that use innerHTML or outerHTML.
No change in the test results.

  • editing/MarkupAccumulator.cpp:

(WebCore::MarkupAccumulator::serializeNodes):
(WebCore::MarkupAccumulator::appendString):
(WebCore::MarkupAccumulator::appendStartTag):
(WebCore::MarkupAccumulator::appendEndTag):
(WebCore::MarkupAccumulator::concatenateMarkup):
(WebCore::MarkupAccumulator::appendQuotedURLAttributeValue):
(WebCore::MarkupAccumulator::appendComment):
(WebCore::MarkupAccumulator::appendDocumentType):
(WebCore::MarkupAccumulator::appendProcessingInstruction):
(WebCore::MarkupAccumulator::appendOpenTag):
(WebCore::MarkupAccumulator::appendAttribute):
(WebCore::MarkupAccumulator::appendCDATASection):

  • editing/MarkupAccumulator.h:

(MarkupAccumulator):

Location:
trunk/Source/WebCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r110991 r110992  
     12012-03-16  Kentaro Hara  <haraken@chromium.org>
     2
     3        [Performance] Optimize innerHTML and outerHTML
     4        https://bugs.webkit.org/show_bug.cgi?id=81214
     5
     6        Reviewed by Adam Barth.
     7
     8        This patch makes innerHTML and outerHTML 2.4 times faster.
     9
     10        Performance test: https://bugs.webkit.org/attachment.cgi?id=132034
     11        The performance test measures body.innerHTML for 3000 lines of HTML,
     12        which is copied from the HTML spec.
     13
     14        - Chromium/Mac without the patch
     15        div.innerHTML: 1658.6 ms
     16        div.outerHTML: 4859.6 ms
     17        body.innerHTML: 640.2 ms
     18        body.outerHTML: 641.8 ms
     19
     20        - Chromium/Mac with the patch
     21        div.innerHTML:  751.0 ms
     22        div.outerHTML: 2096.0 ms
     23        body.innerHTML: 271.2 ms
     24        body.outerHTML: 271.2 ms
     25
     26        - Chromium/Linux without the patch
     27        div.innerHTML:  950.4 ms
     28        div.outerHTML: 2257.8 ms
     29        body.innerHTML: 452.8 ms
     30        body.outerHTML: 457.6 ms
     31
     32        - Chromium/Linux with the patch
     33        div.innerHTML:  582.4 ms
     34        div.outerHTML: 1283.0 ms
     35        body.innerHTML: 233.0 ms
     36        body.outerHTML: 233.4 ms
     37
     38        - AppleWebKit/Mac without the patch
     39        div.innerHTML:  900.6 ms
     40        div.outerHTML: 2245.2 ms
     41        body.innerHTML: 462.6 ms
     42        body.outerHTML: 468.0 ms
     43
     44        - AppleWebKit/Mac with the patch
     45        div.innerHTML:  529.8  ms
     46        div.outerHTML: 1090.2 ms
     47        body.innerHTML: 239.2 ms
     48        body.outerHTML: 239.2 ms
     49
     50        This patch applies the following two optimizations:
     51
     52        (a) Remove redundant copies between Vector<String> and StringBuilders
     53        in MarkupAccumulator::serializeNodes(), MarkupAccumulator::appendStartTag(),
     54        and MarkupAccumulator::appendEndTag().
     55
     56            (Previous behavior)
     57            - Create a StringBuilder for each tag.
     58            - Append a created string in each StringBuilder to Vector<String>,
     59              parsing the DOM tree.
     60            - After the parsing, allocate a StringBuilder whose size is the sum
     61              of all Strings in Vector<String>.
     62            - Append all Strings in Vector<String> to the StringBuilder.
     63            (New behavior)
     64            - Allocate a StringBuilder with a default buffer size.
     65            - Append created strings to the StringBuilder, incrementally parsing
     66              the DOM tree.
     67
     68        (b) Optimize stringBuilder.append().
     69            (b-1) Replace stringBuilder.append("A") with stringBuilder.append('A').
     70                  stringBuilder.append("A") requires to cast the characters to LChar*,
     71                  and then call strlen("A"). stringBuilder.append('A') is faster.
     72            (b-2) Replace stringBuilder.append("AB") with stringBuilder.append('A')
     73                  and stringBuilder.append('B'). In my experiment, appending characters
     74                  one by one is faster than appending the characters at a breath if the
     75                  number of characters is less than 3.
     76            (b-3) Hard-code a string length; i.e. replace stringBuilder.append("ABCDE")
     77                  with stringBuilder.append("ABCDE", 5). While the former requires to call
     78                  strlen("ABCDE"), the latter does not.
     79
     80        (a) improves performance by 170% ~ 200%. (b) improves performance by 30 ~ 40%.
     81
     82        Tests: fast/dom/Range/range-extract-contents.html
     83               fast/dom/serialize-nodes.xhtml
     84               fast/dom/XMLSerializer.html
     85               and all other tests that use innerHTML or outerHTML.
     86               No change in the test results.
     87
     88        * editing/MarkupAccumulator.cpp:
     89        (WebCore::MarkupAccumulator::serializeNodes):
     90        (WebCore::MarkupAccumulator::appendString):
     91        (WebCore::MarkupAccumulator::appendStartTag):
     92        (WebCore::MarkupAccumulator::appendEndTag):
     93        (WebCore::MarkupAccumulator::concatenateMarkup):
     94        (WebCore::MarkupAccumulator::appendQuotedURLAttributeValue):
     95        (WebCore::MarkupAccumulator::appendComment):
     96        (WebCore::MarkupAccumulator::appendDocumentType):
     97        (WebCore::MarkupAccumulator::appendProcessingInstruction):
     98        (WebCore::MarkupAccumulator::appendOpenTag):
     99        (WebCore::MarkupAccumulator::appendAttribute):
     100        (WebCore::MarkupAccumulator::appendCDATASection):
     101        * editing/MarkupAccumulator.h:
     102        (MarkupAccumulator):
     103
    11042012-03-16  Kihong Kwon  <kihong.kwon@samsung.com>
    2105

  • trunk/Source/WebCore/editing/MarkupAccumulator.cpp

    r110915 r110992  
    3838#include "ProcessingInstruction.h"
    3939#include "XMLNSNames.h"
    40 #include <wtf/text/StringBuilder.h>
    4140#include <wtf/unicode/CharacterNames.h>
    4241
    … …  
    8887String MarkupAccumulator::serializeNodes(Node* targetNode, Node* nodeToSkip, EChildrenOnly childrenOnly)
    8988{
    90     StringBuilder result;
    9189    serializeNodesWithNamespaces(targetNode, nodeToSkip, childrenOnly, 0);
    92     result.reserveCapacity(length());
    93     concatenateMarkup(result);
    94     return result.toString();
     90    return m_markup.toString();
    9591}
    9692
    … …  
    135131void MarkupAccumulator::appendString(const String& string)
    136132{
    137     m_succeedingMarkup.append(string);
     133    m_markup.append(string);
    138134}
    139135
    140136void MarkupAccumulator::appendStartTag(Node* node, Namespaces* namespaces)
    141137{
    142     StringBuilder markup;
    143     appendStartMarkup(markup, node, namespaces);
    144     appendString(markup.toString());
     138    appendStartMarkup(m_markup, node, namespaces);
    145139    if (m_nodes)
    146140        m_nodes->append(node);
    … …  
    149143void MarkupAccumulator::appendEndTag(Node* node)
    150144{
    151     StringBuilder markup;
    152     appendEndMarkup(markup, node);
    153     appendString(markup.toString());
     145    appendEndMarkup(m_markup, node);
    154146}
    155147
    … …  
    162154}
    163155
    164 // FIXME: This is a very inefficient way of accumulating the markup.
    165 // We're converting results of appendStartMarkup and appendEndMarkup from StringBuilder to String
    166 // and then back to StringBuilder and again to String here.
    167156void MarkupAccumulator::concatenateMarkup(StringBuilder& result)
    168157{
    169     for (size_t i = 0; i < m_succeedingMarkup.size(); ++i)
    170         result.append(m_succeedingMarkup[i]);
     158    result.append(m_markup);
    171159}
    172160
    … …  
    185173    ASSERT(element->isURLAttribute(const_cast<Attribute*>(&attribute)));
    186174    const String resolvedURLString = resolveURLIfNeeded(element, attribute.value());
    187     UChar quoteChar = '\"';
     175    UChar quoteChar = '"';
    188176    String strippedURLString = resolvedURLString.stripWhiteSpace();
    189177    if (protocolIsJavaScript(strippedURLString)) {
    … …  
    191179        if (strippedURLString.contains('"')) {
    192180            if (strippedURLString.contains('\''))
    193                 strippedURLString.replace('\"', "&quot;");
     181                strippedURLString.replace('"', "&quot;");
    194182            else
    195183                quoteChar = '\'';
    … …  
    302290{
    303291    // FIXME: Comment content is not escaped, but XMLSerializer (and possibly other callers) should raise an exception if it includes "-->".
    304     result.append("<!--");
     292    static const char commentBegin[] = "<!--";
     293    result.append(commentBegin, sizeof(commentBegin) - 1);
    305294    result.append(comment);
    306     result.append("-->");
     295    static const char commentEnd[] = "-->";
     296    result.append(commentEnd, sizeof(commentEnd) - 1);
    307297}
    308298
    … …  
    312302        return;
    313303
    314     result.append("<!DOCTYPE ");
     304    static const char doctypeString[] = "<!DOCTYPE ";
     305    result.append(doctypeString, sizeof(doctypeString) - 1);
    315306    result.append(n->name());
    316307    if (!n->publicId().isEmpty()) {
    317         result.append(" PUBLIC \"");
     308        static const char publicString[] = " PUBLIC \"";
     309        result.append(publicString, sizeof(publicString) - 1);
    318310        result.append(n->publicId());
    319         result.append("\"");
     311        result.append('"');
    320312        if (!n->systemId().isEmpty()) {
    321             result.append(" \"");
     313            result.append(' ');
     314            result.append('"');
    322315            result.append(n->systemId());
    323             result.append("\"");
     316            result.append('"');
    324317        }
    325318    } else if (!n->systemId().isEmpty()) {
    326         result.append(" SYSTEM \"");
     319        static const char systemString[] = " SYSTEM \"";
     320        result.append(systemString, sizeof(systemString) - 1);
    327321        result.append(n->systemId());
    328         result.append("\"");
     322        result.append('"');
    329323    }
    330324    if (!n->internalSubset().isEmpty()) {
    331         result.append(" [");
     325        result.append(' ');
     326        result.append('[');
    332327        result.append(n->internalSubset());
    333         result.append("]");
    334     }
    335     result.append(">");
     328        result.append(']');
     329    }
     330    result.append('>');
    336331}
    337332
    … …  
    339334{
    340335    // FIXME: PI data is not escaped, but XMLSerializer (and possibly other callers) this should raise an exception if it includes "?>".
    341     result.append("<?");
     336    result.append('<');
     337    result.append('?');
    342338    result.append(target);
    343     result.append(" ");
     339    result.append(' ');
    344340    result.append(data);
    345     result.append("?>");
     341    result.append('?');
     342    result.append('>');
    346343}
    347344
    … …  
    367364    result.append(element->nodeNamePreservingCase());
    368365    if (!element->document()->isHTMLDocument() && namespaces && shouldAddNamespaceElement(element))
    369         appendNamespace(result, element->prefix(), element->namespaceURI(), *namespaces);   
     366        appendNamespace(result, element->prefix(), element->namespaceURI(), *namespaces);
    370367}
    371368
    … …  
    396393        appendQuotedURLAttributeValue(result, element, attribute);
    397394    else {
    398         result.append('\"');
     395        result.append('"');
    399396        appendAttributeValue(result, attribute.value(), documentIsHTML);
    400         result.append('\"');
     397        result.append('"');
    401398    }
    402399
    … …  
    408405{
    409406    // FIXME: CDATA content is not escaped, but XMLSerializer (and possibly other callers) should raise an exception if it includes "]]>".
    410     result.append("<![CDATA[");
     407    static const char cdataBegin[] = "<![CDATA[";
     408    result.append(cdataBegin, sizeof(cdataBegin) - 1);
    411409    result.append(section);
    412     result.append("]]>");
     410    static const char cdataEnd[] = "]]>";
     411    result.append(cdataEnd, sizeof(cdataEnd) - 1);
    413412}
    414413

  • trunk/Source/WebCore/editing/MarkupAccumulator.h

    r110915 r110992  
    3131#include <wtf/HashMap.h>
    3232#include <wtf/Vector.h>
     33#include <wtf/text/StringBuilder.h>
    3334
    3435namespace WebCore {
    … …  
    7980    virtual void appendEndTag(Node*);
    8081    static size_t totalLength(const Vector<String>&);
    81     size_t length() const { return totalLength(m_succeedingMarkup); }
     82    size_t length() const { return m_markup.length(); }
    8283    void concatenateMarkup(StringBuilder&);
    8384    void appendAttributeValue(StringBuilder&, const String&, bool);
    … …  
    109110    void serializeNodesWithNamespaces(Node* targetNode, Node* nodeToSkip, EChildrenOnly, const Namespaces*);
    110111
    111     Vector<String> m_succeedingMarkup;
     112    StringBuilder m_markup;
    112113    const EAbsoluteURLs m_resolveURLsMethod;
    113114};
Note: See TracChangeset for help on using the changeset viewer.