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 => 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
117 make_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_vec => gen_insert(SPILLED_SIZE as _),
122 bench_insert_vec_small => gen_insert(VEC_SIZE as _),
123 bench_remove_vec => gen_remove(SPILLED_SIZE as _),
124 bench_remove_vec_small => gen_remove(VEC_SIZE as _),
125 bench_extend_vec => gen_extend(SPILLED_SIZE as _),
126 bench_extend_vec_small => gen_extend(VEC_SIZE as _),
127 bench_from_iter_vec => gen_from_iter(SPILLED_SIZE as _),
128 bench_from_iter_vec_small => gen_from_iter(VEC_SIZE as _),
129 bench_from_slice_vec => gen_from_slice(SPILLED_SIZE as _),
130 bench_from_slice_vec_small => gen_from_slice(VEC_SIZE as _),
131 bench_extend_from_slice_vec => gen_extend_from_slice(SPILLED_SIZE as _),
132 bench_extend_from_slice_vec_small => gen_extend_from_slice(VEC_SIZE as _),
133 bench_macro_from_elem_vec => gen_from_elem(SPILLED_SIZE as _),
134 bench_macro_from_elem_vec_small => gen_from_elem(VEC_SIZE as _),
135 bench_pushpop_vec => gen_pushpop(),
136 }
137 }
138
gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher)139 fn gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
140 #[inline(never)]
141 fn push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
142 vec.push(x);
143 }
144
145 b.iter(|| {
146 let mut vec = V::new();
147 for x in 0..n {
148 push_noinline(&mut vec, x);
149 }
150 vec
151 });
152 }
153
gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher)154 fn gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher) {
155 #[inline(never)]
156 fn insert_noinline<V: Vector<u64>>(vec: &mut V, p: usize, x: u64) {
157 vec.insert(p, x)
158 }
159
160 b.iter(|| {
161 let mut vec = V::new();
162 // Always insert at position 0 so that we are subject to shifts of
163 // many different lengths.
164 vec.push(0);
165 for x in 0..n {
166 insert_noinline(&mut vec, 0, x);
167 }
168 vec
169 });
170 }
171
gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher)172 fn gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher) {
173 #[inline(never)]
174 fn remove_noinline<V: Vector<u64>>(vec: &mut V, p: usize) -> u64 {
175 vec.remove(p)
176 }
177
178 b.iter(|| {
179 let mut vec = V::from_elem(0, n as _);
180
181 for _ in 0..n {
182 remove_noinline(&mut vec, 0);
183 }
184 });
185 }
186
gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher)187 fn gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher) {
188 b.iter(|| {
189 let mut vec = V::new();
190 vec.extend(0..n);
191 vec
192 });
193 }
194
gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher)195 fn gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher) {
196 let v: Vec<u64> = (0..n).collect();
197 b.iter(|| {
198 let vec = V::from(&v);
199 vec
200 });
201 }
202
gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)203 fn gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
204 let v: Vec<u64> = (0..n).collect();
205 b.iter(|| {
206 let vec = V::from_elems(&v);
207 vec
208 });
209 }
210
gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)211 fn gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
212 let v: Vec<u64> = (0..n).collect();
213 b.iter(|| {
214 let mut vec = V::new();
215 vec.extend_from_slice(&v);
216 vec
217 });
218 }
219
gen_pushpop<V: Vector<u64>>(b: &mut Bencher)220 fn gen_pushpop<V: Vector<u64>>(b: &mut Bencher) {
221 #[inline(never)]
222 fn pushpop_noinline<V: Vector<u64>>(vec: &mut V, x: u64) -> Option<u64> {
223 vec.push(x);
224 vec.pop()
225 }
226
227 b.iter(|| {
228 let mut vec = V::new();
229 for x in 0..SPILLED_SIZE as _ {
230 pushpop_noinline(&mut vec, x);
231 }
232 vec
233 });
234 }
235
gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher)236 fn gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher) {
237 b.iter(|| {
238 let vec = V::from_elem(42, n);
239 vec
240 });
241 }
242
243 #[bench]
bench_insert_many(b: &mut Bencher)244 fn bench_insert_many(b: &mut Bencher) {
245 #[inline(never)]
246 fn insert_many_noinline<I: IntoIterator<Item = u64>>(
247 vec: &mut SmallVec<[u64; VEC_SIZE]>,
248 index: usize,
249 iterable: I,
250 ) {
251 vec.insert_many(index, iterable)
252 }
253
254 b.iter(|| {
255 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
256 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
257 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
258 vec
259 });
260 }
261
262 #[bench]
bench_insert_from_slice(b: &mut Bencher)263 fn bench_insert_from_slice(b: &mut Bencher) {
264 let v: Vec<u64> = (0..SPILLED_SIZE as _).collect();
265 b.iter(|| {
266 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
267 vec.insert_from_slice(0, &v);
268 vec.insert_from_slice(0, &v);
269 vec
270 });
271 }
272
273 #[bench]
bench_macro_from_list(b: &mut Bencher)274 fn bench_macro_from_list(b: &mut Bencher) {
275 b.iter(|| {
276 let vec: SmallVec<[u64; 16]> = smallvec![
277 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
278 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
279 0x80000, 0x100000,
280 ];
281 vec
282 });
283 }
284
285 #[bench]
bench_macro_from_list_vec(b: &mut Bencher)286 fn bench_macro_from_list_vec(b: &mut Bencher) {
287 b.iter(|| {
288 let vec: Vec<u64> = vec![
289 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
290 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
291 0x80000, 0x100000,
292 ];
293 vec
294 });
295 }
296