Closed Bug 1067989 Opened 5 years ago Closed 5 years ago

Unify some more binary search uses

Categories

(Core :: General, defect)

defect
Not set
Points:
8

Tracking

()

RESOLVED FIXED
mozilla35
Iteration:
35.2

People

(Reporter: gfritzsche, Assigned: gfritzsche)

References

Details

Attachments

(1 file)

As discussed per IRC, i have been looking into unifying more of our binary searches with our mfbt/BinarySearch.h implementation.
Points: --- → 8
It looks like we're running into an assertion due to an off-by-one error:
https://tbpl.mozilla.org/?tree=Try&rev=bbccd9130acc
Iteration: --- → 35.2
So, some test running of the failing replacement in TimerThread.cpp showed that we don't need to correct the index there at all - we always get the correct one.

https://tbpl.mozilla.org/?tree=Try&rev=e2eeb069dcca
Assignee: nobody → georg.fritzsche
Status: NEW → ASSIGNED
Attachment #8490739 - Flags: review?(jwalden+bmo)
Flags: qe-verify-
Comment on attachment 8490739 [details] [diff] [review]
Unify more binary searches

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

::: xpcom/threads/TimerThread.cpp
@@ +219,5 @@
>    }
> +
> +  size_t usIntervalResolution;
> +  BinarySearchIf(MicrosecondsToInterval(), 0, usForPosInterval, IntervalComparator(), &usIntervalResolution);
> +  MOZ_ASSERT(PR_MicrosecondsToInterval(usIntervalResolution) == 1);

Would be nice to have MOZ_ASSERT(PR_MicrosecondstoInterval(usIntervalResolution - 1) == 0); as well.  It would be Bad if we picked the largest # ms that produced an interval of 1, which just this assertion alone would permit.  We want to sanity-check both sides of the boundary for the expected behavior.
Attachment #8490739 - Flags: review?(jwalden+bmo) → review+
Nice!  How did you find these, out of curiosity?  :-)
Flags: needinfo?(georg.fritzsche)
I understand the process to have been mostly manual searching, plus a second go-by using a somewhat-imprecise LLVM pass written by jcranmer to find binary-search-looking code patterns.
Flags: needinfo?(georg.fritzsche)
https://hg.mozilla.org/mozilla-central/rev/c984a4104674
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
Component: MFBT → General
Depends on: 1257517
You need to log in before you can comment on or make changes to this bug.