352750 - [FIX]Exponential growth in number of timeouts hangs browser in InsertTimeoutIntoList

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect, P3)

Description

[Boris Zbarsky [:bzbarsky]]

See bug 351818 comment 6.

The basic issue I ran into there is that InsertTimeoutIntoList makes inserting a timeout O(N) in number of existing timeouts, with the worst case (walking the whole list) being very common in situations where we're setting a bunch of timeouts of the same duration.

Could we perhaps use a PRCList and walk backwards from the end instead?  That should at least help a little bit.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Note:  This is not a duplicate of bug 261633.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: non-PRCList patch

One possible approach.  Doesn't use PRCList yet, but I think I figured out how to do that, so it's coming up.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: With PRCList

I had to move the nsTimeout struct decl because otherwise I couldn't implement nsGlobalWindow::GetFirstTimeout and GetLastTimeout.

Comment 4

[Brendan Eich [:brendan]]

It'll be interesting to get results from a number of testcases to see whether searching from the end wins.  If not, time for a log(n) heap.

/be

Comment 5

[Boris Zbarsky [:bzbarsky]]

Brendan, searching from end wins any time the overwhelming majority of timeouts all have the same delay (since in that case we want to add to the end of the timeouts that have that delay).  For typical sites, I believe this is the case; it's pretty rare to have a multimodal delay distribution any time you have lots of timers going, because lots of timers pretty much always means they're created as part of some sort of animation package and you tend to keep animations synchronized...

Comment 6

[Brendan Eich [:brendan]]

bz: yeah, I sure hope this is enough, and agree that it ought to be.  Good to see PRClist mixed in.

/be

Comment 7

[Johnny Stenback (:jst)]

Comment on attachment 238712 [details] [diff] [review]
With PRCList

- In nsGlobalWindow.h:

+struct nsTimeout : PRCList
+{
+  nsTimeout()
+  {
...

This'll break on Win32 with VC6 IIRC. You can't have inline ctors or dtors in a class that uses nsRefPtr or nsCOMPtr members of incomplete types. You'll need to uninline the nsTimeout ctor and dtor.

+  nsTimeout* Next() {
+    // Note: might not actually return an nsTimeout.  Use IsTimeout to check.
+    return NS_STATIC_CAST(nsTimeout*, PR_NEXT_LINK(this));
+  }

Maybe it'd be worth changing nsTimeout to be a class and make the inheritance of PRCList private to ensure people use these helpers etc?

Other than that I can't seem to find anything wrong with this patch, so...

r+sr=jst

Comment 8

[Boris Zbarsky [:bzbarsky]]

> This'll break on Win32 with VC6 IIRC

Good catch.  Will fix.

> make the inheritance of PRCList private

Then things like

   PR_INSERT_AFTER(aTimeout, prevSibling);

won't compile.  I could probably fix that by exposing methods on nsTimeout, but the following code:

  +    return NS_STATIC_CAST(nsTimeout*, PR_LIST_HEAD(&mTimeouts));

won't compile anyway, since it's in nsGlobalWindow.  I'd have to make nsGlobalWindow a friend of nsTimeout, but that negates the point of having private inheritance...

Comment 9

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comments and tip

Comment 10

[Boris Zbarsky [:bzbarsky]]

Checked in.