1 #![feature(test)]
2 #![allow(deprecated)]
3
4 extern crate test;
5
6 use self::test::Bencher;
7 use smallvec::{ExtendFromSlice, smallvec, SmallVec};
8
9 const VEC_SIZE: usize = 16;
10 const SPILLED_SIZE: usize = 100;
11
12 trait Vector<T>: for<'a> From<&'a [T]> + Extend<T> + ExtendFromSlice<T> {
new() -> Self13 fn new() -> Self;
push(&mut self, val: T)14 fn push(&mut self, val: T);
pop(&mut self) -> Option<T>15 fn pop(&mut self) -> Option<T>;
remove(&mut self, p: usize) -> T16 fn remove(&mut self, p: usize) -> T;
insert(&mut self, n: usize, val: T)17 fn insert(&mut self, n: usize, val: T);
from_elem(val: T, n: usize) -> Self18 fn from_elem(val: T, n: usize) -> Self;
from_elems(val: &[T]) -> Self19 fn from_elems(val: &[T]) -> Self;
20 }
21
22 impl<T: Copy> Vector<T> for Vec<T> {
new() -> Self23 fn new() -> Self {
24 Self::with_capacity(VEC_SIZE)
25 }
26
push(&mut self, val: T)27 fn push(&mut self, val: T) {
28 self.push(val)
29 }
30
pop(&mut self) -> Option<T>31 fn pop(&mut self) -> Option<T> {
32 self.pop()
33 }
34
remove(&mut self, p: usize) -> T35 fn remove(&mut self, p: usize) -> T {
36 self.remove(p)
37 }
38
insert(&mut self, n: usize, val: T)39 fn insert(&mut self, n: usize, val: T) {
40 self.insert(n, val)
41 }
42
from_elem(val: T, n: usize) -> Self43 fn from_elem(val: T, n: usize) -> Self {
44 vec![val; n]
45 }
46
from_elems(val: &[T]) -> Self47 fn from_elems(val: &[T]) -> Self {
48 val.to_owned()
49 }
50 }
51
52 impl<T: Copy> Vector<T> for SmallVec<[T; VEC_SIZE]> {
new() -> Self53 fn new() -> Self {
54 Self::new()
55 }
56
push(&mut self, val: T)57 fn push(&mut self, val: T) {
58 self.push(val)
59 }
60
pop(&mut self) -> Option<T>61 fn pop(&mut self) -> Option<T> {
62 self.pop()
63 }
64
remove(&mut self, p: usize) -> T65 fn remove(&mut self, p: usize) -> T {
66 self.remove(p)
67 }
68
insert(&mut self, n: usize, val: T)69 fn insert(&mut self, n: usize, val: T) {
70 self.insert(n, val)
71 }
72
from_elem(val: T, n: usize) -> Self73 fn from_elem(val: T, n: usize) -> Self {
74 smallvec![val; n]
75 }
76
from_elems(val: &[T]) -> Self77 fn from_elems(val: &[T]) -> Self {
78 SmallVec::from_slice(val)
79 }
80 }
81
82 macro_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
93 make_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
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_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
gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher)141 fn 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
gen_insert_push<V: Vector<u64>>(n: u64, b: &mut Bencher)156 fn 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
gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher)171 fn 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
gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher)189 fn 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
gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher)204 fn 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
gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher)212 fn 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
gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)220 fn 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
gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)228 fn 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
gen_pushpop<V: Vector<u64>>(b: &mut Bencher)237 fn 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
gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher)253 fn 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]
bench_insert_many(b: &mut Bencher)261 fn 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]
bench_insert_from_slice(b: &mut Bencher)280 fn 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]
bench_macro_from_list(b: &mut Bencher)291 fn 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]
bench_macro_from_list_vec(b: &mut Bencher)303 fn 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