Bug 94048 – SVGPathSegList has O(n) append!

• Status: RESOLVED
• Resolution: FIXED
• Component: SVG

[Philip Rogers]

Original bug: crbug.com/142675

PathSegList has O(n) append! Looks like every time appendItem is called we throw away the whole path and re-create it. This causes us to be really poor at the SVG path list benchmark: http://bl.ocks.org/1296930

[Tom Hudson]

I assume that you're looking at the expandCapacity(size()+1, ...) in appendSlowCase(); doesn't it percolate down to 

reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)))

which at least tries to grow by 25% each time?

[Florin Malita]

(In reply to comment #1)
> I assume that you're looking at the expandCapacity(size()+1, ...) in appendSlowCase(); doesn't it percolate down to 
> 
> reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)))
> 
> which at least tries to grow by 25% each time?

It's actually the way dynamic updates to the segment list are handled: SVGPathElement::pathSegListChanged() calls buildSVGPathByteStreamFromSVGPathSegList() which in turn just throws away the current result and rebuilds it -

bool buildSVGPathByteStreamFromSVGPathSegList(const SVGPathSegList& list, SVGPathByteStream* result, PathParsingMode parsingMode)
{
    ASSERT(result);
    result->clear();
    if (list.isEmpty())
        return false;

    SVGPathByteStreamBuilder* builder = globalSVGPathByteStreamBuilder(result);

    OwnPtr<SVGPathSegListSource> source = SVGPathSegListSource::create(list);
    SVGPathParser* parser = globalSVGPathParser(source.get(), builder);
    bool ok = parser->parsePathDataFromSource(parsingMode);

So for each JS path.pathSegList.appendItem() call, the byte stream gets rebuilt from scratch.

[Florin Malita]

BTW, this also means that currently setting the path data in one go (using the 'd' attribute) is a *lot* more efficient, as it avoids the problem above.

I've run a  quick test with a modified benchmark, and using that method CR is roughly twice as fast as FF on my Linux box:


--- bench_orig.html	2012-08-15 11:25:19.521652393 -0400
+++ bench2.html	2012-08-15 11:34:06.524369474 -0400
@@ -84,7 +84,7 @@
         for (i=0; i < num; i++) {
           xpos += (factor * Math.random() - factor_div_2) + (half_width  - xpos) * correction;
           ypos += (factor * Math.random() - factor_div_2) + (half_height - ypos) * correction;
-          path_seglist.appendItem(path.createSVGPathSegLinetoAbs(xpos, ypos));
+	  pdata += ' L ' + xpos + ' ' + ypos;
         }
       };
 
@@ -109,10 +109,12 @@
       var count = 0;
       var elapsed_time = 0;
       var sample_time, sample_start, sample_end;
+      var pdata = 'M ' + half_width + ' ' + half_height;
 
       function runSet() {
         sample_start = +new Date();
         addLineSegments(increment);
+        path.setAttribute('d', pdata);
         sample_end = +new Date();
         sample_time = sample_end-sample_start;
         elapsed_time += sample_time;

[Stephen Bannasch]

The reason I wrote the SVG Path Benchmark http://bl.ocks.org/1296930 the way I did was because my original use case was to show fast dynamically updating lines graphs. 

The extremely slow performance using SVG in webkit-based browsers caused me to recode this feature by overlaying a 2D Canvas over the SVG.

Being able to quickly and efficiently extend and render existing Paths is important to me.

[Stephen Bannasch]

Here's a google spreadsheet that compares performance drawing Paths in both Canvas and SVG on many different browsers and operating systems:

https://docs.google.com/a/concord.org/spreadsheet/ccc?key=0AtvlFoSBUC5kdEZJNVFySG9wSHZka0NsOTZDSkt3Nnc#gid=0

[Florin Malita]

(In reply to comment #4)
> 
> Being able to quickly and efficiently extend and render existing Paths is important to me.

Absolutely, no argument there - this will be addressed. I am just documenting a workaround that others may find useful, not saying that things work as intended :)

[Philip Rogers]

Just a quick update: I put together a demo of a O(1) appendItem() but it's only a hack at the moment as I don't think it's possible to implement the rest of SVGPathSegList's methods (removeItem, replaceItem, or insertItemBefore) in any performant way on our current infrastructure because our internal path representation is a flattened bytestream. I'm debating whether we should go forward with this approach, or restructure how we store paths internally.

[Philip Rogers]

Created attachment 162324 [details]
First pass

[Dirk Schulze]

Comment on attachment 162324 [details]
First pass

View in context: https://bugs.webkit.org/attachment.cgi?id=162324&action=review

Needs a real review later. Just some comments and questions.

> Source/WebCore/ChangeLog:9
> +        to&from an SVGPathSegList and a string representation of a path.

to and from   looks better.

> Source/WebCore/ChangeLog:31
> +        * svg/SVGPathByteStream.h:
> +        (WebCore::SVGPathByteStream::append):
> +        * svg/SVGPathElement.cpp:
> +        (WebCore::SVGPathElement::pathSegListChanged):
> +        * svg/SVGPathElement.h:
> +        (SVGPathElement):
> +        * svg/SVGPathParser.cpp:

Some inline comments can be helpful here.

> Source/WebCore/svg/SVGPathByteStream.h:68
> +    void append(SVGPathByteStream* other)
> +    {
> +        for (DataIterator it = other->begin(); it != other->end(); ++it)
> +            append(*it);

Are you adding the other string at the end of the current string? why?

> Source/WebCore/svg/SVGPathElement.cpp:336
> +void SVGPathElement::pathSegListChanged(SVGPathSegRole role, ListModification listModification, unsigned affectedIndex)

usually I am not a fan of adding unused variables. In this case why do we have the unsigned? Second, you can also just omit the name, then you don't need the UNUSED_PARAM makro.

> Source/WebCore/svg/SVGPathElement.cpp:345
> +        if (listModification == ListModificationAppend) {

I see, you want to extend this later.

> Source/WebCore/svg/SVGPathElement.h:96
> +    void pathSegListChanged(SVGPathSegRole, ListModification, unsigned affectedIndex);

As far this is not a virtual function, so why do you introduce the variable if you don't use it? Add it in a later patch when you use it.

> Source/WebCore/svg/SVGPathSegList.cpp:41
> +void SVGPathSegList::commitChange(SVGElement* contextElement, ListModification listModification, unsigned affectedIndex)

Ditto. Remove the index for now.

> LayoutTests/perf/svg-path-appenditem.html:17
> +        path.pathSegList.appendItem(path.createSVGPathSegLinetoAbs(20, 20));

This is what I may not understood above, here you add just a new segment. Above you call the append method that adds another byte stream. Do you create a bytestream just for the one segment?

[Philip Rogers]

Created attachment 162406 [details]
Update per reviewer comments

[Philip Rogers]

(In reply to comment #9)
Thanks for the quick review! I've updated the patch to address your points and made the ChangeLog less bad with a better description and benchmark data.

I've also started a meta-bug about the possibility of not using a byte stream and instead using a different data structure for our internal path representation (if we were to do that, the plumbing added in this patch would still be valid): https://bugs.webkit.org/show_bug.cgi?id=95909.

[Nikolas Zimmermann]

Comment on attachment 162406 [details]
Update per reviewer comments

View in context: https://bugs.webkit.org/attachment.cgi?id=162406&action=review

Indeed a new SVGPathByteStream has to be created, serialized from the to-be-appended SVGPathSeg. This is a good idea still, as appending two byte streams is cheaper, than what we do right now (rebuild).
I'd r+ this as-is, but will wait for Dirk, if he has additional comments.

> Source/WebCore/svg/properties/SVGListProperty.h:32
> +    ListModificationUnknown = 0,

I don't think you need to specify = 0,  = 1, .. it's redundant.

[Dirk Schulze]

My concerns are just that it fixes specific cases. We don't have a concept how we want to deal with it on excessive SVG DOM access in general. Especially for insert and other things. Please go ahead with the review, since I am a bit stock with SVG Open at the moment.

[Philip Rogers]

Friendly ping for a review :)

[Philip Rogers]

@Dirk, do you have time to look at this?

[Nikolas Zimmermann]

Comment on attachment 162406 [details]
Update per reviewer comments

Sorry phil, I forgot to login before submitting, two days ago :-( You should have mailed me in private, to remind me.. :-)

[WebKit Review Bot]

Comment on attachment 162406 [details]
Update per reviewer comments

Clearing flags on attachment: 162406

Committed r128729: <http://trac.webkit.org/changeset/128729>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Stephen Bannasch]

Thanks a bunch Philip and reviewers!

How can I follow progress for whether, how, and when this change propagates into the the nightly-releases of WebKit-based browsers?

I expect this work to be folded into Chrome and Safari at some point but am not sure what I can track to monitor this progress.

Will this work also end up in webkit-based browsers on other systems?

[Philip Rogers]

Thanks Niko!

(In reply to comment #19)
> Thanks a bunch Philip and reviewers!
> 
> How can I follow progress for whether, how, and when this change propagates into the the nightly-releases of WebKit-based browsers?
> 
> I expect this work to be folded into Chrome and Safari at some point but am not sure what I can track to monitor this progress.
> 
> Will this work also end up in webkit-based browsers on other systems?


The Chrome port releases very often and has 4 channels: canary (aka nightly), dev (chrome 23), beta (chrome 22), and stable (chrome 21). Every couple months the versions tick up one, so stable will be moving to Chrome 22 very soon. This patch is in canary right now if you want to test it, and the patch will likely be in dev channel in the next few days. You can watch the progress here: http://omahaproxy.appspot.com/viewer
base_webkit_revision is the version you're looking for, and this landed in webkit r128729

Safari releases a little slower, I think roughly once or twice a year.

Unfortunately I don't know about the iOS and Android browser release cycle :/

[Stephen Bannasch]

It's in Nightly Safari already.

The total elapsed time drawing 5000 line segments in this benchmark dropped from about 900ms to 9ms!  http://bl.ocks.org/1296930.

I have Chrome 23.0.1269.0 canary installed. It's not reporting any update available and the total elapsed time is still 871 ms.

Presumably the update will appear shortly.

[Stephen Bannasch]

The Nightly version of Safari/Webkit now runs this SVG Path performance benchmark in just 8ms:

http://bl.ocks.org/1296930

While Chrome 24.0.1272.1 canary now takes 18ms.

I've updated my google spreadsheet with these new results:

https://docs.google.com/a/concord.org/spreadsheet/ccc?key=0AtvlFoSBUC5kdEZJNVFySG9wSHZka0NsOTZDSkt3Nnc#gid=0

[Stephen Bannasch]

The just released Nightly Safari/Webkit (5.1.7 (6534.57.2, r129183)) now runs the benchmark in 25ms almost 3 times slower than it did just a day ago. This performance is still reasonably fast and is now somewhat slower than the equivalent Chrome release..

[Philip Rogers]

(In reply to comment #23)
> The just released Nightly Safari/Webkit (5.1.7 (6534.57.2, r129183)) now runs the benchmark in 25ms almost 3 times slower than it did just a day ago. This performance is still reasonably fast and is now somewhat slower than the equivalent Chrome release..

I think it's likely this is an edge case in the V8 <-> SVG code. I've followed this bug to track it:
https://bugs.webkit.org/show_bug.cgi?id=97420

I did confirm that Chromium nightly and Safari nightly have this fix as the time is constant across runs, albeit slightly slower on Chromium.