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