Closed
Bug 1368493
Opened 7 years ago
Closed 7 years ago
Make TimerThread to keep timers in order
Categories
(Core :: XPCOM, enhancement)
Core
XPCOM
Tracking
()
RESOLVED
FIXED
mozilla55
Tracking | Status | |
---|---|---|
firefox55 | --- | fixed |
People
(Reporter: smaug, Assigned: smaug)
References
Details
Attachments
(2 files, 2 obsolete files)
(deleted),
patch
|
bkelly
:
review+
|
Details | Diff | Splinter Review |
(deleted),
patch
|
Details | Diff | Splinter Review |
No description provided.
Comment 1•7 years ago
|
||
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•7 years ago
|
||
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 4•7 years ago
|
||
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•7 years ago
|
||
oh, I like that, since moving UniquePtrs around is ok, but copying is not.
Assignee | ||
Comment 6•7 years ago
|
||
https://treeherder.mozilla.org/#/jobs?repo=try&revision=fdeeabf7fac7158d1d018ea4fa391bc8d2b57331 Based on some profiling, this seems to behave quite well.
Assignee: nobody → bugs
Comment 7•7 years ago
|
||
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 9•7 years ago
|
||
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 10•7 years ago
|
||
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•7 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•7 years ago
|
||
Not using lambda, since there isn't really any need.
Attachment #8873536 -
Attachment is obsolete: true
Attachment #8873598 -
Flags: review?(bkelly)
Comment 13•7 years ago
|
||
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 14•7 years ago
|
||
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 16•7 years ago
|
||
(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•7 years ago
|
||
reporting idle period when there isn't such would be against requestIdleCallback spec, I'd say.
Comment 18•7 years ago
|
||
(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•7 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•7 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•7 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/3efb0fe88029
Status: NEW → RESOLVED
Closed: 7 years ago
status-firefox55:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
You need to log in
before you can comment on or make changes to this bug.
Description
•