Bug 97905

Summary: [SVG] Update of element referenced by multiple 'use' nodes is absurdly slow
Product: WebKit Reporter: Branimir Lambov <blambov>
Component: SVGAssignee: Florin Malita <fmalita>
Status: RESOLVED FIXED    
Severity: Normal CC: fmalita, krit, pdr, schenney, webkit.review.bot, zimmermann
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 98047    
Bug Blocks:    
Attachments:
Description Flags
Testcase
none
Patch
none
Patch for landing none

Description Branimir Lambov 2012-09-28 06:30:53 PDT
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.
Comment 1 Branimir Lambov 2012-09-28 07:19:25 PDT
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.
Comment 2 Florin Malita 2012-09-28 10:32:44 PDT
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()
Comment 3 Florin Malita 2012-09-28 11:03:36 PDT
There are all kinds of nasty going on here, we're rebuilding the shadow and instance trees waaaay more times than we should.
Comment 4 Nikolas Zimmermann 2012-10-01 01:11:20 PDT
(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.
Comment 5 Florin Malita 2012-10-01 05:59:13 PDT
(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.
Comment 6 Florin Malita 2012-10-02 12:52:50 PDT
Created attachment 166736 [details]
Patch
Comment 7 Florin Malita 2012-10-02 13:02:14 PDT
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).
Comment 8 Dirk Schulze 2013-02-15 23:45:27 PST
Comment on attachment 166736 [details]
Patch

Sounds reasonable. Not sure if it still applies so. r=me.
Comment 9 Florin Malita 2013-02-20 13:01:29 PST
(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!
Comment 10 Florin Malita 2013-02-20 13:03:15 PST
Created attachment 189361 [details]
Patch for landing
Comment 11 Dirk Schulze 2013-02-20 13:25:04 PST
(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. :)
Comment 12 WebKit Review Bot 2013-02-20 13:45:12 PST
Comment on attachment 189361 [details]
Patch for landing

Clearing flags on attachment: 189361

Committed r143498: <http://trac.webkit.org/changeset/143498>
Comment 13 WebKit Review Bot 2013-02-20 13:45:15 PST
All reviewed patches have been landed.  Closing bug.