1368493 - Make TimerThread to keep timers in order

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Comment 1

[Ben Kelly [:bkelly, not reviewing]]

Let's be careful not to lose the benefits from bug 1325254 here.

Also, I think what is really necessary is the ability to answer:

"What is the next soonest normal priority timer for a given target?"

This may not require complete ordering of the list.

Also, its unclear if we need this for all targets, or just for the main thread.

Comment 2

[Ben Kelly [:bkelly, not reviewing]]

In IRC there was talk of making the idle checking method do something like:

1. Copy mTimers list to a temp array
2. Use std::pop_heap in a loop for some small constant number of iterations.

It occurs to me that copying the mTimers list in (1) would probably trigger heap allocation and could be expensive.  We could instead:

1. Create a reasonably sized stack-based AutoTArray
2. Use std::pop_heap on mTimers directly and store in the AutoTArray
3. After we complete the search or hit our limit use std::push_heap to put them back

Depending on what our iteration constant and total length of mTimers, it might be a lot faster to do this than pay the cost of a heap allocation and full copy.

Comment 3

[(no longer active)]

Nice idea, sounds worth trying!

Comment 4

[Ben Kelly [:bkelly, not reviewing]]

Actually, you don't even need the AutoTArray.  You can std::pop_heap to the back of the mTimers array repeatedly with an end iterator that is one shorter each time.  Something like:

  iterator end = mTimers.end();
  while(TIMER_DOES_NOT_MATCH(mTimers[0])) {
    std::pop_heap(mTimers.begin(), end);
    end -= 1;
  }

  // save off the match data

  // put the list back
  while (end != mTimer.end()) {
    end += 1;
    std::push_heap(mTimers.begin(), end);
  }

  // return data

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

oh, I like that, since moving UniquePtrs around is ok, but copying is not.

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Attachment: bkelly's approach

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

Based on some profiling, this seems to behave quite well.

Comment 7

[Ben Kelly [:bkelly, not reviewing]]

Comment on attachment 8873482 [details] [diff] [review]
bkelly's approach

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

::: xpcom/threads/TimerThread.h
@@ +122,5 @@
> +      // the front of the heap.  We want that to be the earliest timer.
> +      return aRight->mTimeout < aLeft->mTimeout;
> +    }
> +
> +    const TimeStamp mTimeout;

I assume the changes in this file are stale and not needed?

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

No. They are needed for DEBUG code.

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Attachment: bkelly's approach v2

I managed to push to try from broken tree.
And I reverted a change to timestamp handling I had made.

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


I think bkelly owns TimerThread these days :)

Comment 10

[Ben Kelly [:bkelly, not reviewing]]

Comment on attachment 8873536 [details] [diff] [review]
bkelly's approach v2

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

Overall looks like its going in a good direction.  r- is for the timeStamp logic bug.  I also would really like to avoid the DEBUG comparison of the entire list since it can grow quite large.

::: xpcom/threads/TimerThread.cpp
@@ +607,3 @@
>  
> +  auto end = mTimers.end();
> +  while(end != mTimers.begin()) {

Maybe do something like this so you can use continue without worrying about the pop_heap/end() dance?

  auto end = mTimers.end();
  auto next = [&] {
    std::pop_heap(mTimers.begin(), end, Entry::UniquePtrLessThan);
    --end
  };

  for (; end != mTimers.begin(); next()) {

@@ +607,5 @@
>  
> +  auto end = mTimers.end();
> +  while(end != mTimers.begin()) {
> +    nsTimerImpl* timer = mTimers[0]->Value();
> +    if (timer) {

if (!timer) {
  continue;
}

We could also actually remove these entries as an optimization here.  We can do that in a later bug, though.

@@ +618,5 @@
> +      // reach the bound or when we find a timer for the current thread.
> +      // This won't give accurate information if we stop before finding
> +      // any timer for the current thread, but at least won't report too
> +      // long idle period.
> +      timeStamp = timer->mTimeout;

I don't think timeStamp is handled correctly here.  Consider searching for a timer with target B and aDefault of t+5.  If you have this list:

0. target A, time t
1. target A, time t+1

You will exit the loop naturally due to hitting the end of the list.  The timeStamp value, however, will be set to t+1 even though it did not match the correct target.  This will then get returned.

I think you should only set timeStamp if you hit your match condition just before you break.  You could also assert timeStamp is aDefault at the top of your loop to make sure this doesn't get messed up.

@@ +621,5 @@
> +      // long idle period.
> +      timeStamp = timer->mTimeout;
> +
> +      // Don't yield to timers created with the *_LOW_PRIORITY type.
> +      if (!timer->IsLowPriority()) {

if (timer->IsLowPriority()) {
  continue;
}

@@ +659,5 @@
> +    MOZ_ASSERT(debugEntries[0]->mTimeout == debugEntries2[0]->mTimeout);
> +    std::pop_heap(debugEntries.begin(), end1, Entry::LessThan);
> +    std::pop_heap(debugEntries2.begin(), end2, Entry::LessThan);
> +    --end1;
> +    --end2;

This DEBUG code to iterate the entire list with pop_heap/push_heap seems very heavy to me.  Yes, its only DEBUG, but we do still need to use DEBUG builds sometimes.

Could we perhaps just verify that mTimers[0] is put back correctly here?

::: xpcom/threads/TimerThread.h
@@ +111,5 @@
>      UniquePtrLessThan(UniquePtr<Entry>& aLeft, UniquePtr<Entry>& aRight)
>      {
>        // This is reversed because std::push_heap() sorts the "largest" to
>        // the front of the heap.  We want that to be the earliest timer.
>        return aRight->mTimeout < aLeft->mTimeout;

Can you make this just call LessThan(aLeft.get(), aRight.get()) so we don't duplicate the actual comparison logic?

@@ +122,5 @@
> +      // the front of the heap.  We want that to be the earliest timer.
> +      return aRight->mTimeout < aLeft->mTimeout;
> +    }
> +
> +    const TimeStamp mTimeout;

Please keep this private and expose a getter or something.  I know this class has a ton of public attributes, but I think we should try to move to a more encapsulated design in the future.

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Ben Kelly [reviewing, but slowly][:bkelly] from comment #10)
> Maybe do something like this so you can use continue without worrying about
> the pop_heap/end() dance?
> 
>   auto end = mTimers.end();
>   auto next = [&] {
>     std::pop_heap(mTimers.begin(), end, Entry::UniquePtrLessThan);
>     --end
>   };
Looks really hard to read, so no thank you :)

> 
> @@ +618,5 @@
> > +      // reach the bound or when we find a timer for the current thread.
> > +      // This won't give accurate information if we stop before finding
> > +      // any timer for the current thread, but at least won't report too
> > +      // long idle period.
> > +      timeStamp = timer->mTimeout;
> 
> I don't think timeStamp is handled correctly here.  Consider searching for a
> timer with target B and aDefault of t+5.  If you have this list:
> 
> 0. target A, time t
> 1. target A, time t+1
> 
> You will exit the loop naturally due to hitting the end of the list.  The
> timeStamp value, however, will be set to t+1 even though it did not match
> the correct target.  This will then get returned.
Yes. That is what the comment says. I kept the old behavior and improved the comment.
We explicitly want to return something less than aDefault if we're about to return early.
But I guess I could set timestamp each time before break; to ease reading.

> 
> This DEBUG code to iterate the entire list with pop_heap/push_heap seems
> very heavy to me.  Yes, its only DEBUG, but we do still need to use DEBUG
> builds sometimes.
> 
I tested this and couldn't see it in the profiles, but I can assert [0] too


> Could we perhaps just verify that mTimers[0] is put back correctly here?
I was wondering that too

> > +    const TimeStamp mTimeout;
> 
> Please keep this private and expose a getter or something.  I know this
> class has a ton of public attributes, but I think we should try to move to a
> more encapsulated design in the future.
It is const and very struct like class... but ok.

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Attachment: v4

Not using lambda, since there isn't really any need.

Comment 13

[Ben Kelly [:bkelly, not reviewing]]

Comment on attachment 8873598 [details] [diff] [review]
v4

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

Thanks!  I guess if someone puts a `continue` in by accident they will hit an infinite loop pretty quickly.

Comment 14

[Ben Kelly [:bkelly, not reviewing]]

Comment on attachment 8873598 [details] [diff] [review]
v4

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

::: xpcom/threads/TimerThread.cpp
@@ +627,5 @@
> +        // Track the currently highest timeout so that we can bail out when we
> +        // reach the bound or when we find a timer for the current thread.
> +        // This won't give accurate information if we stop before finding
> +        // any timer for the current thread, but at least won't report too
> +        // long idle period.

If this is intentional, ok, but I find it very confusing.  If I have a ton of timers scheduled for a worker thread I don't know why it should limit idle time on the main thread.

Comment 15

[Olli Pettay [:smaug][[e-mail]]]

Well we don't want to report too long idle periods.

Comment 16

[Ben Kelly [:bkelly, not reviewing]]

(In reply to Olli Pettay [:smaug] from comment #15)
> Well we don't want to report too long idle periods.

Isn't not reporting an idle period at all (because another thread is busy) equally bad?  If stuff like CC/GC depends on this a worker could cause main thread stuff to eventually OOM.

Comment 17

[Olli Pettay [:smaug][[e-mail]]]

reporting idle period when there isn't such would be against requestIdleCallback spec, I'd say.

Comment 18

[Ben Kelly [:bkelly, not reviewing]]

(In reply to Olli Pettay [:smaug] from comment #17)
> reporting idle period when there isn't such would be against
> requestIdleCallback spec, I'd say.

In theory we were spec compliant before we looked at nsITimer list at all, right?

Anyway, not asking you to change it.  Just unexpected to me.

Comment 19

[Olli Pettay [:smaug][[e-mail]]]

Attachment: timerthread_v3_5.diff

+ a test fix, since the patch changed low priority handling.
https://treeherder.mozilla.org/#/jobs?repo=try&revision=3aab9b0e78ffd861b8785dde4e7ab234269030d3

Let's see if I have other stuff to fix too :/

Comment 20

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3efb0fe88029
TimerThread::FindNextFireTimeForCurrentThread should look at timers in order, r=bkelly

Comment 21

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

https://hg.mozilla.org/mozilla-central/rev/3efb0fe88029