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