Improve the performance of binary_search by reducing the number of

unpredictable conditional branches in the loop. In addition improve the
benchmarks to test performance in l1, l2 and l3 caches on sorted arrays
with or without dups.

Before:

```
test slice::binary_search_l1                               ... bench:  48 ns/iter (+/- 1)
test slice::binary_search_l2                               ... bench:  63 ns/iter (+/- 0)
test slice::binary_search_l3                               ... bench: 152 ns/iter (+/- 12)
test slice::binary_search_l1_with_dups                     ... bench:  36 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups                     ... bench:  64 ns/iter (+/- 1)
test slice::binary_search_l3_with_dups                     ... bench: 153 ns/iter (+/- 6)
```

After:

```
test slice::binary_search_l1                               ... bench:  15 ns/iter (+/- 0)
test slice::binary_search_l2                               ... bench:  23 ns/iter (+/- 0)
test slice::binary_search_l3                               ... bench: 100 ns/iter (+/- 17)
test slice::binary_search_l1_with_dups                     ... bench:  15 ns/iter (+/- 0)
test slice::binary_search_l2_with_dups                     ... bench:  23 ns/iter (+/- 0)
test slice::binary_search_l3_with_dups                     ... bench:  98 ns/iter (+/- 14)
```

1 files changed, 18 insertions, 16 deletions

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 5039bef631e..e5b4df96845 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -394,23 +394,25 @@ impl<T> SliceExt for [T] {
     fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
         where F: FnMut(&'a T) -> Ordering
     {
-        let mut base = 0usize;
-        let mut s = self;
-
-        loop {
-            let (head, tail) = s.split_at(s.len() >> 1);
-            if tail.is_empty() {
-                return Err(base)
-            }
-            match f(&tail[0]) {
-                Less => {
-                    base += head.len() + 1;
-                    s = &tail[1..];
-                }
-                Greater => s = head,
-                Equal => return Ok(base + head.len()),
-            }
+        let s = self;
+        let mut size = s.len();
+        if size == 0 {
+            return Err(0);
         }
+        let mut base = 0usize;
+        while size > 1 {
+            let half = size / 2;
+            let mid = base + half;
+            // mid is always in [0, size).
+            // mid >= 0: by definition
+            // mid < size: mid = size / 2 + size / 4 + size / 8 ...
+            let cmp = f(unsafe { s.get_unchecked(mid) });
+            base = if cmp == Greater { base } else { mid };
+            size -= half;
+        }
+        // base is always in [0, size) because base <= mid.
+        let cmp = f(unsafe { s.get_unchecked(base) });
+        if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
     }
 
     #[inline]