Closed
Bug 338580
Opened 19 years ago
Closed 19 years ago
Improve SVG hittesting performance
Categories
(Core :: SVG, defect)
Tracking
()
RESOLVED
FIXED
People
(Reporter: alex, Unassigned)
Details
Attachments
(2 files)
1.93 KB,
patch
|
jwatt
:
review+
tor
:
superreview+
|
Details | Diff | Splinter Review |
513 bytes,
patch
|
jwatt
:
review+
tor
:
superreview+
|
Details | Diff | Splinter Review |
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•19 years ago
|
||
Attachment #222656 -
Flags: superreview?(tor)
Attachment #222656 -
Flags: review?(jwatt)
Reporter | ||
Comment 2•19 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•19 years ago
|
||
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•19 years ago
|
Attachment #222665 -
Flags: superreview?(tor)
Attachment #222665 -
Flags: review+
![]() |
||
Comment 6•19 years ago
|
||
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+
![]() |
||
Comment 7•19 years ago
|
||
BTW I certainly think it's worth opening a bug for further improvements.
Attachment #222665 -
Flags: superreview?(tor) → superreview+
(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 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+
![]() |
||
Comment 10•19 years ago
|
||
Checked in for Alex.
Status: NEW → RESOLVED
Closed: 19 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•