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