1#![feature(test)]
2#![allow(deprecated)]
3
4extern crate test;
5
6use self::test::Bencher;
7use smallvec::{ExtendFromSlice, smallvec, SmallVec};
8
9const VEC_SIZE: usize = 16;
10const SPILLED_SIZE: usize = 100;
11
12trait Vector<T>: for<'a> From<&'a [T]> + Extend<T> + ExtendFromSlice<T> {
13 fn new() -> Self;
14 fn push(&mut self, val: T);
15 fn pop(&mut self) -> Option<T>;
16 fn remove(&mut self, p: usize) -> T;
17 fn insert(&mut self, n: usize, val: T);
18 fn from_elem(val: T, n: usize) -> Self;
19 fn from_elems(val: &[T]) -> Self;
20}
21
22impl<T: Copy> Vector<T> for Vec<T> {
23 fn new() -> Self {
24 Self::with_capacity(VEC_SIZE)
25 }
26
27 fn push(&mut self, val: T) {
28 self.push(val)
29 }
30
31 fn pop(&mut self) -> Option<T> {
32 self.pop()
33 }
34
35 fn remove(&mut self, p: usize) -> T {
36 self.remove(p)
37 }
38
39 fn insert(&mut self, n: usize, val: T) {
40 self.insert(n, val)
41 }
42
43 fn from_elem(val: T, n: usize) -> Self {
44 vec![val; n]
45 }
46
47 fn from_elems(val: &[T]) -> Self {
48 val.to_owned()
49 }
50}
51
52impl<T: Copy> Vector<T> for SmallVec<[T; VEC_SIZE]> {
53 fn new() -> Self {
54 Self::new()
55 }
56
57 fn push(&mut self, val: T) {
58 self.push(val)
59 }
60
61 fn pop(&mut self) -> Option<T> {
62 self.pop()
63 }
64
65 fn remove(&mut self, p: usize) -> T {
66 self.remove(p)
67 }
68
69 fn insert(&mut self, n: usize, val: T) {
70 self.insert(n, val)
71 }
72
73 fn from_elem(val: T, n: usize) -> Self {
74 smallvec![val; n]
75 }
76
77 fn from_elems(val: &[T]) -> Self {
78 SmallVec::from_slice(val)
79 }
80}
81
82macro_rules! make_benches {
83 ($typ:ty { $($b_name:ident => $g_name:ident($($args:expr),*),)* }) => {
84 $(
85 #[bench]
86 fn $b_name(b: &mut Bencher) {
87 $g_name::<$typ>($($args,)* b)
88 }
89 )*
90 }
91}
92
93make_benches! {
94 SmallVec<[u64; VEC_SIZE]> {
95 bench_push => gen_push(SPILLED_SIZE as _),
96 bench_push_small => gen_push(VEC_SIZE as _),
97 bench_insert_push => gen_insert_push(SPILLED_SIZE as _),
98 bench_insert_push_small => gen_insert_push(VEC_SIZE as _),
99 bench_insert => gen_insert(SPILLED_SIZE as _),
100 bench_insert_small => gen_insert(VEC_SIZE as _),
101 bench_remove => gen_remove(SPILLED_SIZE as _),
102 bench_remove_small => gen_remove(VEC_SIZE as _),
103 bench_extend => gen_extend(SPILLED_SIZE as _),
104 bench_extend_small => gen_extend(VEC_SIZE as _),
105 bench_from_iter => gen_from_iter(SPILLED_SIZE as _),
106 bench_from_iter_small => gen_from_iter(VEC_SIZE as _),
107 bench_from_slice => gen_from_slice(SPILLED_SIZE as _),
108 bench_from_slice_small => gen_from_slice(VEC_SIZE as _),
109 bench_extend_from_slice => gen_extend_from_slice(SPILLED_SIZE as _),
110 bench_extend_from_slice_small => gen_extend_from_slice(VEC_SIZE as _),
111 bench_macro_from_elem => gen_from_elem(SPILLED_SIZE as _),
112 bench_macro_from_elem_small => gen_from_elem(VEC_SIZE as _),
113 bench_pushpop => gen_pushpop(),
114 }
115}
116
117make_benches! {
118 Vec<u64> {
119 bench_push_vec => gen_push(SPILLED_SIZE as _),
120 bench_push_vec_small => gen_push(VEC_SIZE as _),
121 bench_insert_push_vec => gen_insert_push(SPILLED_SIZE as _),
122 bench_insert_push_vec_small => gen_insert_push(VEC_SIZE as _),
123 bench_insert_vec => gen_insert(SPILLED_SIZE as _),
124 bench_insert_vec_small => gen_insert(VEC_SIZE as _),
125 bench_remove_vec => gen_remove(SPILLED_SIZE as _),
126 bench_remove_vec_small => gen_remove(VEC_SIZE as _),
127 bench_extend_vec => gen_extend(SPILLED_SIZE as _),
128 bench_extend_vec_small => gen_extend(VEC_SIZE as _),
129 bench_from_iter_vec => gen_from_iter(SPILLED_SIZE as _),
130 bench_from_iter_vec_small => gen_from_iter(VEC_SIZE as _),
131 bench_from_slice_vec => gen_from_slice(SPILLED_SIZE as _),
132 bench_from_slice_vec_small => gen_from_slice(VEC_SIZE as _),
133 bench_extend_from_slice_vec => gen_extend_from_slice(SPILLED_SIZE as _),
134 bench_extend_from_slice_vec_small => gen_extend_from_slice(VEC_SIZE as _),
135 bench_macro_from_elem_vec => gen_from_elem(SPILLED_SIZE as _),
136 bench_macro_from_elem_vec_small => gen_from_elem(VEC_SIZE as _),
137 bench_pushpop_vec => gen_pushpop(),
138 }
139}
140
141fn gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
142 #[inline(never)]
143 fn push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
144 vec.push(x);
145 }
146
147 b.iter(|| {
148 let mut vec = V::new();
149 for x in 0..n {
150 push_noinline(&mut vec, x);
151 }
152 vec
153 });
154}
155
156fn gen_insert_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
157 #[inline(never)]
158 fn insert_push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
159 vec.insert(x as usize, x);
160 }
161
162 b.iter(|| {
163 let mut vec = V::new();
164 for x in 0..n {
165 insert_push_noinline(&mut vec, x);
166 }
167 vec
168 });
169}
170
171fn gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher) {
172 #[inline(never)]
173 fn insert_noinline<V: Vector<u64>>(vec: &mut V, p: usize, x: u64) {
174 vec.insert(p, x)
175 }
176
177 b.iter(|| {
178 let mut vec = V::new();
179 // Always insert at position 0 so that we are subject to shifts of
180 // many different lengths.
181 vec.push(0);
182 for x in 0..n {
183 insert_noinline(&mut vec, 0, x);
184 }
185 vec
186 });
187}
188
189fn gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher) {
190 #[inline(never)]
191 fn remove_noinline<V: Vector<u64>>(vec: &mut V, p: usize) -> u64 {
192 vec.remove(p)
193 }
194
195 b.iter(|| {
196 let mut vec = V::from_elem(0, n as _);
197
198 for _ in 0..n {
199 remove_noinline(&mut vec, 0);
200 }
201 });
202}
203
204fn gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher) {
205 b.iter(|| {
206 let mut vec = V::new();
207 vec.extend(0..n);
208 vec
209 });
210}
211
212fn gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher) {
213 let v: Vec<u64> = (0..n).collect();
214 b.iter(|| {
215 let vec = V::from(&v);
216 vec
217 });
218}
219
220fn gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
221 let v: Vec<u64> = (0..n).collect();
222 b.iter(|| {
223 let vec = V::from_elems(&v);
224 vec
225 });
226}
227
228fn gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
229 let v: Vec<u64> = (0..n).collect();
230 b.iter(|| {
231 let mut vec = V::new();
232 vec.extend_from_slice(&v);
233 vec
234 });
235}
236
237fn gen_pushpop<V: Vector<u64>>(b: &mut Bencher) {
238 #[inline(never)]
239 fn pushpop_noinline<V: Vector<u64>>(vec: &mut V, x: u64) -> Option<u64> {
240 vec.push(x);
241 vec.pop()
242 }
243
244 b.iter(|| {
245 let mut vec = V::new();
246 for x in 0..SPILLED_SIZE as _ {
247 pushpop_noinline(&mut vec, x);
248 }
249 vec
250 });
251}
252
253fn gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher) {
254 b.iter(|| {
255 let vec = V::from_elem(42, n);
256 vec
257 });
258}
259
260#[bench]
261fn bench_insert_many(b: &mut Bencher) {
262 #[inline(never)]
263 fn insert_many_noinline<I: IntoIterator<Item = u64>>(
264 vec: &mut SmallVec<[u64; VEC_SIZE]>,
265 index: usize,
266 iterable: I,
267 ) {
268 vec.insert_many(index, iterable)
269 }
270
271 b.iter(|| {
272 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
273 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
274 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
275 vec
276 });
277}
278
279#[bench]
280fn bench_insert_from_slice(b: &mut Bencher) {
281 let v: Vec<u64> = (0..SPILLED_SIZE as _).collect();
282 b.iter(|| {
283 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
284 vec.insert_from_slice(0, &v);
285 vec.insert_from_slice(0, &v);
286 vec
287 });
288}
289
290#[bench]
291fn bench_macro_from_list(b: &mut Bencher) {
292 b.iter(|| {
293 let vec: SmallVec<[u64; 16]> = smallvec![
294 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
295 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
296 0x80000, 0x100000,
297 ];
298 vec
299 });
300}
301
302#[bench]
303fn bench_macro_from_list_vec(b: &mut Bencher) {
304 b.iter(|| {
305 let vec: Vec<u64> = vec![
306 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
307 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
308 0x80000, 0x100000,
309 ];
310 vec
311 });
312}
313