library/core/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 impl Cache {
  11     fn size(&self) -> usize {
  12         match self {
  13             Cache::L1 => 1000,      // 8kb
  14             Cache::L2 => 10_000,    // 80kb
  15             Cache::L3 => 1_000_000, // 8Mb
  16         }
  17     }
  18 }
  19
  20 fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
  21 where
  22     F: Fn(usize) -> usize,
  23 {
  24     let size = cache.size();
  25     let v = (0..size).map(&mapper).collect::<Vec<_>>();
  26     let mut r = 0usize;
  27     b.iter(move || {
  28         // LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
  29         r = r.wrapping_mul(1664525).wrapping_add(1013904223);
  30         // Lookup the whole range to get 50% hits and 50% misses.
  31         let i = mapper(r % size);
  32         black_box(v.binary_search(&i).is_ok());
  33     });
  34 }
  35
  36 fn binary_search_worst_case(b: &mut Bencher, cache: Cache) {
  37     let size = cache.size();
  38
  39     let mut v = vec![0; size];
  40     let i = 1;
  41     v[size - 1] = i;
  42     b.iter(move || {
  43         black_box(v.binary_search(&i).is_ok());
  44     });
  45 }
  46
  47 #[bench]
  48 fn binary_search_l1(b: &mut Bencher) {
  49     binary_search(b, Cache::L1, |i| i * 2);
  50 }
  51
  52 #[bench]
  53 fn binary_search_l2(b: &mut Bencher) {
  54     binary_search(b, Cache::L2, |i| i * 2);
  55 }
  56
  57 #[bench]
  58 fn binary_search_l3(b: &mut Bencher) {
  59     binary_search(b, Cache::L3, |i| i * 2);
  60 }
  61
  62 #[bench]
  63 fn binary_search_l1_with_dups(b: &mut Bencher) {
  64     binary_search(b, Cache::L1, |i| i / 16 * 16);
  65 }
  66
  67 #[bench]
  68 fn binary_search_l2_with_dups(b: &mut Bencher) {
  69     binary_search(b, Cache::L2, |i| i / 16 * 16);
  70 }
  71
  72 #[bench]
  73 fn binary_search_l3_with_dups(b: &mut Bencher) {
  74     binary_search(b, Cache::L3, |i| i / 16 * 16);
  75 }
  76
  77 #[bench]
  78 fn binary_search_l1_worst_case(b: &mut Bencher) {
  79     binary_search_worst_case(b, Cache::L1);
  80 }
  81
  82 #[bench]
  83 fn binary_search_l2_worst_case(b: &mut Bencher) {
  84     binary_search_worst_case(b, Cache::L2);
  85 }
  86
  87 #[bench]
  88 fn binary_search_l3_worst_case(b: &mut Bencher) {
  89     binary_search_worst_case(b, Cache::L3);
  90 }
  91
  92 #[derive(Clone)]
  93 struct Rgb(u8, u8, u8);
  94
  95 impl Rgb {
  96     fn gen(i: usize) -> Self {
  97         Rgb(i as u8, (i as u8).wrapping_add(7), (i as u8).wrapping_add(42))
  98     }
  99 }
 100
 101 macro_rules! rotate {
 102     ($fn:ident, $n:expr, $mapper:expr) => {
 103         #[bench]
 104         fn $fn(b: &mut Bencher) {
 105             let mut x = (0usize..$n).map(&$mapper).collect::<Vec<_>>();
 106             b.iter(|| {
 107                 for s in 0..x.len() {
 108                     x[..].rotate_right(s);
 109                 }
 110                 black_box(x[0].clone())
 111             })
 112         }
 113     };
 114 }
 115
 116 rotate!(rotate_u8, 32, |i| i as u8);
 117 rotate!(rotate_rgb, 32, Rgb::gen);
 118 rotate!(rotate_usize, 32, |i| i);
 119 rotate!(rotate_16_usize_4, 16, |i| [i; 4]);
 120 rotate!(rotate_16_usize_5, 16, |i| [i; 5]);
 121 rotate!(rotate_64_usize_4, 64, |i| [i; 4]);
 122 rotate!(rotate_64_usize_5, 64, |i| [i; 5]);
 123
 124 macro_rules! swap_with_slice {
 125     ($fn:ident, $n:expr, $mapper:expr) => {
 126         #[bench]
 127         fn $fn(b: &mut Bencher) {
 128             let mut x = (0usize..$n).map(&$mapper).collect::<Vec<_>>();
 129             let mut y = ($n..($n * 2)).map(&$mapper).collect::<Vec<_>>();
 130             let mut skip = 0;
 131             b.iter(|| {
 132                 for _ in 0..32 {
 133                     x[skip..].swap_with_slice(&mut y[..($n - skip)]);
 134                     skip = black_box(skip + 1) % 8;
 135                 }
 136                 black_box((x[$n / 3].clone(), y[$n * 2 / 3].clone()))
 137             })
 138         }
 139     };
 140 }
 141
 142 swap_with_slice!(swap_with_slice_u8_30, 30, |i| i as u8);
 143 swap_with_slice!(swap_with_slice_u8_3000, 3000, |i| i as u8);
 144 swap_with_slice!(swap_with_slice_rgb_30, 30, Rgb::gen);
 145 swap_with_slice!(swap_with_slice_rgb_3000, 3000, Rgb::gen);
 146 swap_with_slice!(swap_with_slice_usize_30, 30, |i| i);
 147 swap_with_slice!(swap_with_slice_usize_3000, 3000, |i| i);
 148 swap_with_slice!(swap_with_slice_4x_usize_30, 30, |i| [i; 4]);
 149 swap_with_slice!(swap_with_slice_4x_usize_3000, 3000, |i| [i; 4]);
 150 swap_with_slice!(swap_with_slice_5x_usize_30, 30, |i| [i; 5]);
 151 swap_with_slice!(swap_with_slice_5x_usize_3000, 3000, |i| [i; 5]);
 152
 153 #[bench]
 154 fn fill_byte_sized(b: &mut Bencher) {
 155     #[derive(Copy, Clone)]
 156     struct NewType(u8);
 157
 158     let mut ary = [NewType(0); 1024];
 159
 160     b.iter(|| {
 161         let slice = &mut ary[..];
 162         black_box(slice.fill(black_box(NewType(42))));
 163     });
 164 }