src/libcore/benches/slice.rs

   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.
   4 //
   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.
  10
  11 use test::black_box;
  12 use test::Bencher;
  13
  14 enum Cache {
  15     L1,
  16     L2,
  17     L3,
  18 }
  19
  20 fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
  21     where F: Fn(usize) -> usize
  22 {
  23     let size = match cache {
  24         Cache::L1 => 1000, // 8kb
  25         Cache::L2 => 10_000, // 80kb
  26         Cache::L3 => 1_000_000, // 8Mb
  27     };
  28     let v = (0..size).map(&mapper).collect::<Vec<_>>();
  29     let mut r = 0usize;
  30     b.iter(move || {
  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());
  36     })
  37 }
  38
  39 #[bench]
  40 fn binary_search_l1(b: &mut Bencher) {
  41     binary_search(b, Cache::L1, |i| i * 2);
  42 }
  43
  44 #[bench]
  45 fn binary_search_l2(b: &mut Bencher) {
  46     binary_search(b, Cache::L2, |i| i * 2);
  47 }
  48
  49 #[bench]
  50 fn binary_search_l3(b: &mut Bencher) {
  51     binary_search(b, Cache::L3, |i| i * 2);
  52 }
  53
  54 #[bench]
  55 fn binary_search_l1_with_dups(b: &mut Bencher) {
  56     binary_search(b, Cache::L1, |i| i / 16 * 16);
  57 }
  58
  59 #[bench]
  60 fn binary_search_l2_with_dups(b: &mut Bencher) {
  61     binary_search(b, Cache::L2, |i| i / 16 * 16);
  62 }
  63
  64 #[bench]
  65 fn binary_search_l3_with_dups(b: &mut Bencher) {
  66     binary_search(b, Cache::L3, |i| i / 16 * 16);
  67 }