src/libcore/benches/slice.rs

   1 use test::black_box;
   2 use test::Bencher;
   3
   4 enum Cache {
   5     L1,
   6     L2,
   7     L3,
   8 }
   9
  10 fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
  11 where
  12     F: Fn(usize) -> usize,
  13 {
  14     let size = match cache {
  15         Cache::L1 => 1000,      // 8kb
  16         Cache::L2 => 10_000,    // 80kb
  17         Cache::L3 => 1_000_000, // 8Mb
  18     };
  19     let v = (0..size).map(&mapper).collect::<Vec<_>>();
  20     let mut r = 0usize;
  21     b.iter(move || {
  22         // LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
  23         r = r.wrapping_mul(1664525).wrapping_add(1013904223);
  24         // Lookup the whole range to get 50% hits and 50% misses.
  25         let i = mapper(r % size);
  26         black_box(v.binary_search(&i).is_ok());
  27     })
  28 }
  29
  30 #[bench]
  31 fn binary_search_l1(b: &mut Bencher) {
  32     binary_search(b, Cache::L1, |i| i * 2);
  33 }
  34
  35 #[bench]
  36 fn binary_search_l2(b: &mut Bencher) {
  37     binary_search(b, Cache::L2, |i| i * 2);
  38 }
  39
  40 #[bench]
  41 fn binary_search_l3(b: &mut Bencher) {
  42     binary_search(b, Cache::L3, |i| i * 2);
  43 }
  44
  45 #[bench]
  46 fn binary_search_l1_with_dups(b: &mut Bencher) {
  47     binary_search(b, Cache::L1, |i| i / 16 * 16);
  48 }
  49
  50 #[bench]
  51 fn binary_search_l2_with_dups(b: &mut Bencher) {
  52     binary_search(b, Cache::L2, |i| i / 16 * 16);
  53 }
  54
  55 #[bench]
  56 fn binary_search_l3_with_dups(b: &mut Bencher) {
  57     binary_search(b, Cache::L3, |i| i / 16 * 16);
  58 }
  59
  60 macro_rules! rotate {
  61     ($fn:ident, $n:expr, $mapper:expr) => {
  62         #[bench]
  63         fn $fn(b: &mut Bencher) {
  64             let mut x = (0usize..$n).map(&$mapper).collect::<Vec<_>>();
  65             b.iter(|| {
  66                 for s in 0..x.len() {
  67                     x[..].rotate_right(s);
  68                 }
  69                 black_box(x[0].clone())
  70             })
  71         }
  72     };
  73 }
  74
  75 #[derive(Clone)]
  76 struct Rgb(u8, u8, u8);
  77
  78 rotate!(rotate_u8, 32, |i| i as u8);
  79 rotate!(rotate_rgb, 32, |i| Rgb(i as u8, (i as u8).wrapping_add(7), (i as u8).wrapping_add(42)));
  80 rotate!(rotate_usize, 32, |i| i);
  81 rotate!(rotate_16_usize_4, 16, |i| [i; 4]);
  82 rotate!(rotate_16_usize_5, 16, |i| [i; 5]);
  83 rotate!(rotate_64_usize_4, 64, |i| [i; 4]);
  84 rotate!(rotate_64_usize_5, 64, |i| [i; 5]);