Bug 97905 – [SVG] Update of element referenced by multiple 'use' nodes is absurdly slow

• Component: SVG
• Status: RESOLVED FIXED

[Branimir Lambov]

Created attachment 166239 [details]
Testcase

The attached SVG animation contains an unit element that is used to draw a few hundred triangles by a hierarchy of 'use' nodes. 

The file animates the scale attribute of the unit element. This results in an update that takes tens of second for a single frame (i.e. on the order of 1/10 s for each triangle drawn!).

Tested on Chrome Linux + MacOS and Safari MacOS, all have the problem.


Opera runs this animation at 50 fps. Internet Explorer also does this smoothly.

[Branimir Lambov]

Additionally, if you leave the 'qqqqq' definition unused (e.g. by changing line 51 to refer to '#qqq' instead), the file's performance will not improve.

[Florin Malita]

This has the same profile as https://bugs.webkit.org/show_bug.cgi?id=97910, so I suspect it's the same problem:

+   3.81%  SignalSender  libpthread-2.15.so  [.] pthread_mutex_lock
+   3.65%  SignalSender  libpthread-2.15.so  [.] pthread_mutex_unlock
+   1.79%  SignalSender  libwebkit.so        [.] WTF::StringHasher::addCharactersToHash(unsigned short, unsigned short)
+   1.49%  SignalSender  libwebkit.so        [.] WTF::Locker<WTF::Mutex>::Locker(WTF::Mutex&)
+   1.39%  SignalSender  libwebkit.so        [.] WTF::intHash(unsigned long)
+   1.34%  SignalSender  libwebkit.so        [.] WTF::OwnPtr<WTF::Mutex>::operator*() const
+   1.03%  SignalSender  libwebkit.so        [.] WebCore::Node::getFlag(WebCore::Node::NodeFlags) const
+   1.01%  SignalSender  libwebkit.so        [.] WTF::Mutex::lock()
+   0.92%  SignalSender  libpthread-2.15.so  [.] pthread_getspecific
+   0.92%  SignalSender  libwebkit.so        [.] WTF::ThreadRestrictionVerifier::isSafeToUse() const
+   0.81%  SignalSender  libwebkit.so        [.] unsigned int WTF::StringHasher::computeHashAndMaskTop8Bits<unsigned short, &(WTF::StringHasher::defaultConverter(unsigned short))>(
+   0.78%  SignalSender  chrome              [.] (anonymous namespace)::FL_Previous_No_Check(void*)
+   0.69%  SignalSender  chrome              [.] PackedCache<36, unsigned long>::GetOrDefault(unsigned long, unsigned long) const
+   0.68%  SignalSender  libwebkit.so        [.] WTF::RefPtr<WTF::StringImpl>::get() const
+   0.67%  SignalSender  libwebkit.so        [.] WTF::currentThread()
+   0.61%  SignalSender  libwebkit.so        [.] WTF::Mutex::unlock()
+   0.58%  SignalSender  chrome              [.] base::subtle::Acquire_Load(long const volatile*)
+   0.57%  SignalSender  libwebkit.so        [.] WTF::ThreadIdentifierData::identifier()
+   0.56%  SignalSender  libwebkit.so        [.] WTF::StringHasher::defaultConverter(unsigned short)
+   0.56%  SignalSender  libwebkit.so        [.] WebCore::Node::document() const
+   0.55%  SignalSender  chrome              [.] TCMalloc_PageMap3<36>::get(unsigned long) const
+   0.55%  SignalSender  libwebkit.so        [.] WTF::RefCountedBase::derefBase()
+   0.53%  SignalSender  libwebkit.so        [.] WTF::RefCountedBase::ref()
+   0.53%  SignalSender  libwebkit.so        [.] WTF::Locker<WTF::Mutex>::~Locker()

[Florin Malita]

There are all kinds of nasty going on here, we're rebuilding the shadow and instance trees waaaay more times than we should.

[Nikolas Zimmermann]

(In reply to comment #3)
> There are all kinds of nasty going on here, we're rebuilding the shadow and instance trees waaaay more times than we should.


            <g id="unit">
		<polygon points="0,0 10,0 5,8.66025403784439"/>	    
	    </g>


            unit.setAttribute('transform', 'scale(' + (Math.abs(f%20-10)/10) + ')');

This causes all instance & shadow trees of all the <use> elements referencing "unit" to be rebuilt.
If this would use <animateTransform> exactly this kind of cloning is suppressed. An SVGAnimateTransformElement knows how to update all instances without having to rebuild/reclone.

Unfortunately I have zero time at the moment for large patches, what we really want to assure:
- Only rebuild shadow/dom trees if the DOM is mutated by insertions or removal.
- Never rebuild the trees for attribute changes, we can always find all instances of a cloned element and propagate updates to them for both XML DOM (setAttribute) and SVG DOM (foo.x.baseVal.value=..) changes.

This would fix the root of these problems.

[Florin Malita]

(In reply to comment #4)
> - Only rebuild shadow/dom trees if the DOM is mutated by insertions or removal.
> - Never rebuild the trees for attribute changes, we can always find all instances of a cloned element and propagate updates to them for both XML DOM (setAttribute) and SVG DOM (foo.x.baseVal.value=..) changes.
> 
> This would fix the root of these problems.

Agreed, these are good ideas Niko and they should greatly improve use performance.

In this bug/example, there's a particularly bad interaction going on on top of the expensive tree rebuild: rebuilding dependent use trees is recursive, causing many unnecessary updates that just get thrown away.

Say we have L groups containing N use elements each, and each use in L depends on all other uses in L-1 (in the example L = 5 and N = 4), and all uses in group0 depend on some element. If the element is updated, we start rebuilding use0 in group0 and then we're immediately rebuilding all dependent uses in group1 (which propagates recursively all the way). Then we move on to use1, and again invalidate and rebuild all the uses in group1 and so on. That introduces a N^L factor for this kind of setup because we're not rebuilding the trees in topological (sorted use-dependency) order.

I believe this should not be too hard to address if we have a separate (recursive) invalidation phase and a non-recursive rebuild phase. I'm playing with it right now, hope to have something working in the next days.

[Florin Malita]

Created attachment 166736 [details]
Patch

[Florin Malita]

The patch doesn't address the general slowness of <use> shadow/instance tree rebuilds (will focus on that in https://bugs.webkit.org/show_bug.cgi?id=97910), but it removes many redundant updates triggered by this test (on my workstation it increases the framerate from ~0.04fps to ~9.5fps).

[Dirk Schulze]

Comment on attachment 166736 [details]
Patch

Sounds reasonable. Not sure if it still applies so. r=me.

[Florin Malita]

(In reply to comment #8)
> (From update of attachment 166736 [details])
> Sounds reasonable. Not sure if it still applies so. r=me.

Yes, this is still relevant. Thanks!

[Florin Malita]

Created attachment 189361 [details]
Patch for landing

[Dirk Schulze]

(In reply to comment #9)
> (In reply to comment #8)
> > (From update of attachment 166736 [details] [details])
> > Sounds reasonable. Not sure if it still applies so. r=me.
> 
> Yes, this is still relevant. Thanks!

If the patch still applies to ToT. :)

[WebKit Review Bot]

Comment on attachment 189361 [details]
Patch for landing

Clearing flags on attachment: 189361

Committed r143498: <http://trac.webkit.org/changeset/143498>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.