Improve SVG hittesting performance

RESOLVED FIXED

Status

()

RESOLVED FIXED
13 years ago
13 years ago

People

(Reporter: alex, Unassigned)

Tracking

Trunk
x86
Windows XP
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

(Reporter)

Description

13 years ago
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.
(Reporter)

Comment 1

13 years ago
Created attachment 222656 [details] [diff] [review]
patch v1
Attachment #222656 - Flags: superreview?(tor)
Attachment #222656 - Flags: review?(jwatt)
(Reporter)

Comment 2

13 years ago
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.
(Reporter)

Comment 3

13 years ago
Created attachment 222665 [details] [diff] [review]
reject test for glyph geometries
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 :-).
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.

Updated

13 years ago
Attachment #222665 - Flags: superreview?(tor)
Attachment #222665 - Flags: review+
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
Attachment #222656 - Flags: review?(jwatt) → review+
BTW I certainly think it's worth opening a bug for further improvements.

Updated

13 years ago
Attachment #222665 - Flags: superreview?(tor) → superreview+

Comment 8

13 years ago
(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

13 years ago
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.
Attachment #222656 - Flags: superreview?(tor) → superreview+
Checked in for Alex.
Status: NEW → RESOLVED
Last Resolved: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.