Make TimerThread to keep timers in order

RESOLVED FIXED in Firefox 55

Status

()

enhancement
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: smaug, Assigned: smaug)

Tracking

(Depends on 2 bugs)

unspecified
mozilla55
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(2 attachments, 2 obsolete attachments)

Assignee

Description

2 years ago
No description provided.
Assignee

Updated

2 years ago
Blocks: 1311425
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.
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

2 years ago
Nice idea, sounds worth trying!
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
Assignee

Comment 5

2 years ago
oh, I like that, since moving UniquePtrs around is ok, but copying is not.
Assignee

Comment 6

2 years ago
Posted patch bkelly's approach (obsolete) — Splinter Review
https://treeherder.mozilla.org/#/jobs?repo=try&revision=fdeeabf7fac7158d1d018ea4fa391bc8d2b57331

Based on some profiling, this seems to behave quite well.
Assignee: nobody → bugs
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?
Assignee

Comment 8

2 years ago
No. They are needed for DEBUG code.
Assignee

Comment 9

2 years ago
Posted patch bkelly's approach v2 (obsolete) — Splinter Review
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 :)
Attachment #8873482 - Attachment is obsolete: true
Attachment #8873536 - Flags: review?(bkelly)
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.
Attachment #8873536 - Flags: review?(bkelly) → review-
Assignee

Comment 11

2 years ago
(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.
Assignee

Comment 12

2 years ago
Posted patch v4Splinter Review
Not using lambda, since there isn't really any need.
Attachment #8873536 - Attachment is obsolete: true
Attachment #8873598 - Flags: review?(bkelly)
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.
Attachment #8873598 - Flags: review?(bkelly) → review+
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.
Assignee

Comment 15

2 years ago
Well we don't want to report too long idle periods.
(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.
Assignee

Comment 17

2 years ago
reporting idle period when there isn't such would be against requestIdleCallback spec, I'd say.
(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.
Assignee

Comment 19

2 years ago
+ 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

2 years ago
Pushed by opettay@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3efb0fe88029
TimerThread::FindNextFireTimeForCurrentThread should look at timers in order, r=bkelly

Comment 21

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/3efb0fe88029
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Depends on: 1373062
You need to log in before you can comment on or make changes to this bug.