11 fn size(&self) -> usize {
13 Cache::L1 => 1000, // 8kb
14 Cache::L2 => 10_000, // 80kb
15 Cache::L3 => 1_000_000, // 8Mb
20 fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
22 F: Fn(usize) -> usize,
24 let size = cache.size();
25 let v = (0..size).map(&mapper).collect::<Vec<_>>();
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());
36 fn binary_search_worst_case(b: &mut Bencher, cache: Cache) {
37 let size = cache.size();
39 let mut v = vec![0; size];
43 black_box(v.binary_search(&i).is_ok());
48 fn binary_search_l1(b: &mut Bencher) {
49 binary_search(b, Cache::L1, |i| i * 2);
53 fn binary_search_l2(b: &mut Bencher) {
54 binary_search(b, Cache::L2, |i| i * 2);
58 fn binary_search_l3(b: &mut Bencher) {
59 binary_search(b, Cache::L3, |i| i * 2);
63 fn binary_search_l1_with_dups(b: &mut Bencher) {
64 binary_search(b, Cache::L1, |i| i / 16 * 16);
68 fn binary_search_l2_with_dups(b: &mut Bencher) {
69 binary_search(b, Cache::L2, |i| i / 16 * 16);
73 fn binary_search_l3_with_dups(b: &mut Bencher) {
74 binary_search(b, Cache::L3, |i| i / 16 * 16);
78 fn binary_search_l1_worst_case(b: &mut Bencher) {
79 binary_search_worst_case(b, Cache::L1);
83 fn binary_search_l2_worst_case(b: &mut Bencher) {
84 binary_search_worst_case(b, Cache::L2);
88 fn binary_search_l3_worst_case(b: &mut Bencher) {
89 binary_search_worst_case(b, Cache::L3);
93 struct Rgb(u8, u8, u8);
96 fn gen(i: usize) -> Self {
97 Rgb(i as u8, (i as u8).wrapping_add(7), (i as u8).wrapping_add(42))
101 macro_rules! rotate {
102 ($fn:ident, $n:expr, $mapper:expr) => {
104 fn $fn(b: &mut Bencher) {
105 let mut x = (0usize..$n).map(&$mapper).collect::<Vec<_>>();
107 for s in 0..x.len() {
108 x[..].rotate_right(s);
110 black_box(x[0].clone())
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]);
124 macro_rules! swap_with_slice {
125 ($fn:ident, $n:expr, $mapper:expr) => {
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<_>>();
133 x[skip..].swap_with_slice(&mut y[..($n - skip)]);
134 skip = black_box(skip + 1) % 8;
136 black_box((x[$n / 3].clone(), y[$n * 2 / 3].clone()))
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]);
154 fn fill_byte_sized(b: &mut Bencher) {
155 #[derive(Copy, Clone)]
158 let mut ary = [NewType(0); 1024];
161 let slice = &mut ary[..];
162 black_box(slice.fill(black_box(NewType(42))));