1787974 - Rework TImerThread's timer storage to allow in-order access

Status: RESOLVED FIXED

(Core :: XPCOM, task)

Description

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

TimerThread::mTimers is currently an array of unique pointers to Entry's, managed as a binary heap (with std::push_heap and std::pop_heap, such that the first element always has the earliest timeout).
This arrangement was implemented in bug 1325254, and makes adding timers very fast, but makes it difficult to look at multiple timers in order, which will be needed when trying to coalesce timers in bug 1783405.

This bug intends to change mTimers into a sorted array of entries.
I will attach the current WIP soon, but I won't have the time to finish it together with bug 1783405 (it doesn't make much sense to do one without the other.)

Testing it showed that the overall speed was pretty much the same.
While adding elements in a sorted array is intuitively slower than using std::push_heap, this was effectively balanced by a number of factors:

• The list is generally fairly small, tens to around 100 elements at times, so linear access is fast on modern CPUs thanks to cache locality and prefetching.
• Storing entries instead of pointers to on-memory-heap entries, saving lots of (de)allocations and indirections.
• Removing timers is done by nulling a pointer in entries, and when adding we can reuse these "empty" entries (either directly, or when inserting and therefore moving elements to the right until the first empty entry), resulting in few element moves in practice.

Comment 1

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - ***OPTIONAL PATCH*** Add waiting/added-first/notified to marker in TimerThread::AddTimer

This adds more information in the "AddTimer" markers, about the internal state
of the TimerThread when adding each timer.

Comment 2

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - ***OPTIONAL PATCH*** Better marker for TimerThread::RemoveTimer -

Also both AddTimer and RemoveTimer markers now show the duration of these
function calls.

Depends on D155932

Comment 3

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Only nsTimerImplHolder::Forget needs to be public -

Depends on D155933

Comment 4

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Style: Put Entry private section at the bottom of the class -

Depends on D155934

Comment 5

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Do a linear search in RemoveTimerInternal to stop going through the holder -

Note that it's about 4 times slower in practice! But this will be balanced in later patches.

Depends on D155935

Comment 6

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - nsTimerImpl directly keeps track of whether it's in a TimerThread::Entry -

nsTimerImplHolder can now be removed.

Depends on D155936

Comment 7

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - TimerThread stores Entry's instead of UniquePtrs to Entry's -

This removes memory heap allocations and deallocations, and indirections to access entries.

Depends on D155937

Comment 8

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Entry constructor only takes an nsTimerImpl* -

So entries now store the given timeout value (instead of clamping it to after "now").
And we store this timeout first, as it's accessed more frequently.

Depends on D155938

Comment 9

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Entry::Forget doesn't need a parameter -

Depends on D155939

Comment 10

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - In TimerThread::Shutdown, only Take non-null entries -

Depends on D155940

Comment 11

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - Changing mTimers from heap to timestamp-sorted array -

Inserting elements in the sorted array is more costly than pushing to a binary
heap, but this is balanced by the removal of indirections and de/allocations,
and the upcoming re-use of empty entries.

In the end, this change is necessary to allow future improvements like timer-
coalescing, where we'll need to see multiple timers in order.

Bonus: FindNextFireTimeForCurrentThread changes a lot, because it used to have
to pop_heap elements and then push_heap them back! (Sometimes resulting in
subtle changes for timers with the same timeout.) So this one benefits the
most.

Depends on D155941

Comment 12

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - AddTimerInternal efficiently inserts by shifting entries until next gap -

This makes the code more complex, but it is needed to keep this most-used
function efficient related to its old implementation using std::push_heap.

Depends on D155942

Comment 13

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Attachment: WIP: Bug 1787974 - ***OPTIONAL PATCH*** Markers timer added->removed and removed->run -

This adds some valuable markers showing the times from adding to dispatching a
timer, and then from dispatching to actually running the timer code.

Depends on D155943

Comment 14

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

Time is almost up for me, so I won't have time to progress this further myself. Happy to answer any questions though.
Good continuation, I hope this proves to be useful.

Comment 15

[Justin Link]

Attachment: WIP: Bug 1787974 - Add waiting/added-first/notified to marker in TimerThread::AddTimer

This adds more information in the "AddTimer" markers, about the internal state
of the TimerThread when adding each timer.

Comment 16

[Justin Link]

Attachment: WIP: Bug 1787974 - Better marker for TimerThread::RemoveTimer

Also both AddTimer and RemoveTimer markers now show the duration of these
function calls.

Depends on D164281

Comment 17

[Justin Link]

Attachment: Bug 1787974 - Only nsTimerImplHolder::Forget needs to be public r=florian,smaug

Depends on D164282

Comment 18

[Justin Link]

Attachment: Bug 1787974 - Style: Put Entry private section at the bottom of the class r=florian,smaug

Depends on D164283

Comment 19

[Justin Link]

Attachment: Bug 1787974 - Do a linear search in RemoveTimerInternal to stop going through the holder r=florian,smaug

Note that it's about 4 times slower in practice! But this will be balanced in later patches.

Depends on D164284

Comment 20

[Justin Link]

Attachment: Bug 1787974 - nsTimerImpl directly keeps track of whether it's in a TimerThread::Entry r=florian,smaug

nsTimerImplHolder can now be removed.

Depends on D164285

Comment 21

[Justin Link]

Attachment: Bug 1787974 - TimerThread stores Entry's instead of UniquePtrs to Entry's r=florian,smaug

This removes memory heap allocations and deallocations, and indirections to access entries.

Depends on D164286

Comment 22

[Justin Link]

Attachment: Bug 1787974 - Entry constructor only takes an nsTimerImpl* r=florian,smaug

So entries now store the given timeout value (instead of clamping it to after "now").
And we store this timeout first, as it's accessed more frequently.

Depends on D164287

Comment 23

[Justin Link]

Attachment: Bug 1787974 - Entry::Forget doesn't need a parameter r=florian,smaug

Depends on D164288

Comment 24

[Justin Link]

Attachment: Bug 1787974 - In TimerThread::Shutdown, only Take non-null entries r=florian,smaug

Depends on D164289

Comment 25

[Justin Link]

Attachment: Bug 1787974 - Changing mTimers from heap to timestamp-sorted array r=florian,smaug

Inserting elements in the sorted array is more costly than pushing to a binary
heap, but this is balanced by the removal of indirections and de/allocations,
and the upcoming re-use of empty entries.

In the end, this change is necessary to allow future improvements like timer-
coalescing, where we'll need to see multiple timers in order.

Bonus: FindNextFireTimeForCurrentThread changes a lot, because it used to have
to pop_heap elements and then push_heap them back! (Sometimes resulting in
subtle changes for timers with the same timeout.) So this one benefits the
most.

Depends on D164290

Comment 26

[Justin Link]

Attachment: Bug 1787974 - AddTimerInternal efficiently inserts by shifting entries until next gap r=florian,smaug

This makes the code more complex, but it is needed to keep this most-used
function efficient related to its old implementation using std::push_heap.

Depends on D164291

Comment 27

[Justin Link]

Attachment: WIP: Bug 1787974 - Markers timer added->removed and removed->run

This adds some valuable markers showing the times from adding to dispatching a
timer, and then from dispatching to actually running the timer code.

Depends on D164292

Comment 28

[Justin Link]

Attachment: Bug 1787974 - Fixed problem where AddTimerInternal() could add a new timer in the wrong spot. r=florian,smaug

Depends on D164293

Comment 29

[Justin Link]

Attachment: Bug 1787974 - Fixed small logic change in FindNextFireTimeForCurrentThread(). r=smaug

I also took a stab at documenting the behavior since I found it a bit
difficult to follow.

Depends on D164294

Comment 30

[Justin Link]

Attachment: Bug 1787974 - Remove leading canceled timers before deciding if we added a new front timer r=smaug,florian

Due to the possible presence of canceled timers at the "front" of the
list, mTimers[0] won't necessarily hold the next timer to be fired
unless we've cleaned up those front timers recently.

Comment 31

[Justin Link]

Try run with the current patch stack: https://treeherder.mozilla.org/jobs?revision=eba0461bc280f88e1d42ff0a95e45468542517ad&repo=try (seems good to me)

Comment 32

[Justin Link]

Olli, Florian: I've moved the three changes with the "top" of the stack and made sure that each change in the new stack compiles (with its dependent changes). I've also now disconnected the profiling changes from the rest of the stack as well.

It looks like all of the non-profiling changes have been approved so I'll probably try to land this a little later today unless you let me know and want to take one last look first. (I think I still have a few code review comments to respond to/close also.)

Comment 33

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/e22855795b9f
Only nsTimerImplHolder::Forget needs to be public r=smaug
https://hg.mozilla.org/integration/autoland/rev/aad44174c4bf
Style: Put Entry private section at the bottom of the class r=smaug
https://hg.mozilla.org/integration/autoland/rev/5d58bb968292
Do a linear search in RemoveTimerInternal to stop going through the holder r=smaug
https://hg.mozilla.org/integration/autoland/rev/b70b44f7828f
nsTimerImpl directly keeps track of whether it's in a TimerThread::Entry r=smaug
https://hg.mozilla.org/integration/autoland/rev/248126e639c3
TimerThread stores Entry's instead of UniquePtrs to Entry's r=smaug
https://hg.mozilla.org/integration/autoland/rev/cc9b47f124a8
Entry constructor only takes an nsTimerImpl* r=smaug
https://hg.mozilla.org/integration/autoland/rev/6603be788d60
Entry::Forget doesn't need a parameter r=smaug
https://hg.mozilla.org/integration/autoland/rev/4c8d9ee64409
In TimerThread::Shutdown, only Take non-null entries r=smaug
https://hg.mozilla.org/integration/autoland/rev/115dff277414
Changing mTimers from heap to timestamp-sorted array r=smaug
https://hg.mozilla.org/integration/autoland/rev/facb9344bb5d
AddTimerInternal efficiently inserts by shifting entries until next gap r=smaug
https://hg.mozilla.org/integration/autoland/rev/f1f071954863
Fixed problem where AddTimerInternal() could add a new timer in the wrong spot. r=smaug
https://hg.mozilla.org/integration/autoland/rev/199888078547
Fixed small logic change in FindNextFireTimeForCurrentThread(). r=smaug
https://hg.mozilla.org/integration/autoland/rev/3e5c9fa28ebb
Remove leading canceled timers before deciding if we added a new front timer r=smaug

Comment 34

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/e22855795b9f
https://hg.mozilla.org/mozilla-central/rev/aad44174c4bf
https://hg.mozilla.org/mozilla-central/rev/5d58bb968292
https://hg.mozilla.org/mozilla-central/rev/b70b44f7828f
https://hg.mozilla.org/mozilla-central/rev/248126e639c3
https://hg.mozilla.org/mozilla-central/rev/cc9b47f124a8
https://hg.mozilla.org/mozilla-central/rev/6603be788d60
https://hg.mozilla.org/mozilla-central/rev/4c8d9ee64409
https://hg.mozilla.org/mozilla-central/rev/115dff277414
https://hg.mozilla.org/mozilla-central/rev/facb9344bb5d
https://hg.mozilla.org/mozilla-central/rev/f1f071954863
https://hg.mozilla.org/mozilla-central/rev/199888078547
https://hg.mozilla.org/mozilla-central/rev/3e5c9fa28ebb