338580 - Improve SVG hittesting performance

Status: RESOLVED FIXED

(Core :: SVG, defect)

Description

[Alex Fritze]

Traversing frames in reverse order for hittesting, rather than hittesting each and every frame seems to give quite a dramatic performance improvement.
Patch coming up.

Comment 1

[Alex Fritze]

Attachment: patch v1

Comment 2

[Alex Fritze]

So the win of the reverse frame traversal patch is not as great as I initially thought :-(

Tor came up with another idea: Implementing an early reject test for glyph geometries (as already implemented for path geometries). This seems to help a little bit more, but I still see a strong correlation of decreasing hittesting performance with the number of svg objects in a document.

Patch coming up.

Comment 3

[Alex Fritze]

Attachment: reject test for glyph geometries

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It seems to me that stopping when you hit the frame traversing backwards in general is still going to take 1/2 the time of a full traversal, in general. (Actually a bit less since frames late in the tree are more likely to be on top.)

A slightly cleaner and simpler way to do it would be to fill an nsAutoVoidArray with the child list and traverse it from back to front. In-place list reversal is cool but a bit over-clever IMHO :-).

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The only way to really nail this problem is to somehow avoid testing whole subtrees of a document. In regular frame-land we have access to the bounding box of each frame subtree.

So one way to deal with this would be to have nsSVGFrame::GetBBox cache the bbox on the frame (as a property). Invalidating it when necessary might be hard, I don't know. Then during event processing you call GetBBox on a frame before descending into it. Thus the first event would be slower but subsequent events without geometry changes (common for mousemoves, I guess) would be fast.

Comment 6

[Jonathan Watt [:jwatt]]

Comment on attachment 222656 [details] [diff] [review]
patch v1

(In reply to comment #4)
> A slightly cleaner and simpler way to do it would be to fill an nsAutoVoidArray
> with the child list and traverse it from back to front. In-place list reversal
> is cool but a bit over-clever IMHO :-).

I agree it would be cleaner, but using list reversal we can be sure there won't be any time wasted or heap churn when the number of siblings is more than seven.

This is a significant improvement in performance. For example, without this patch I can get http://jwatt.org/svg/tmp/removeChild.svg to freeze up relatively easily. With it, I can't get it to freeze, however hard I try. And some large SVGs have a *lot* more elements than are added by mousemoves in that demo.

So r=jwatt

Comment 7

[Jonathan Watt [:jwatt]]

BTW I certainly think it's worth opening a bug for further improvements.

Comment 8

[tor]

(In reply to comment #6)
> (From update of attachment 222656 [details] [diff] [review] [edit])
> (In reply to comment #4)
> > A slightly cleaner and simpler way to do it would be to fill an nsAutoVoidArray
> > with the child list and traverse it from back to front. In-place list reversal
> > is cool but a bit over-clever IMHO :-).
> 
> I agree it would be cleaner, but using list reversal we can be sure there won't
> be any time wasted or heap churn when the number of siblings is more than
> seven.

One possibility might be to use a nsVoidArray instead, and set the initial size to mFrameList.Count().  That would guarantee a constant amount of heap churn. :)

Comment 9

[tor]

Comment on attachment 222656 [details] [diff] [review]
patch v1

Top comment should also state that the frame has an inconsistent state during this flipping, as it will think it only has a single child after the pointers are flipped.

Comment 10

[Jonathan Watt [:jwatt]]

Checked in for Alex.