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)
```

2 files changed, 68 insertions, 1 deletions

diff --git a/src/libcore/benches/lib.rs b/src/libcore/benches/lib.rs
index d2db329da79..201064e823b 100644
--- a/src/libcore/benches/lib.rs
+++ b/src/libcore/benches/lib.rs
@@ -20,6 +20,6 @@ extern crate test;
 mod any;
 mod hash;
 mod iter;
-mod mem;
 mod num;
 mod ops;
+mod slice;
diff --git a/src/libcore/benches/slice.rs b/src/libcore/benches/slice.rs
new file mode 100644
index 00000000000..b2fc74544f1
--- /dev/null
+++ b/src/libcore/benches/slice.rs
@@ -0,0 +1,67 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use test::black_box;
+use test::Bencher;
+
+enum Cache {
+    L1,
+    L2,
+    L3,
+}
+
+fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
+    where F: Fn(usize) -> usize
+{
+    let size = match cache {
+        Cache::L1 => 1000, // 8kb
+        Cache::L2 => 10_000, // 80kb
+        Cache::L3 => 1_000_000, // 8Mb
+    };
+    let v = (0..size).map(&mapper).collect::<Vec<_>>();
+    let mut r = 0usize;
+    b.iter(move || {
+        // LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
+        r = r.wrapping_mul(1664525).wrapping_add(1013904223);
+        // Lookup the whole range to get 50% hits and 50% misses.
+        let i = mapper(r % size);
+        black_box(v.binary_search(&i).is_ok());
+    })
+}
+
+#[bench]
+fn binary_search_l1(b: &mut Bencher) {
+    binary_search(b, Cache::L1, |i| i * 2);
+}
+
+#[bench]
+fn binary_search_l2(b: &mut Bencher) {
+    binary_search(b, Cache::L2, |i| i * 2);
+}
+
+#[bench]
+fn binary_search_l3(b: &mut Bencher) {
+    binary_search(b, Cache::L3, |i| i * 2);
+}
+
+#[bench]
+fn binary_search_l1_with_dups(b: &mut Bencher) {
+    binary_search(b, Cache::L1, |i| i / 16 * 16);
+}
+
+#[bench]
+fn binary_search_l2_with_dups(b: &mut Bencher) {
+    binary_search(b, Cache::L2, |i| i / 16 * 16);
+}
+
+#[bench]
+fn binary_search_l3_with_dups(b: &mut Bencher) {
+    binary_search(b, Cache::L3, |i| i / 16 * 16);
+}