Source/WebCore: Make SVGPathSegList.appendItem O(1) instead of O(n)
authorpdr@google.com <pdr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 17 Sep 2012 08:56:04 +0000 (08:56 +0000)
committerpdr@google.com <pdr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 17 Sep 2012 08:56:04 +0000 (08:56 +0000)
https://bugs.webkit.org/show_bug.cgi?id=94048

Reviewed by Nikolas Zimmermann.

Paths in SVG can be specified with a String (with the d attribute) or
with an SVGPathSegList. In SVGPathElement a single representation is
maintained: an SVGPathByteStream. To keep the byte stream synchronized with
the d attribute and the PathSegList, this byte stream is
rebuilt on every operation. As a result, any modification to the
path is an O(n) operation.

This patch takes advantage of the stream aspect of SVGPathByteStream
to make SVGPathSegList.append an O(1) operation instead of O(n).
When an SVGPathSeg is appended to an SVGPathSegList, this patch parses
the SVGPathSeg and directly appends the resulting bytes to the
byte stream.

To achieve this some plumbing has been added to pass more information
about the actual path changes from the SVGPathSegListTearOff to the
SVGPathElement: instead of the generic commitChange() this patch adds
commitChange(ListModification type). If we decide to change our
internal path data structure in the future, this additional commitChange
function can be used to pass the information needed to make
SVGPathSegList synchronization faster.

SVG Path Benchmark (http://bl.ocks.org/1296930) showing just the
appendItem() time used in building a 5000 segment path (avg of 3 runs):
WebKit without patch: 562 ms
Firefox 18.01a:       55 ms
Opera 12.50 internal: 27 ms
WebKit with patch:    7 ms

Test: perf/svg-path-appenditem.html

    This test proves the claim: SVGPathSegList.appendItem is now O(1).
    Additional tests that appendItem works are covered with existing tests.

* svg/SVGPathByteStream.h:
(WebCore::SVGPathByteStream::append):

    This additional append method allows an SVGPathByteStream to be
    appended to another.

* svg/SVGPathElement.cpp:
(WebCore::SVGPathElement::pathSegListChanged):

    By passing the extra ListModification type to pathSegListChanged,
    SVGPathElement is now able to only synchronize the parts of the byte stream
    that actually changed. In this patch only append is treated
    differently but one can imagine other performance improvements this
    additional information allows.

* svg/SVGPathElement.h:
(SVGPathElement):
* svg/SVGPathParser.cpp:
(WebCore::SVGPathParser::parsePathDataFromSource):

    During normal SVGPathSegList parsing we enforce that the path start with a moveto
    command. This function has been expanded to make that optional so that parsing
    can be performed elsewhere in the path (e.g., in the middle).

* svg/SVGPathParser.h:
(SVGPathParser):
* svg/SVGPathSegList.cpp:
(WebCore::SVGPathSegList::commitChange):
* svg/SVGPathSegList.h:
(SVGPathSegList):
* svg/SVGPathSegWithContext.h:
(WebCore::SVGPathSegWithContext::commitChange):
* svg/SVGPathUtilities.cpp:
(WebCore::appendSVGPathByteStreamFromSVGPathSeg):

    This function reuses the SVGPathSegList parsing infrastructure
    to parse an SVGPathSegList with just the single SVGPathSeg that
    is being appended. The resulting byte stream can then be appended
    to the result path byte stream.

(WebCore):
* svg/SVGPathUtilities.h:
(WebCore):
* svg/properties/SVGListProperty.h:
(WebCore::SVGListProperty::appendItemValues):
(WebCore::SVGListProperty::appendItemValuesAndWrappers):
(WebCore::SVGListProperty::commitChange):
(SVGListProperty):
* svg/properties/SVGPathSegListPropertyTearOff.h:
(WebCore::SVGPathSegListPropertyTearOff::commitChange):
(SVGPathSegListPropertyTearOff):

LayoutTests: Make SVGPathSegList.append O(1) instead of O(n)
https://bugs.webkit.org/show_bug.cgi?id=94048

Reviewed by Nikolas Zimmermann.

Add performance test to prove this patch works. The rest of SVGPathSegList.append should be covered
in existing tests.

* perf/svg-path-appenditem-expected.txt: Added.
* perf/svg-path-appenditem.html: Added.

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

15 files changed:
LayoutTests/ChangeLog
LayoutTests/perf/svg-path-appenditem-expected.txt [new file with mode: 0644]
LayoutTests/perf/svg-path-appenditem.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/svg/SVGPathByteStream.h
Source/WebCore/svg/SVGPathElement.cpp
Source/WebCore/svg/SVGPathElement.h
Source/WebCore/svg/SVGPathParser.cpp
Source/WebCore/svg/SVGPathParser.h
Source/WebCore/svg/SVGPathSegList.cpp
Source/WebCore/svg/SVGPathSegList.h
Source/WebCore/svg/SVGPathUtilities.cpp
Source/WebCore/svg/SVGPathUtilities.h
Source/WebCore/svg/properties/SVGListProperty.h
Source/WebCore/svg/properties/SVGPathSegListPropertyTearOff.h

index 2cb5634..96b966b 100644 (file)
@@ -1,3 +1,16 @@
+2012-09-17  Philip Rogers  <pdr@google.com>
+
+        Make SVGPathSegList.append O(1) instead of O(n)
+        https://bugs.webkit.org/show_bug.cgi?id=94048
+
+        Reviewed by Nikolas Zimmermann.
+
+        Add performance test to prove this patch works. The rest of SVGPathSegList.append should be covered
+        in existing tests.
+
+        * perf/svg-path-appenditem-expected.txt: Added.
+        * perf/svg-path-appenditem.html: Added.
+
 2012-09-17  Christophe Dumez  <christophe.dumez@intel.com>
 
         [EFL] Add baseline for text/shaping tests
diff --git a/LayoutTests/perf/svg-path-appenditem-expected.txt b/LayoutTests/perf/svg-path-appenditem-expected.txt
new file mode 100644 (file)
index 0000000..6e1b75e
--- /dev/null
@@ -0,0 +1,3 @@
+Tests that SVG path.appendItem() is constant with respect to the length of the path.
+PASS
+
diff --git a/LayoutTests/perf/svg-path-appenditem.html b/LayoutTests/perf/svg-path-appenditem.html
new file mode 100644 (file)
index 0000000..340113e
--- /dev/null
@@ -0,0 +1,23 @@
+<body>
+<script src="../resources/magnitude-perf.js"></script>
+<script>
+    var path;
+
+    function setup(magnitude)
+    {
+        path = document.createElementNS("http://www.w3.org/2000/svg", "path");
+        var pathD = "";
+        for (var i = 0; i < magnitude; i++)
+            pathD += "M20 20Z";
+        path.setAttribute('d', pathD);
+    }
+
+    function test(magnitude)
+    {
+        path.pathSegList.appendItem(path.createSVGPathSegLinetoAbs(20, 20));
+    }
+
+    Magnitude.description("Tests that SVG path.appendItem() is constant with respect to the length of the path.");
+    Magnitude.run(setup, test, Magnitude.CONSTANT);
+</script>
+</body>
index 5e45491..11b56ff 100644 (file)
@@ -1,3 +1,95 @@
+2012-09-17  Philip Rogers  <pdr@google.com>
+
+        Make SVGPathSegList.appendItem O(1) instead of O(n)
+        https://bugs.webkit.org/show_bug.cgi?id=94048
+
+        Reviewed by Nikolas Zimmermann.
+
+        Paths in SVG can be specified with a String (with the d attribute) or
+        with an SVGPathSegList. In SVGPathElement a single representation is
+        maintained: an SVGPathByteStream. To keep the byte stream synchronized with
+        the d attribute and the PathSegList, this byte stream is
+        rebuilt on every operation. As a result, any modification to the
+        path is an O(n) operation.
+
+        This patch takes advantage of the stream aspect of SVGPathByteStream
+        to make SVGPathSegList.append an O(1) operation instead of O(n).
+        When an SVGPathSeg is appended to an SVGPathSegList, this patch parses
+        the SVGPathSeg and directly appends the resulting bytes to the
+        byte stream.
+
+        To achieve this some plumbing has been added to pass more information
+        about the actual path changes from the SVGPathSegListTearOff to the
+        SVGPathElement: instead of the generic commitChange() this patch adds
+        commitChange(ListModification type). If we decide to change our
+        internal path data structure in the future, this additional commitChange
+        function can be used to pass the information needed to make
+        SVGPathSegList synchronization faster.
+
+        SVG Path Benchmark (http://bl.ocks.org/1296930) showing just the
+        appendItem() time used in building a 5000 segment path (avg of 3 runs):
+        WebKit without patch: 562 ms
+        Firefox 18.01a:       55 ms
+        Opera 12.50 internal: 27 ms
+        WebKit with patch:    7 ms
+
+        Test: perf/svg-path-appenditem.html
+
+            This test proves the claim: SVGPathSegList.appendItem is now O(1).
+            Additional tests that appendItem works are covered with existing tests.
+
+        * svg/SVGPathByteStream.h:
+        (WebCore::SVGPathByteStream::append):
+
+            This additional append method allows an SVGPathByteStream to be
+            appended to another.
+
+        * svg/SVGPathElement.cpp:
+        (WebCore::SVGPathElement::pathSegListChanged):
+
+            By passing the extra ListModification type to pathSegListChanged,
+            SVGPathElement is now able to only synchronize the parts of the byte stream
+            that actually changed. In this patch only append is treated
+            differently but one can imagine other performance improvements this
+            additional information allows.
+
+        * svg/SVGPathElement.h:
+        (SVGPathElement):
+        * svg/SVGPathParser.cpp:
+        (WebCore::SVGPathParser::parsePathDataFromSource):
+
+            During normal SVGPathSegList parsing we enforce that the path start with a moveto
+            command. This function has been expanded to make that optional so that parsing
+            can be performed elsewhere in the path (e.g., in the middle).
+
+        * svg/SVGPathParser.h:
+        (SVGPathParser):
+        * svg/SVGPathSegList.cpp:
+        (WebCore::SVGPathSegList::commitChange):
+        * svg/SVGPathSegList.h:
+        (SVGPathSegList):
+        * svg/SVGPathSegWithContext.h:
+        (WebCore::SVGPathSegWithContext::commitChange):
+        * svg/SVGPathUtilities.cpp:
+        (WebCore::appendSVGPathByteStreamFromSVGPathSeg):
+
+            This function reuses the SVGPathSegList parsing infrastructure
+            to parse an SVGPathSegList with just the single SVGPathSeg that
+            is being appended. The resulting byte stream can then be appended
+            to the result path byte stream.
+
+        (WebCore):
+        * svg/SVGPathUtilities.h:
+        (WebCore):
+        * svg/properties/SVGListProperty.h:
+        (WebCore::SVGListProperty::appendItemValues):
+        (WebCore::SVGListProperty::appendItemValuesAndWrappers):
+        (WebCore::SVGListProperty::commitChange):
+        (SVGListProperty):
+        * svg/properties/SVGPathSegListPropertyTearOff.h:
+        (WebCore::SVGPathSegListPropertyTearOff::commitChange):
+        (SVGPathSegListPropertyTearOff):
+
 2012-09-16  James Robinson  <jamesr@chromium.org>
 
         Chromium win build fix - listing a file that doesn't exist is a fatal errors in the msvs gyp generator.
index 15ad961..523faec 100644 (file)
@@ -62,6 +62,11 @@ public:
     DataIterator begin() { return m_data.begin(); }
     DataIterator end() { return m_data.end(); }
     void append(unsigned char byte) { m_data.append(byte); }
+    void append(SVGPathByteStream* other)
+    {
+        for (DataIterator it = other->begin(); it != other->end(); ++it)
+            append(*it);
+    }
     void clear() { m_data.clear(); }
     bool isEmpty() const { return !m_data.size(); }
     unsigned size() const { return m_data.size(); }
index 986f5fe..04e25ea 100644 (file)
@@ -333,14 +333,18 @@ SVGPathSegListPropertyTearOff* SVGPathElement::animatedNormalizedPathSegList()
     return 0;
 }
 
-void SVGPathElement::pathSegListChanged(SVGPathSegRole role)
+void SVGPathElement::pathSegListChanged(SVGPathSegRole role, ListModification listModification)
 {
     switch (role) {
     case PathSegNormalizedRole:
         // FIXME: https://bugs.webkit.org/show_bug.cgi?id=15412 - Implement normalized path segment lists!
         break;
     case PathSegUnalteredRole:
-        buildSVGPathByteStreamFromSVGPathSegList(m_pathSegList.value, m_pathByteStream.get(), UnalteredParsing);
+        if (listModification == ListModificationAppend) {
+            ASSERT(!m_pathSegList.value.isEmpty());
+            appendSVGPathByteStreamFromSVGPathSeg(m_pathSegList.value.last(), m_pathByteStream.get(), UnalteredParsing);
+        } else
+            buildSVGPathByteStreamFromSVGPathSegList(m_pathSegList.value, m_pathByteStream.get(), UnalteredParsing);
         break;
     case PathSegUndefinedRole:
         return;
index 265c779..2bda949 100644 (file)
@@ -93,7 +93,7 @@ public:
 
     SVGPathByteStream* pathByteStream() const;
 
-    void pathSegListChanged(SVGPathSegRole);
+    void pathSegListChanged(SVGPathSegRole, ListModification = ListModificationUnknown);
 
     virtual FloatRect getBBox(StyleUpdateStrategy = AllowStyleUpdate);
 
index 7decf56..dc4892a 100644 (file)
@@ -282,7 +282,7 @@ bool SVGPathParser::parseArcToSegment()
     return true;
 }
 
-bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode)
+bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode, bool checkForInitialMoveTo)
 {
     ASSERT(m_source);
     ASSERT(m_consumer);
@@ -303,7 +303,7 @@ bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode)
     m_lastCommand = PathSegUnknown;
 
     // Path must start with moveto.
-    if (command != PathSegMoveToAbs && command != PathSegMoveToRel)
+    if (checkForInitialMoveTo && command != PathSegMoveToAbs && command != PathSegMoveToRel)
         return false;
 
     while (true) {
index 52e14c8..a9a0b24 100644 (file)
@@ -38,7 +38,7 @@ class SVGPathParser {
 public:
     SVGPathParser();
 
-    bool parsePathDataFromSource(PathParsingMode pathParsingMode);
+    bool parsePathDataFromSource(PathParsingMode, bool checkForInitialMoveTo = true);
     void setCurrentConsumer(SVGPathConsumer* consumer) { m_consumer = consumer; }
     void setCurrentSource(SVGPathSource* source) { m_source = source; }
     void cleanup();
index dc7760b..d40cb56 100644 (file)
@@ -38,11 +38,11 @@ String SVGPathSegList::valueAsString() const
     return pathString;
 }
 
-void SVGPathSegList::commitChange(SVGElement* contextElement)
+void SVGPathSegList::commitChange(SVGElement* contextElement, ListModification listModification)
 {
     ASSERT(contextElement);
     ASSERT(contextElement->hasTagName(SVGNames::pathTag));
-    static_cast<SVGPathElement*>(contextElement)->pathSegListChanged(m_role);
+    static_cast<SVGPathElement*>(contextElement)->pathSegListChanged(m_role, listModification);
 }
 
 }
index 5013b9f..058c080 100644 (file)
@@ -21,6 +21,7 @@
 #define SVGPathSegList_h
 
 #if ENABLE(SVG)
+#include "SVGListProperty.h"
 #include "SVGPathSeg.h"
 #include "SVGPropertyTraits.h"
 
@@ -41,7 +42,7 @@ public:
     String valueAsString() const;
 
     // Only used by SVGPathSegListPropertyTearOff.
-    void commitChange(SVGElement* contextElement);
+    void commitChange(SVGElement* contextElement, ListModification);
 
 private:
     SVGPathSegRole m_role;
index a5af9e7..9caf6a4 100644 (file)
@@ -140,6 +140,28 @@ bool buildSVGPathByteStreamFromSVGPathSegList(const SVGPathSegList& list, SVGPat
     return ok;
 }
 
+bool appendSVGPathByteStreamFromSVGPathSeg(PassRefPtr<SVGPathSeg> pathSeg, SVGPathByteStream* result, PathParsingMode parsingMode)
+{
+    ASSERT(result);
+    // FIXME: https://bugs.webkit.org/show_bug.cgi?id=15412 - Implement normalized path segment lists!
+    ASSERT(parsingMode == UnalteredParsing);
+
+    SVGPathSegList appendedItemList(PathSegUnalteredRole);
+    appendedItemList.append(pathSeg);
+    OwnPtr<SVGPathByteStream> appendedByteStream = SVGPathByteStream::create();
+
+    SVGPathByteStreamBuilder* builder = globalSVGPathByteStreamBuilder(appendedByteStream.get());
+    OwnPtr<SVGPathSegListSource> source = SVGPathSegListSource::create(appendedItemList);
+    SVGPathParser* parser = globalSVGPathParser(source.get(), builder);
+    bool ok = parser->parsePathDataFromSource(parsingMode, false);
+    parser->cleanup();
+
+    if (ok)
+        result->append(appendedByteStream.get());
+
+    return ok;
+}
+
 bool buildPathFromByteStream(SVGPathByteStream* stream, Path& result)
 {
     ASSERT(stream);
index f24aa00..bedaa21 100644 (file)
@@ -23,6 +23,7 @@
 #if ENABLE(SVG)
 #include "SVGPathByteStream.h"
 #include "SVGPathConsumer.h"
+#include "SVGPathSeg.h"
 #include <wtf/OwnPtr.h>
 #include <wtf/text/WTFString.h>
 
@@ -39,6 +40,7 @@ bool buildPathFromByteStream(SVGPathByteStream*, Path&);
 
 // SVGPathSegList/String -> SVGPathByteStream
 bool buildSVGPathByteStreamFromSVGPathSegList(const SVGPathSegList&, SVGPathByteStream*, PathParsingMode);
+bool appendSVGPathByteStreamFromSVGPathSeg(PassRefPtr<SVGPathSeg>, SVGPathByteStream*, PathParsingMode);
 bool buildSVGPathByteStreamFromString(const String&, SVGPathByteStream*, PathParsingMode);
 
 // SVGPathByteStream/SVGPathSegList -> String
index 1587a40..9db2f4c 100644 (file)
 
 namespace WebCore {
 
+enum ListModification {
+    ListModificationUnknown = 0,
+    ListModificationInsert = 1,
+    ListModificationReplace = 2,
+    ListModificationRemove = 3,
+    ListModificationAppend = 4
+};
+
 template<typename PropertyType>
 class SVGAnimatedListPropertyTearOff;
 
@@ -390,7 +398,7 @@ public:
         // Append the value at the end of the list.
         m_values->append(newItem);
 
-        commitChange();
+        commitChange(ListModificationAppend);
         return newItem;
     }
 
@@ -416,7 +424,7 @@ public:
         m_values->append(newItem->propertyReference());
         m_wrappers->append(newItem);
 
-        commitChange();
+        commitChange(ListModificationAppend);
         return newItem.release();
     }
 
@@ -448,6 +456,11 @@ protected:
     }
 
     virtual void commitChange() = 0;
+    virtual void commitChange(ListModification)
+    {
+        commitChange();
+    }
+
     virtual void processIncomingListItemValue(const ListItemType& newItem, unsigned* indexToModify) = 0;
     virtual void processIncomingListItemWrapper(RefPtr<ListItemTearOff>& newItem, unsigned* indexToModify) = 0;
 
index 4f41af3..bac9ee7 100644 (file)
@@ -140,7 +140,13 @@ private:
     virtual void commitChange()
     {
         ASSERT(m_values);
-        m_values->commitChange(m_animatedProperty->contextElement());
+        m_values->commitChange(m_animatedProperty->contextElement(), ListModificationUnknown);
+    }
+
+    virtual void commitChange(ListModification listModification)
+    {
+        ASSERT(m_values);
+        m_values->commitChange(m_animatedProperty->contextElement(), listModification);
     }
 
     virtual void processIncomingListItemValue(const ListItemType& newItem, unsigned* indexToModify);