Closed Bug 1071448 Opened 6 years ago Closed 6 years ago

BinarySearch.jsm: Optimize the search algorithm a little

Categories

(Toolkit :: General, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla35

People

(Reporter: WeirdAl, Assigned: WeirdAl)

References

()

Details

Attachments

(1 file)

By replacing:
let mid = Math.floor((low + high) / 2);

with:
let mid = (low + high) >> 1;

we can make the binary search code about 2.5x as fast as it is now.  I don't know who came up with this idea, but it works.
Comment on attachment 8493559 [details] [diff] [review]
Speed up binary searches using a bitwise operation.

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

Thanks, Alex.
Attachment #8493559 - Flags: review?(adw) → review+
Attachment #8493559 - Flags: checkin?(adw)
It's not convenient for me to check this in right now, so I'll mark the bug as checkin-needed instead.

No try push necessary: relevant test passes locally, very small change.
Status: NEW → ASSIGNED
Keywords: checkin-needed
OS: Linux → All
Hardware: x86_64 → All
Attachment #8493559 - Flags: checkin?(adw)
https://hg.mozilla.org/mozilla-central/rev/c105e80ce923
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Whiteboard: [fixed-in-fx-team]
Target Milestone: --- → mozilla35
You need to log in before you can comment on or make changes to this bug.