Bug 96697 – Refactor SMILTimeContainer to maintain animation information instead of recalculating it every frame

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

[Philip Rogers]

SMILTimeContainer::updateAnimations is a hot method and pines for some performance-related refactoring. For example, at the moment we both create a copy of the animations vector and re-create the {SVGElement*, QualifiedName attributeName} -> SVGSMILElement* map on every frame.

[Philip Rogers]

Created attachment 163985 [details]
First pass

Note: in the first comment I specified the wrong kind of map. It should be HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >.

[WebKit Review Bot]

Comment on attachment 163985 [details]
First pass

Attachment 163985 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13850298

[kov's GTK+ EWS bot]

Comment on attachment 163985 [details]
First pass

Attachment 163985 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/13833962

[Build Bot]

Comment on attachment 163985 [details]
First pass

Attachment 163985 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/13852199

[Gyuyoung Kim]

Comment on attachment 163985 [details]
First pass

Attachment 163985 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/13854188

[Philip Rogers]

Created attachment 163990 [details]
Fix a couple last-minute mistakes that sneaked in.

I guess patches need to compile. Fixed.

[Philip Rogers]

Some benchmark results: http://philbit.com/results.png (left: without patch, right: with patch)

Overall, 10-15% faster.

Depending on how you organize the benchmark you can highlight different areas this patch speeds up (e.g., by a bunch of animations on one element vs a bunch of animations on a bunch of elements) but in my tests the total time in updateAnimations always dropped. In the traces above I used 70 rects with 50 animations on each.

The important parts of the trace results above are:
1) The total time in updateAnimations drops
2) Because we are sorting smaller and partially-sorted arrays, time spent in sortByPriority drops.
3) Because we no longer rebuild the map every frame, we no longer spend any time in HashTableAddResult

Along with these results, on a complex SVG animation demo by an internal team, CPU usage seems to be about 10% lower with the patch.


@Eseidel, I am a little confused about why the total time in SVGSMILElement::progress seems to go up with this patch. I have instrumented the code and verified that it is called the same number of times. I've also examined the individual functions of progress() and they are just higher. Overall the progress() codepaths should not be affected. Could I be misunderstanding the "running time" number?
philbit.com/prepatch_final.trace
philbit.com/postpatch_final.trace

[Eric Seidel (no email)]

Presumably we're actually rendering more frames now?  Do we have an FPS counter for SVG animation we can turn on?

[Eric Seidel (no email)]

Could you email me the sample files?  I'm happy to take a peak.

[Eric Seidel (no email)]

(In reply to comment #7)
> @Eseidel, I am a little confused about why the total time in SVGSMILElement::progress seems to go up with this patch. I have instrumented the code and verified that it is called the same number of times. I've also examined the individual functions of progress() and they are just higher. Overall the progress() codepaths should not be affected. Could I be misunderstanding the "running time" number?
> philbit.com/prepatch_final.trace
> philbit.com/postpatch_final.trace

BAH.  Nm.  I see them there now. :)

[Eric Seidel (no email)]

(In reply to comment #10)
> (In reply to comment #7)
> > @Eseidel, I am a little confused about why the total time in SVGSMILElement::progress seems to go up with this patch. I have instrumented the code and verified that it is called the same number of times. I've also examined the individual functions of progress() and they are just higher. Overall the progress() codepaths should not be affected. Could I be misunderstanding the "running time" number?
> > philbit.com/prepatch_final.trace
> > philbit.com/postpatch_final.trace
> 
> BAH.  Nm.  I see them there now. :)

Actually... I'm not sure how to download a directory from an http listing...

[Philip Rogers]

(In reply to comment #11)
> (In reply to comment #10)
> > (In reply to comment #7)
> > > @Eseidel, I am a little confused about why the total time in SVGSMILElement::progress seems to go up with this patch. I have instrumented the code and verified that it is called the same number of times. I've also examined the individual functions of progress() and they are just higher. Overall the progress() codepaths should not be affected. Could I be misunderstanding the "running time" number?
> > > philbit.com/prepatch_final.trace
> > > philbit.com/postpatch_final.trace
> > 
> > BAH.  Nm.  I see them there now. :)
> 
> Actually... I'm not sure how to download a directory from an http listing...

Oops, OSX has gotten so slick I didn't realize those were directories. Zipped!
philbit.com/traces.zip

[Eric Seidel (no email)]

Wow, the post-patch trace shows a bunch of low-hanging fruit when viewed with inverted callstacks. :)

I'm happy to look at this patch when I'm less tired.  But I'm excited by the idea.

[Philip Rogers]

(In reply to comment #13)
> Wow, the post-patch trace shows a bunch of low-hanging fruit when viewed with inverted callstacks. :)
> 
> I'm happy to look at this patch when I'm less tired.  But I'm excited by the idea.

The fruit is laying on the ground begging to be picked but I wanted to keep this patch small. Followups forthcoming!

[Eric Seidel (no email)]

Comment on attachment 163990 [details]
Fix a couple last-minute mistakes that sneaked in.

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

I think I'm too tired to give a real review.  BUt hopefully these nits will help a little.

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:50
> +    #ifndef NDEBUG

I think #ifndef is normally not indented.  We should scold the stylebot for not complaining. :)

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:81
> +    HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator it = m_scheduledAnimations.find(key);
> +    if (it == m_scheduledAnimations.end()) {
> +        scheduled = new Vector<SVGSMILElement*>();
> +        m_scheduledAnimations.set(key, scheduled);
> +    } else
> +        scheduled = it->second;

I thought there was already a way to get hashmap to allocate values for you if it didnt' find them?  (Obviously you'd have to tell it how...  I could be misremembering.)

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:193
> +    HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator end = m_scheduledAnimations.end();

We might need a typedef for this HashMap and Vector to make this more readable. :)

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:270
> +    for (HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator it = m_scheduledAnimations.begin(); it != end; ++it) {

This is a long block in a long function.  We should probably spend a patch or two making it smaller (splitting out static helper methods, etc.) after this one.

[Philip Rogers]

Created attachment 164305 [details]
Update per reviewer comments

[Philip Rogers]

(In reply to comment #15)
> (From update of attachment 163990 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=163990&action=review
> 
> I think I'm too tired to give a real review.  BUt hopefully these nits will help a little.

Thanks!

> 
> > Source/WebCore/svg/animation/SMILTimeContainer.cpp:50
> > +    #ifndef NDEBUG
> 
> I think #ifndef is normally not indented.  We should scold the stylebot for not complaining. :)

Fixed indentation in the newest patch.

I have also appropriately scolded the stylechecker. After https://bugs.webkit.org/show_bug.cgi?id=96874 I hope the stylechecker will have learned its lesson.

> 
> > Source/WebCore/svg/animation/SMILTimeContainer.cpp:81
> > +    HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator it = m_scheduledAnimations.find(key);
> > +    if (it == m_scheduledAnimations.end()) {
> > +        scheduled = new Vector<SVGSMILElement*>();
> > +        m_scheduledAnimations.set(key, scheduled);
> > +    } else
> > +        scheduled = it->second;
> 
> I thought there was already a way to get hashmap to allocate values for you if it didnt' find them?  (Obviously you'd have to tell it how...  I could be misremembering.)

I looked at our other uses of this pattern and they seem to be similar to the approach I used :( For example, FontCacheWin.cpp. Other uses of HashMap< , Vector*> sometimes used OwnPtr but still followed a similar pattern. BTW, because we use deleteAllValues(m_scheduledAnimations) I don't think OwnPtr is necessary.

I did update the patch to be a little cleaner by using get() instead of find(). This way we check if the returned pointer is null instead of the confusing it == m_scheduledAnimations.end() check.

> 
> > Source/WebCore/svg/animation/SMILTimeContainer.cpp:193
> > +    HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator end = m_scheduledAnimations.end();
> 
> We might need a typedef for this HashMap and Vector to make this more readable. :)

Completely agree and I think it's much cleaner now :)
I went with the following:
    typedef pair<SVGElement*, QualifiedName> ElementAttributePair;
    typedef Vector<SVGSMILElement*> AnimationsVector;
    typedef HashMap<ElementAttributePair, AnimationsVector* > GroupedAnimationsMap;
    GroupedAnimationsMap m_scheduledAnimations;

Having the type name in the typedef (e.g., xyzPair, xyzVector, xyzMap) seems to be how typedefs are handled elsewhere in the codebase.

> 
> > Source/WebCore/svg/animation/SMILTimeContainer.cpp:270
> > +    for (HashMap<ElementAttributePair, Vector<SVGSMILElement*>* >::iterator it = m_scheduledAnimations.begin(); it != end; ++it) {
> 
> This is a long block in a long function.  We should probably spend a patch or two making it smaller (splitting out static helper methods, etc.) after this one.

+1!

[Eric Seidel (no email)]

Comment on attachment 164305 [details]
Update per reviewer comments

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

> Source/WebCore/svg/SVGAnimateElement.cpp:59
> -    
> +

snuck into the diff.

> Source/WebCore/svg/SVGAnimateMotionElement.cpp:92
> +    // AnimateMotion does not use attributeName.

... so it's always valid. (I would have added.) :)

> Source/WebCore/svg/SVGAnimationElement.cpp:572
> -{    
> +{

Snuck in here too.

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:106
> +    startTimer(0);

Why is this done async?

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:278
> +        for (unsigned n = 0; n < size; n++) {
> +            SVGSMILElement* animation = scheduled->at(n);

None of this loop can cause JS to run, or the SVGSMILElement to go away, right?

And the vector itself is protected by your bool, right?  You might want to note these things.

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:315
> +    for (unsigned i = 0; i < animationsToApplySize; ++i)
> +        animationsToApply[i]->applyResultsToTarget();

This can run arbitrary JS, I assume?  But we don't care at this point?  (For example, is the src of an image, script, etc. animateable?  if so, then javascript: urls could execute?)

> Source/WebCore/svg/animation/SVGSMILElement.cpp:245
> +            resetTargetElement(false);

what does false mean?  Should this be an enum?

> Source/WebCore/svg/animation/SVGSMILElement.cpp:256
> +bool SVGSMILElement::hasValidAttributeName()
> +{
> +    return attributeName() != anyQName();
> +}

Why are we using anyQName as a sentinal value?  Should we store this out-of-bounds?  Is it possible for real content to use whatever anyQName resolves to, legitimently?

> Source/WebCore/svg/animation/SVGSMILElement.cpp:610
> +void SVGSMILElement::resetTargetElement(bool resolveNewTarget)

This should be an enum instead of a bool. :)

> Source/WebCore/svg/animation/SVGSMILElement.cpp:618
> +    // Force resolution of target element
> +    if (resolveNewTarget)
> +        targetElement();

Why is this necessary?

[Philip Rogers]

Created attachment 165406 [details]
Address reviewer comments

Thank you for the very detailed review!

[Philip Rogers]

Comment on attachment 164305 [details]
Update per reviewer comments

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

>> Source/WebCore/svg/SVGAnimateElement.cpp:59
>> +
> 
> snuck into the diff.

Fixed

>> Source/WebCore/svg/SVGAnimateMotionElement.cpp:92
>> +    // AnimateMotion does not use attributeName.
> 
> ... so it's always valid. (I would have added.) :)

Fixed

>> Source/WebCore/svg/SVGAnimationElement.cpp:572
>> +{
> 
> Snuck in here too.

Fixed

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:106
>> +    startTimer(0);
> 
> Why is this done async?

This is a great question.

We do this async so that we can queue up multiple changes at once before calling updateAnimations(). Consider "<rect><animate><animate><animate></rect>": if you insert that into the document you want to add all 3 animations before calling updateAnimations. Each of the 3 animation inserts will call notifyIntervalsChanged but, because it is deferred, updateAnimations will only get called once.

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:278
>> +            SVGSMILElement* animation = scheduled->at(n);
> 
> None of this loop can cause JS to run, or the SVGSMILElement to go away, right?
> 
> And the vector itself is protected by your bool, right?  You might want to note these things.

I've added a comment to this effect.

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:315
>> +        animationsToApply[i]->applyResultsToTarget();
> 
> This can run arbitrary JS, I assume?  But we don't care at this point?  (For example, is the src of an image, script, etc. animateable?  if so, then javascript: urls could execute?)

A really good point that I missed. m_preventScheduledAnimationsChanges should be moved down (also duplicated right before the return) so that it protects the vector as well.

This should not run JS at all. It looks like we do not support the SMIL onend/onbegin/onrepeat events nor webkit's css animation events on SVG nodes. If these events were supported they would need to be asynchronous (it looks like the CSS ones for HTML nodes already are). Luckily, for what is animatable, the SVG spec is pretty explicit and it's mostly x/y/width/height, not src/scripts.

Unfortunately in looking into this I discovered that you can animate xlink:href in a <use> which can create/delete the <use> shadow tree's associated <animate> elements. This needs to be addressed and I've assigned myself to https://bugs.webkit.org/show_bug.cgi?id=84657 to do that.

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:245
>> +            resetTargetElement(false);
> 
> what does false mean?  Should this be an enum?

This should be an enum. Fixed.

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:256
>> +}
> 
> Why are we using anyQName as a sentinal value?  Should we store this out-of-bounds?  Is it possible for real content to use whatever anyQName resolves to, legitimently?

I think we should store this out-of-bounds for performance reasons. Mind if I do that as a followup?

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:610
>> +void SVGSMILElement::resetTargetElement(bool resolveNewTarget)
> 
> This should be an enum instead of a bool. :)

Done

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:618
>> +        targetElement();
> 
> Why is this necessary?

This patch requires that we schedule/unschedule if the target or attributeName changes.
targetElement() lazily resolves m_targetElement which complicates this. If we are changing from one target to another, we need to reset the target, unscheduling the animation, and then immediately resolve the target, causing the animation to schedule itself again. If we are removed from the document, we only want to reset the target and unschedule ourselves, but not re-resolve the target and re-schedule; this is why we use the enum.

[Eric Seidel (no email)]

Comment on attachment 165406 [details]
Address reviewer comments

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

This seems reasonable.  I think a few more comments could make this clearer for future hackers in this area.

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:106
> +    startTimer(0);

We should comment here as to why this uses a timer. :)

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:187
> +    m_preventScheduledAnimationsChanges = true;

This will eventually become a RAII I figured. :)

> Source/WebCore/svg/animation/SMILTimeContainer.cpp:264
> +    // This boolean protects against these cases.

It doesn't protect JS from executing, so we should be more clear here. :)  You could set teh eventDispatchForbidden bool if you want that. :)   (that doesn't prevent event dispatch, but will ASSERT if ti happens).

// This boolean will catch any attempts to modify scheduledAnimations during this critical section.... or some such.

> Source/WebCore/svg/animation/SMILTimeContainer.h:96
> +    bool m_preventScheduledAnimationsChanges;

Should this be a static?  s_ instead?

> Source/WebCore/svg/animation/SVGSMILElement.cpp:205
> +        setAttributeName(constructQualifiedName(this, fastGetAttribute(SVGNames::attributeNameAttr)));

Why not just do this at the top like before?

> Source/WebCore/svg/animation/SVGSMILElement.cpp:616
> +    // Force resolution of target element

"Why" is more useful than "what" here.

[Philip Rogers]

Created attachment 165449 [details]
Address reviewer comments (2)

Thank you again for a very thorough review!

[Philip Rogers]

Comment on attachment 165406 [details]
Address reviewer comments

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

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:106
>> +    startTimer(0);
> 
> We should comment here as to why this uses a timer. :)

Done

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:187
>> +    m_preventScheduledAnimationsChanges = true;
> 
> This will eventually become a RAII I figured. :)

Yes! I found a similar pattern in rniwa's eventDispatchForbidden code and helped him land it today :) This should eventually work similarly.

>> Source/WebCore/svg/animation/SMILTimeContainer.cpp:264
>> +    // This boolean protects against these cases.
> 
> It doesn't protect JS from executing, so we should be more clear here. :)  You could set teh eventDispatchForbidden bool if you want that. :)   (that doesn't prevent event dispatch, but will ASSERT if ti happens).
> 
> // This boolean will catch any attempts to modify scheduledAnimations during this critical section.... or some such.

I've updated the comment here. PTAL?

>> Source/WebCore/svg/animation/SMILTimeContainer.h:96
>> +    bool m_preventScheduledAnimationsChanges;
> 
> Should this be a static?  s_ instead?

In this case, no. We can have multiple SMILTimeContainers (one for each SVGSVGElement) and these can run sandboxed in svg-as-image. For example, we could have an animation of a xlink:href that kicks off the loading of a base64'ed SVG image that causes animations in the svg-as-image to run. This flag only protects against modifying this time container's scheduled animations.

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:205
>> +        setAttributeName(constructQualifiedName(this, fastGetAttribute(SVGNames::attributeNameAttr)));
> 
> Why not just do this at the top like before?

This is another great catch. When I was originally writing this patch I had to separate these but eventually they should have been re-combined but I missed this case. I've fixed this.

>> Source/WebCore/svg/animation/SVGSMILElement.cpp:616
>> +    // Force resolution of target element
> 
> "Why" is more useful than "what" here.

Fixed.

[Eric Seidel (no email)]

Comment on attachment 165449 [details]
Address reviewer comments (2)

Very exciting.  I look forward to the follow-ups. :)

[WebKit Review Bot]

Comment on attachment 165449 [details]
Address reviewer comments (2)

Clearing flags on attachment: 165449

Committed r129670: <http://trac.webkit.org/changeset/129670>

[Philip Rogers]

(In reply to comment #25)
> (From update of attachment 165449 [details])
> Clearing flags on attachment: 165449
> 
> Committed r129670: <http://trac.webkit.org/changeset/129670>

Thanks for the really excellent reviews Eric.

Now, off to work on the ~5 followups I've promised :)