Changeset 128729 in webkit


Ignore:
Timestamp:
Sep 17, 2012 1:56:04 AM (12 years ago)
Author:
pdr@google.com
Message:

Source/WebCore: 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):

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.
Location:
trunk
Files:
2 added
13 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r128728 r128729  
     12012-09-17  Philip Rogers  <pdr@google.com>
     2
     3        Make SVGPathSegList.append O(1) instead of O(n)
     4        https://bugs.webkit.org/show_bug.cgi?id=94048
     5
     6        Reviewed by Nikolas Zimmermann.
     7
     8        Add performance test to prove this patch works. The rest of SVGPathSegList.append should be covered
     9        in existing tests.
     10
     11        * perf/svg-path-appenditem-expected.txt: Added.
     12        * perf/svg-path-appenditem.html: Added.
     13
    1142012-09-17  Christophe Dumez  <christophe.dumez@intel.com>
    215

  • trunk/Source/WebCore/ChangeLog

    r128716 r128729  
     12012-09-17  Philip Rogers  <pdr@google.com>
     2
     3        Make SVGPathSegList.appendItem O(1) instead of O(n)
     4        https://bugs.webkit.org/show_bug.cgi?id=94048
     5
     6        Reviewed by Nikolas Zimmermann.
     7
     8        Paths in SVG can be specified with a String (with the d attribute) or
     9        with an SVGPathSegList. In SVGPathElement a single representation is
     10        maintained: an SVGPathByteStream. To keep the byte stream synchronized with
     11        the d attribute and the PathSegList, this byte stream is
     12        rebuilt on every operation. As a result, any modification to the
     13        path is an O(n) operation.
     14
     15        This patch takes advantage of the stream aspect of SVGPathByteStream
     16        to make SVGPathSegList.append an O(1) operation instead of O(n).
     17        When an SVGPathSeg is appended to an SVGPathSegList, this patch parses
     18        the SVGPathSeg and directly appends the resulting bytes to the
     19        byte stream.
     20
     21        To achieve this some plumbing has been added to pass more information
     22        about the actual path changes from the SVGPathSegListTearOff to the
     23        SVGPathElement: instead of the generic commitChange() this patch adds
     24        commitChange(ListModification type). If we decide to change our
     25        internal path data structure in the future, this additional commitChange
     26        function can be used to pass the information needed to make
     27        SVGPathSegList synchronization faster.
     28
     29        SVG Path Benchmark (http://bl.ocks.org/1296930) showing just the
     30        appendItem() time used in building a 5000 segment path (avg of 3 runs):
     31        WebKit without patch: 562 ms
     32        Firefox 18.01a:       55 ms
     33        Opera 12.50 internal: 27 ms
     34        WebKit with patch:    7 ms
     35
     36        Test: perf/svg-path-appenditem.html
     37
     38            This test proves the claim: SVGPathSegList.appendItem is now O(1).
     39            Additional tests that appendItem works are covered with existing tests.
     40
     41        * svg/SVGPathByteStream.h:
     42        (WebCore::SVGPathByteStream::append):
     43
     44            This additional append method allows an SVGPathByteStream to be
     45            appended to another.
     46
     47        * svg/SVGPathElement.cpp:
     48        (WebCore::SVGPathElement::pathSegListChanged):
     49
     50            By passing the extra ListModification type to pathSegListChanged,
     51            SVGPathElement is now able to only synchronize the parts of the byte stream
     52            that actually changed. In this patch only append is treated
     53            differently but one can imagine other performance improvements this
     54            additional information allows.
     55
     56        * svg/SVGPathElement.h:
     57        (SVGPathElement):
     58        * svg/SVGPathParser.cpp:
     59        (WebCore::SVGPathParser::parsePathDataFromSource):
     60
     61            During normal SVGPathSegList parsing we enforce that the path start with a moveto
     62            command. This function has been expanded to make that optional so that parsing
     63            can be performed elsewhere in the path (e.g., in the middle).
     64
     65        * svg/SVGPathParser.h:
     66        (SVGPathParser):
     67        * svg/SVGPathSegList.cpp:
     68        (WebCore::SVGPathSegList::commitChange):
     69        * svg/SVGPathSegList.h:
     70        (SVGPathSegList):
     71        * svg/SVGPathSegWithContext.h:
     72        (WebCore::SVGPathSegWithContext::commitChange):
     73        * svg/SVGPathUtilities.cpp:
     74        (WebCore::appendSVGPathByteStreamFromSVGPathSeg):
     75
     76            This function reuses the SVGPathSegList parsing infrastructure
     77            to parse an SVGPathSegList with just the single SVGPathSeg that
     78            is being appended. The resulting byte stream can then be appended
     79            to the result path byte stream.
     80
     81        (WebCore):
     82        * svg/SVGPathUtilities.h:
     83        (WebCore):
     84        * svg/properties/SVGListProperty.h:
     85        (WebCore::SVGListProperty::appendItemValues):
     86        (WebCore::SVGListProperty::appendItemValuesAndWrappers):
     87        (WebCore::SVGListProperty::commitChange):
     88        (SVGListProperty):
     89        * svg/properties/SVGPathSegListPropertyTearOff.h:
     90        (WebCore::SVGPathSegListPropertyTearOff::commitChange):
     91        (SVGPathSegListPropertyTearOff):
     92
    1932012-09-16  James Robinson  <jamesr@chromium.org>
    294

  • trunk/Source/WebCore/svg/SVGPathByteStream.h

    r115555 r128729  
    6363    DataIterator end() { return m_data.end(); }
    6464    void append(unsigned char byte) { m_data.append(byte); }
     65    void append(SVGPathByteStream* other)
     66    {
     67        for (DataIterator it = other->begin(); it != other->end(); ++it)
     68            append(*it);
     69    }
    6570    void clear() { m_data.clear(); }
    6671    bool isEmpty() const { return !m_data.size(); }

  • trunk/Source/WebCore/svg/SVGPathElement.cpp

    r126693 r128729  
    334334}
    335335
    336 void SVGPathElement::pathSegListChanged(SVGPathSegRole role)
     336void SVGPathElement::pathSegListChanged(SVGPathSegRole role, ListModification listModification)
    337337{
    338338    switch (role) {
    … …  
    341341        break;
    342342    case PathSegUnalteredRole:
    343         buildSVGPathByteStreamFromSVGPathSegList(m_pathSegList.value, m_pathByteStream.get(), UnalteredParsing);
     343        if (listModification == ListModificationAppend) {
     344            ASSERT(!m_pathSegList.value.isEmpty());
     345            appendSVGPathByteStreamFromSVGPathSeg(m_pathSegList.value.last(), m_pathByteStream.get(), UnalteredParsing);
     346        } else
     347            buildSVGPathByteStreamFromSVGPathSegList(m_pathSegList.value, m_pathByteStream.get(), UnalteredParsing);
    344348        break;
    345349    case PathSegUndefinedRole:

  • trunk/Source/WebCore/svg/SVGPathElement.h

    r126693 r128729  
    9494    SVGPathByteStream* pathByteStream() const;
    9595
    96     void pathSegListChanged(SVGPathSegRole);
     96    void pathSegListChanged(SVGPathSegRole, ListModification = ListModificationUnknown);
    9797
    9898    virtual FloatRect getBBox(StyleUpdateStrategy = AllowStyleUpdate);

  • trunk/Source/WebCore/svg/SVGPathParser.cpp

    r101895 r128729  
    283283}
    284284
    285 bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode)
     285bool SVGPathParser::parsePathDataFromSource(PathParsingMode pathParsingMode, bool checkForInitialMoveTo)
    286286{
    287287    ASSERT(m_source);
    … …  
    304304
    305305    // Path must start with moveto.
    306     if (command != PathSegMoveToAbs && command != PathSegMoveToRel)
     306    if (checkForInitialMoveTo && command != PathSegMoveToAbs && command != PathSegMoveToRel)
    307307        return false;
    308308

  • trunk/Source/WebCore/svg/SVGPathParser.h

    r127757 r128729  
    3939    SVGPathParser();
    4040
    41     bool parsePathDataFromSource(PathParsingMode pathParsingMode);
     41    bool parsePathDataFromSource(PathParsingMode, bool checkForInitialMoveTo = true);
    4242    void setCurrentConsumer(SVGPathConsumer* consumer) { m_consumer = consumer; }
    4343    void setCurrentSource(SVGPathSource* source) { m_source = source; }

  • trunk/Source/WebCore/svg/SVGPathSegList.cpp

    r115560 r128729  
    3939}
    4040
    41 void SVGPathSegList::commitChange(SVGElement* contextElement)
     41void SVGPathSegList::commitChange(SVGElement* contextElement, ListModification listModification)
    4242{
    4343    ASSERT(contextElement);
    4444    ASSERT(contextElement->hasTagName(SVGNames::pathTag));
    45     static_cast<SVGPathElement*>(contextElement)->pathSegListChanged(m_role);
     45    static_cast<SVGPathElement*>(contextElement)->pathSegListChanged(m_role, listModification);
    4646}
    4747

  • trunk/Source/WebCore/svg/SVGPathSegList.h

    r74493 r128729  
    2222
    2323#if ENABLE(SVG)
     24#include "SVGListProperty.h"
    2425#include "SVGPathSeg.h"
    2526#include "SVGPropertyTraits.h"
    … …  
    4243
    4344    // Only used by SVGPathSegListPropertyTearOff.
    44     void commitChange(SVGElement* contextElement);
     45    void commitChange(SVGElement* contextElement, ListModification);
    4546
    4647private:

  • trunk/Source/WebCore/svg/SVGPathUtilities.cpp

    r115560 r128729  
    141141}
    142142
     143bool appendSVGPathByteStreamFromSVGPathSeg(PassRefPtr<SVGPathSeg> pathSeg, SVGPathByteStream* result, PathParsingMode parsingMode)
     144{
     145    ASSERT(result);
     146    // FIXME: https://bugs.webkit.org/show_bug.cgi?id=15412 - Implement normalized path segment lists!
     147    ASSERT(parsingMode == UnalteredParsing);
     148
     149    SVGPathSegList appendedItemList(PathSegUnalteredRole);
     150    appendedItemList.append(pathSeg);
     151    OwnPtr<SVGPathByteStream> appendedByteStream = SVGPathByteStream::create();
     152
     153    SVGPathByteStreamBuilder* builder = globalSVGPathByteStreamBuilder(appendedByteStream.get());
     154    OwnPtr<SVGPathSegListSource> source = SVGPathSegListSource::create(appendedItemList);
     155    SVGPathParser* parser = globalSVGPathParser(source.get(), builder);
     156    bool ok = parser->parsePathDataFromSource(parsingMode, false);
     157    parser->cleanup();
     158
     159    if (ok)
     160        result->append(appendedByteStream.get());
     161
     162    return ok;
     163}
     164
    143165bool buildPathFromByteStream(SVGPathByteStream* stream, Path& result)
    144166{

  • trunk/Source/WebCore/svg/SVGPathUtilities.h

    r115560 r128729  
    2424#include "SVGPathByteStream.h"
    2525#include "SVGPathConsumer.h"
     26#include "SVGPathSeg.h"
    2627#include <wtf/OwnPtr.h>
    2728#include <wtf/text/WTFString.h>
    … …  
    4041// SVGPathSegList/String -> SVGPathByteStream
    4142bool buildSVGPathByteStreamFromSVGPathSegList(const SVGPathSegList&, SVGPathByteStream*, PathParsingMode);
     43bool appendSVGPathByteStreamFromSVGPathSeg(PassRefPtr<SVGPathSeg>, SVGPathByteStream*, PathParsingMode);
    4244bool buildSVGPathByteStreamFromString(const String&, SVGPathByteStream*, PathParsingMode);
    4345

  • trunk/Source/WebCore/svg/properties/SVGListProperty.h

    r124733 r128729  
    2929namespace WebCore {
    3030
     31enum ListModification {
     32    ListModificationUnknown = 0,
     33    ListModificationInsert = 1,
     34    ListModificationReplace = 2,
     35    ListModificationRemove = 3,
     36    ListModificationAppend = 4
     37};
     38
    3139template<typename PropertyType>
    3240class SVGAnimatedListPropertyTearOff;
    … …  
    391399        m_values->append(newItem);
    392400
    393         commitChange();
     401        commitChange(ListModificationAppend);
    394402        return newItem;
    395403    }
    … …  
    417425        m_wrappers->append(newItem);
    418426
    419         commitChange();
     427        commitChange(ListModificationAppend);
    420428        return newItem.release();
    421429    }
    … …  
    449457
    450458    virtual void commitChange() = 0;
     459    virtual void commitChange(ListModification)
     460    {
     461        commitChange();
     462    }
     463
    451464    virtual void processIncomingListItemValue(const ListItemType& newItem, unsigned* indexToModify) = 0;
    452465    virtual void processIncomingListItemWrapper(RefPtr<ListItemTearOff>& newItem, unsigned* indexToModify) = 0;

  • trunk/Source/WebCore/svg/properties/SVGPathSegListPropertyTearOff.h

    r118735 r128729  
    141141    {
    142142        ASSERT(m_values);
    143         m_values->commitChange(m_animatedProperty->contextElement());
     143        m_values->commitChange(m_animatedProperty->contextElement(), ListModificationUnknown);
     144    }
     145
     146    virtual void commitChange(ListModification listModification)
     147    {
     148        ASSERT(m_values);
     149        m_values->commitChange(m_animatedProperty->contextElement(), listModification);
    144150    }
    145151
Note: See TracChangeset for help on using the changeset viewer.