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 F: Fn(usize) -> usize
  12 {
  13     let size = match cache {
  14         Cache::L1 => 1000, // 8kb
  15         Cache::L2 => 10_000, // 80kb
  16         Cache::L3 => 1_000_000, // 8Mb
  17     };
  18     let v = (0..size).map(&mapper).collect::<Vec<_>>();
  19     let mut r = 0usize;
  20     b.iter(move || {
  21         // LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
  22         r = r.wrapping_mul(1664525).wrapping_add(1013904223);
  23         // Lookup the whole range to get 50% hits and 50% misses.
  24         let i = mapper(r % size);
  25         black_box(v.binary_search(&i).is_ok());
  26     })
  27 }
  28
  29 #[bench]
  30 fn binary_search_l1(b: &mut Bencher) {
  31     binary_search(b, Cache::L1, |i| i * 2);
  32 }
  33
  34 #[bench]
  35 fn binary_search_l2(b: &mut Bencher) {
  36     binary_search(b, Cache::L2, |i| i * 2);
  37 }
  38
  39 #[bench]
  40 fn binary_search_l3(b: &mut Bencher) {
  41     binary_search(b, Cache::L3, |i| i * 2);
  42 }
  43
  44 #[bench]
  45 fn binary_search_l1_with_dups(b: &mut Bencher) {
  46     binary_search(b, Cache::L1, |i| i / 16 * 16);
  47 }
  48
  49 #[bench]
  50 fn binary_search_l2_with_dups(b: &mut Bencher) {
  51     binary_search(b, Cache::L2, |i| i / 16 * 16);
  52 }
  53
  54 #[bench]
  55 fn binary_search_l3_with_dups(b: &mut Bencher) {
  56     binary_search(b, Cache::L3, |i| i / 16 * 16);
  57 }