2011-01-28 Eric Seidel <eric@webkit.org>
authoreric@webkit.org <eric@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 29 Jan 2011 07:37:58 +0000 (07:37 +0000)
committereric@webkit.org <eric@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 29 Jan 2011 07:37:58 +0000 (07:37 +0000)
        Reviewed by Darin Adler.

        HTML5 TreeBuilder regressed a Peacekeeper DOM test by 40%
        https://bugs.webkit.org/show_bug.cgi?id=48719

        It's unclear exactly what the Peacekeeper benchmark is testing,
        because I haven't found a way to run it myself.

        However, I constructed a benchmark which shows at least one possible slow point.
        The HTML5 spec talks about creating a new document for every time we use
        the fragment parsing algorithm.  Document() it turns out, it a huge bloated
        mess, and the constructor and destructor do a huge amount of work.
        To avoid constructing (or destructing) documents for each innerHTML call,
        this patch adds a shared dummy document used by all innerHTML calls.

        * benchmarks/parser/tiny-innerHTML.html: Added.
2011-01-28  Eric Seidel  <eric@webkit.org>

        Reviewed by Darin Adler.

        HTML5 TreeBuilder regressed a Peacekeeper DOM test by 40%
        https://bugs.webkit.org/show_bug.cgi?id=48719

        It's unclear exactly what the Peacekeeper benchmark is testing,
        because I haven't found a way to run it myself.

        However, I constructed a benchmark which shows at least one possible slow point.
        The HTML5 spec talks about creating a new document for every time we use
        the fragment parsing algorithm.  Document() it turns out, it a huge bloated
        mess, and the constructor and destructor do a huge amount of work.
        To avoid constructing (or destructing) documents for each innerHTML call,
        this patch adds a shared dummy document used by all innerHTML calls.

        This patch brings us from 7x slower than Safari 5 on tiny-innerHTML
        to only 1.5x slower than Safari 5.  I'm sure there is more work to do here.

        Saving a shared Document like this is error prone.  Currently
        DummyDocumentFactory::releaseDocument() calls removeAllChildren()
        in an attempt to clear the Document's state. However it's possible
        that that call is not sufficient and we'll have future bugs here.

        * html/parser/HTMLTreeBuilder.cpp:
        (WebCore::DummyDocumentFactory::createDummyDocument):
        (WebCore::DummyDocumentFactory::releaseDocument):
        (WebCore::HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext):
        (WebCore::HTMLTreeBuilder::FragmentParsingContext::document):
        (WebCore::HTMLTreeBuilder::FragmentParsingContext::finished):
        * html/parser/HTMLTreeBuilder.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@77050 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/Parser/ChangeLog
PerformanceTests/Parser/resources/performance-test.js [new file with mode: 0644]
PerformanceTests/Parser/tiny-innerHTML.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/html/parser/HTMLTreeBuilder.cpp
Source/WebCore/html/parser/HTMLTreeBuilder.h

index 37a9f2e..4c927de 100644 (file)
@@ -1,3 +1,22 @@
+2011-01-28  Eric Seidel  <eric@webkit.org>
+
+        Reviewed by Darin Adler.
+
+        HTML5 TreeBuilder regressed a Peacekeeper DOM test by 40%
+        https://bugs.webkit.org/show_bug.cgi?id=48719
+
+        It's unclear exactly what the Peacekeeper benchmark is testing,
+        because I haven't found a way to run it myself.
+
+        However, I constructed a benchmark which shows at least one possible slow point.
+        The HTML5 spec talks about creating a new document for every time we use
+        the fragment parsing algorithm.  Document() it turns out, it a huge bloated
+        mess, and the constructor and destructor do a huge amount of work.
+        To avoid constructing (or destructing) documents for each innerHTML call,
+        this patch adds a shared dummy document used by all innerHTML calls.
+
+        * benchmarks/parser/tiny-innerHTML.html: Added.
+
 2010-12-31  Adam Barth  <abarth@webkit.org>
 
         Rubber-stamped by Eric Seidel.
diff --git a/PerformanceTests/Parser/resources/performance-test.js b/PerformanceTests/Parser/resources/performance-test.js
new file mode 100644 (file)
index 0000000..448feb1
--- /dev/null
@@ -0,0 +1,76 @@
+// A basic performance testing harness.
+
+function loadFile(path) {
+    var xhr = new XMLHttpRequest();
+    xhr.open("GET", path, false);
+    xhr.send(null);
+    return xhr.responseText;
+}
+
+var logDiv;
+
+function setupLogging() {
+    logDiv = document.createElement("pre");
+    document.body.appendChild(logDiv);
+}
+
+function log(text) {
+    logDiv.innerText += text + "\n";
+    window.scrollTo(document.body.height);
+}
+
+// FIXME: We should make it possible to configure runCount.
+var runCount = 20;
+var completedRuns = -1; // Discard the any runs < 0.
+var times = [];
+
+function computeAverage(values) {
+    var sum = 0;
+    for (var i = 0; i < values.length; i++)
+        sum += values[i];
+    return sum / values.length;
+}
+
+function computeStdev(values) {
+    var average = computeAverage(values);
+    var sumOfSquaredDeviations = 0;
+    for (var i = 0; i < values.length; ++i) {
+        var deviation = values[i] - average;
+        sumOfSquaredDeviations += deviation * deviation;
+    }
+    return Math.sqrt(sumOfSquaredDeviations / values.length);
+}
+
+function logStatistics(times) {
+    log("");
+    log("avg " + computeAverage(times));
+    log("stdev " + computeStdev(times));
+}
+
+var testFunction;
+
+function runPerformanceTest(testFunction) {
+    setupLogging()
+
+    log("Running " + runCount + " times");
+    window.testFunction = testFunction;
+    runOneTest();
+}
+
+function runOneTest() {
+    var start = new Date();
+    window.testFunction();
+    var time = new Date() - start;
+    completedRuns++;
+    if (completedRuns <= 0) {
+        log("Ignoring warm-up run (" + time + ")");
+    } else {
+        times.push(time);
+        log(time);
+    }
+    if (completedRuns < runCount) {
+        window.setTimeout(runOneTest, 0);
+    } else {
+        logStatistics(times);
+    }
+}
diff --git a/PerformanceTests/Parser/tiny-innerHTML.html b/PerformanceTests/Parser/tiny-innerHTML.html
new file mode 100644 (file)
index 0000000..b357cf1
--- /dev/null
@@ -0,0 +1,16 @@
+<!DOCTYPE html>
+<body>
+<pre id="log"></pre>
+<script src="resources/runner.js"></script>
+<script>
+start(20, function() {
+    var testDiv = document.createElement("div");
+    testDiv.style.display = "none";
+    document.body.appendChild(testDiv);
+    for (var x = 0; x < 100000; x++) {
+        testDiv.innerHTML = "This is a tiny HTML document";
+    }
+    document.body.removeChild(testDiv);
+});
+</script>
+</body>
index 0876d22..f4a60de 100644 (file)
@@ -1,3 +1,36 @@
+2011-01-28  Eric Seidel  <eric@webkit.org>
+
+        Reviewed by Darin Adler.
+
+        HTML5 TreeBuilder regressed a Peacekeeper DOM test by 40%
+        https://bugs.webkit.org/show_bug.cgi?id=48719
+
+        It's unclear exactly what the Peacekeeper benchmark is testing,
+        because I haven't found a way to run it myself.
+
+        However, I constructed a benchmark which shows at least one possible slow point.
+        The HTML5 spec talks about creating a new document for every time we use
+        the fragment parsing algorithm.  Document() it turns out, it a huge bloated
+        mess, and the constructor and destructor do a huge amount of work.
+        To avoid constructing (or destructing) documents for each innerHTML call,
+        this patch adds a shared dummy document used by all innerHTML calls.
+
+        This patch brings us from 7x slower than Safari 5 on tiny-innerHTML
+        to only 1.5x slower than Safari 5.  I'm sure there is more work to do here.
+
+        Saving a shared Document like this is error prone.  Currently
+        DummyDocumentFactory::releaseDocument() calls removeAllChildren()
+        in an attempt to clear the Document's state. However it's possible
+        that that call is not sufficient and we'll have future bugs here.
+
+        * html/parser/HTMLTreeBuilder.cpp:
+        (WebCore::DummyDocumentFactory::createDummyDocument):
+        (WebCore::DummyDocumentFactory::releaseDocument):
+        (WebCore::HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext):
+        (WebCore::HTMLTreeBuilder::FragmentParsingContext::document):
+        (WebCore::HTMLTreeBuilder::FragmentParsingContext::finished):
+        * html/parser/HTMLTreeBuilder.h:
+
 2011-01-28  Johnny Ding  <jnd@chromium.org>
 
         Reviewed by Adam Barth.
index 97cee13..6b58afa 100644 (file)
@@ -395,6 +395,50 @@ void HTMLTreeBuilder::detach()
     m_tree.detach();
 }
 
+// NOTE: HTML5 requires that we use a dummy document when parsing
+// document fragments.  However, creating a new Document element
+// for each fragment is very slow (Document() does too much work, and
+// innerHTML is a common call).  So we use a shared dummy document.
+// This sharing works because there can only ever be one fragment
+// parser at any time.  Fragment parsing is synchronous and done
+// only from the main thread.  It should be impossible for javascript
+// (or anything else) to ever hold a reference to the dummy document.
+// See https://bugs.webkit.org/show_bug.cgi?id=48719
+class DummyDocumentFactory {
+    WTF_MAKE_NONCOPYABLE(DummyDocumentFactory); WTF_MAKE_FAST_ALLOCATED;
+public:
+    // Use an explicit create/release here to ASSERT this sharing is safe.
+    static HTMLDocument* createDummyDocument();
+    static void releaseDocument(HTMLDocument*);
+
+private:
+    static HTMLDocument* s_sharedDummyDocument;
+    static int s_sharedDummyDocumentMutex;
+};
+
+HTMLDocument* DummyDocumentFactory::createDummyDocument()
+{
+    if (!s_sharedDummyDocument) {
+        s_sharedDummyDocument = HTMLDocument::create(0, KURL()).releaseRef();
+        s_sharedDummyDocumentMutex = 0;
+    }
+    ASSERT(!s_sharedDummyDocumentMutex);
+    ASSERT(!s_sharedDummyDocument->hasChildNodes());
+    s_sharedDummyDocumentMutex++;
+    return s_sharedDummyDocument;
+}
+
+void DummyDocumentFactory::releaseDocument(HTMLDocument* dummyDocument)
+{
+    ASSERT(s_sharedDummyDocument == dummyDocument);
+    s_sharedDummyDocumentMutex--;
+    ASSERT(!s_sharedDummyDocumentMutex);
+    dummyDocument->removeAllChildren();
+}
+
+HTMLDocument* DummyDocumentFactory::s_sharedDummyDocument = 0;
+int DummyDocumentFactory::s_sharedDummyDocumentMutex = 0;
+
 HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext()
     : m_fragment(0)
     , m_contextElement(0)
@@ -403,27 +447,33 @@ HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext()
 }
 
 HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext(DocumentFragment* fragment, Element* contextElement, FragmentScriptingPermission scriptingPermission)
-    : m_dummyDocumentForFragmentParsing(HTMLDocument::create(0, KURL(), fragment->document()->baseURI()))
+    : m_dummyDocumentForFragmentParsing(DummyDocumentFactory::createDummyDocument())
     , m_fragment(fragment)
     , m_contextElement(contextElement)
     , m_scriptingPermission(scriptingPermission)
 {
     m_dummyDocumentForFragmentParsing->setCompatibilityMode(fragment->document()->compatibilityMode());
+    // Setting the baseURL should work the same as it would have had we passed
+    // it during HTMLDocument() construction, since the new document is empty.
+    m_dummyDocumentForFragmentParsing->setURL(fragment->document()->baseURI());
 }
 
 Document* HTMLTreeBuilder::FragmentParsingContext::document() const
 {
     ASSERT(m_fragment);
-    return m_dummyDocumentForFragmentParsing.get();
+    return m_dummyDocumentForFragmentParsing;
 }
 
 void HTMLTreeBuilder::FragmentParsingContext::finished()
 {
     // Populate the DocumentFragment with the parsed content now that we're done.
-    ContainerNode* root = m_dummyDocumentForFragmentParsing.get();
+    ContainerNode* root = m_dummyDocumentForFragmentParsing;
     if (m_contextElement)
         root = m_dummyDocumentForFragmentParsing->documentElement();
     m_fragment->takeAllChildrenFrom(root);
+    ASSERT(!m_dummyDocumentForFragmentParsing->hasChildNodes());
+    DummyDocumentFactory::releaseDocument(m_dummyDocumentForFragmentParsing);
+    m_dummyDocumentForFragmentParsing = 0;
 }
 
 HTMLTreeBuilder::FragmentParsingContext::~FragmentParsingContext()
index 309ac6f..2af6158 100644 (file)
@@ -220,7 +220,9 @@ private:
         void finished();
 
     private:
-        RefPtr<Document> m_dummyDocumentForFragmentParsing;
+        // Use a shared dummy document to avoid expensive Document creation.
+        // Hold a raw pointer to the document since there is no need to ref it.
+        HTMLDocument* m_dummyDocumentForFragmentParsing;
         DocumentFragment* m_fragment;
         Element* m_contextElement;