• pdr@google.com's avatar
    Source/WebCore: Make SVGPathSegList.appendItem O(1) instead of O(n) · 9725ba60
    pdr@google.com authored
    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:
        This additional append method allows an SVGPathByteStream to be
        appended to another.
    * svg/SVGPathElement.cpp:
        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:
    * svg/SVGPathParser.cpp:
        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:
    * svg/SVGPathSegList.cpp:
    * svg/SVGPathSegList.h:
    * svg/SVGPathSegWithContext.h:
    * svg/SVGPathUtilities.cpp:
        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.
    * svg/SVGPathUtilities.h:
    * svg/properties/SVGListProperty.h:
    * svg/properties/SVGPathSegListPropertyTearOff.h:
    LayoutTests: Make SVGPathSegList.append O(1) instead of O(n)
    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: http://svn.webkit.org/repository/webkit/trunk@128729 268f45cc-cd09-0410-ab3c-d52691b4dbfc