1071448 - BinarySearch.jsm: Optimize the search algorithm a little

Status: RESOLVED FIXED

(Toolkit :: General, defect)

Description

[Alex Vincent [:WeirdAl]]

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 1

[Alex Vincent [:WeirdAl]]

Attachment: Speed up binary searches using a bitwise operation.

Comment 2

[Drew Willcoxon :adw]

Comment on attachment 8493559 [details] [diff] [review]
Speed up binary searches using a bitwise operation.

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

Thanks, Alex.

Comment 3

[Drew Willcoxon :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.

Comment 4

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/integration/fx-team/rev/c105e80ce923

Comment 5

[Ryan VanderMeulen [:RyanVM]]

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