1067989 - Unify some more binary search uses

Status: RESOLVED FIXED

(Core :: General, defect)

Description

[Georg Fritzsche [:gfritzsche]]

As discussed per IRC, i have been looking into unifying more of our binary searches with our mfbt/BinarySearch.h implementation.

Comment 1

[Georg Fritzsche [:gfritzsche]]

It looks like we're running into an assertion due to an off-by-one error:
https://tbpl.mozilla.org/?tree=Try&rev=bbccd9130acc

Comment 2

[Georg Fritzsche [:gfritzsche]]

Attachment: Unify more binary searches

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

Comment 3

[Jeff Walden [:Waldo]]

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.

Comment 4

[Georg Fritzsche [:gfritzsche]]

https://tbpl.mozilla.org/?tree=Try&rev=056272eeca34

Comment 5

[Georg Fritzsche [:gfritzsche]]

https://tbpl.mozilla.org/?tree=Try&rev=3e88dcab69ee

Comment 6

[Georg Fritzsche [:gfritzsche]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/c984a4104674

Comment 7

[(no longer active)]

Nice!  How did you find these, out of curiosity?  :-)

Comment 8

[Jeff Walden [:Waldo]]

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.

Comment 9

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/c984a4104674