1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
20 fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
21 where F: Fn(usize) -> usize
23 let size = match cache {
24 Cache::L1 => 1000, // 8kb
25 Cache::L2 => 10_000, // 80kb
26 Cache::L3 => 1_000_000, // 8Mb
28 let v = (0..size).map(&mapper).collect::<Vec<_>>();
31 // LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
32 r = r.wrapping_mul(1664525).wrapping_add(1013904223);
33 // Lookup the whole range to get 50% hits and 50% misses.
34 let i = mapper(r % size);
35 black_box(v.binary_search(&i).is_ok());
40 fn binary_search_l1(b: &mut Bencher) {
41 binary_search(b, Cache::L1, |i| i * 2);
45 fn binary_search_l2(b: &mut Bencher) {
46 binary_search(b, Cache::L2, |i| i * 2);
50 fn binary_search_l3(b: &mut Bencher) {
51 binary_search(b, Cache::L3, |i| i * 2);
55 fn binary_search_l1_with_dups(b: &mut Bencher) {
56 binary_search(b, Cache::L1, |i| i / 16 * 16);
60 fn binary_search_l2_with_dups(b: &mut Bencher) {
61 binary_search(b, Cache::L2, |i| i / 16 * 16);
65 fn binary_search_l3_with_dups(b: &mut Bencher) {
66 binary_search(b, Cache::L3, |i| i / 16 * 16);