1336822 - Optimize ResetTimersForThrottleReduction

Status: RESOLVED FIXED

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

Description

[Ben Kelly [:bkelly, not reviewing]]

Currently ResetTimersForThrottleReduction() re-inserts every timer it modifies.  This makes the algorithm O(n^2).  In most cases, though, we will be shifting a lot of timers by the same amount and the order won't change.  We can optimize for this case to avoid large pauses due to re-sorting.

Comment 1

[Ben Kelly [:bkelly, not reviewing]]

Attachment: Optimize ResetTimesForTHrottleReduction() for common case. r=ehsan

Ehsan, while testing my time-flood case here:

https://people-mozilla.org/~bkelly/timer-flood/index.html

I am seeing massive main thread jank due to ResetTimersForThrottleReduction().  This algorithm is O(n^2) due to its re-insertion of every modified timer.  I think we can avoid a lot of this work, though, because in the common case we will be shifting large blocks of timers in the same direction.

This patch only does the re-insertion if we detect that the order actually changed.  This completely removes the jank from this method in that test case for me.

Comment 2

[Ben Kelly [:bkelly, not reviewing]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=f0ee317478e49add8e1876536fe60e312b6211e0

Comment 3

[Ben Kelly [:bkelly, not reviewing]]

I would like to uplift this to FF52 if possible.

Comment 4

[Ben Kelly [:bkelly, not reviewing]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=b95dbbbd1873975f216790dba4a26ee3470b38b3

Comment 5

[(no longer active)]

Comment on attachment 8833784 [details] [diff] [review]
Optimize ResetTimesForTHrottleReduction() for common case. r=ehsan

Review of attachment 8833784 [details] [diff] [review]:
-----------------------------------------------------------------

Nice!

Comment 6

[Ben Kelly [:bkelly, not reviewing]]

Also note that we run this code on tab switch when a window is brought back into the foreground.  So it could benefit some of our top line metrics.

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ce9071b29a86
Optimize ResetTimesForTHrottleReduction() for common case. r=ehsan

Comment 8

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/ce9071b29a86

Comment 9

[Ben Kelly [:bkelly, not reviewing]]

Comment on attachment 8833784 [details] [diff] [review]
Optimize ResetTimesForTHrottleReduction() for common case. r=ehsan

Approval Request Comment
[Feature/Bug causing the regression]: This is an additional change to realize the benefits of bugs 1300659.  I'd like to write a blog post about our timer improvements in FF52 and I need this patch for the demonstration to work well.
[User impact if declined]: Reduced jank when there are large numbers of timers and the user switches tabs, etc.
[Is this code covered by automated tests?]: We have extensive tests that trigger this code.
[Has the fix been verified in Nightly?]: This patch has been in nightly for a week without problem.
[Needs manual test from QE? If yes, steps to reproduce]:  None
[List of other uplifts needed for the feature/fix]: None
[Is the change risky?]: Low risk
[Why is the change risky/not risky?]: The patch has been proven on nightly and is quite small.  It simply avoids re-inserting data into a list if we can determine that the order did not actually change.
[String changes made/needed]: None

Comment 10

[Ben Kelly [:bkelly, not reviewing]]

Note, the patch will need a rebase since the code moved from nsGlobalWindow.cpp to TimeoutManager.cpp in FF53 or FF54.  I'll handle this if the uplift is approved.

Comment 11

[Liz Henry (:lizzard) (relman/hg->git project)]

Comment on attachment 8833784 [details] [diff] [review]
Optimize ResetTimesForTHrottleReduction() for common case. r=ehsan

Another small fix for timer issues, Probably this will miss the build for beta 6 but can still make it to beta 7 later this week.

Comment 12

[Ben Kelly [:bkelly, not reviewing]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/a453af7168f3

Comment 13

[Ben Kelly [:bkelly, not reviewing]]

https://hg.mozilla.org/releases/mozilla-beta/rev/bd9cd325c4bca4a9f0256d9300c7ac00dd9bf7a8

Comment 14

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr52/rev/bd9cd325c4bc

Comment 15

[Andrei Vaida [:avaida]]

Setting qe-verify- based on Comment 9.