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 // Add one element, with each iteration we insert one before the end.
163 // This means that we benchmark the insertion operation and not the
164 // time it takes to `ptr::copy` the data.
165 vec.push(0);
166 for x in 0..n {
167 insert_noinline(&mut vec, x as _, x);
168 }
169 vec
170 });
171 }
172
gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher)173 fn gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher) {
174 #[inline(never)]
175 fn remove_noinline<V: Vector<u64>>(vec: &mut V, p: usize) -> u64 {
176 vec.remove(p)
177 }
178
179 b.iter(|| {
180 let mut vec = V::from_elem(0, n as _);
181
182 for x in (0..n - 1).rev() {
183 remove_noinline(&mut vec, x);
184 }
185 });
186 }
187
gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher)188 fn gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher) {
189 b.iter(|| {
190 let mut vec = V::new();
191 vec.extend(0..n);
192 vec
193 });
194 }
195
gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher)196 fn gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher) {
197 let v: Vec<u64> = (0..n).collect();
198 b.iter(|| {
199 let vec = V::from(&v);
200 vec
201 });
202 }
203
gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)204 fn gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
205 let v: Vec<u64> = (0..n).collect();
206 b.iter(|| {
207 let vec = V::from_elems(&v);
208 vec
209 });
210 }
211
gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher)212 fn gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
213 let v: Vec<u64> = (0..n).collect();
214 b.iter(|| {
215 let mut vec = V::new();
216 vec.extend_from_slice(&v);
217 vec
218 });
219 }
220
gen_pushpop<V: Vector<u64>>(b: &mut Bencher)221 fn gen_pushpop<V: Vector<u64>>(b: &mut Bencher) {
222 #[inline(never)]
223 fn pushpop_noinline<V: Vector<u64>>(vec: &mut V, x: u64) -> Option<u64> {
224 vec.push(x);
225 vec.pop()
226 }
227
228 b.iter(|| {
229 let mut vec = V::new();
230 for x in 0..SPILLED_SIZE as _ {
231 pushpop_noinline(&mut vec, x);
232 }
233 vec
234 });
235 }
236
gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher)237 fn gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher) {
238 b.iter(|| {
239 let vec = V::from_elem(42, n);
240 vec
241 });
242 }
243
244 #[bench]
bench_insert_many(b: &mut Bencher)245 fn bench_insert_many(b: &mut Bencher) {
246 #[inline(never)]
247 fn insert_many_noinline<I: IntoIterator<Item = u64>>(
248 vec: &mut SmallVec<[u64; VEC_SIZE]>,
249 index: usize,
250 iterable: I,
251 ) {
252 vec.insert_many(index, iterable)
253 }
254
255 b.iter(|| {
256 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
257 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
258 insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
259 vec
260 });
261 }
262
263 #[bench]
bench_insert_from_slice(b: &mut Bencher)264 fn bench_insert_from_slice(b: &mut Bencher) {
265 let v: Vec<u64> = (0..SPILLED_SIZE as _).collect();
266 b.iter(|| {
267 let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
268 vec.insert_from_slice(0, &v);
269 vec.insert_from_slice(0, &v);
270 vec
271 });
272 }
273
274 #[bench]
bench_macro_from_list(b: &mut Bencher)275 fn bench_macro_from_list(b: &mut Bencher) {
276 b.iter(|| {
277 let vec: SmallVec<[u64; 16]> = smallvec![
278 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
279 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
280 0x80000, 0x100000,
281 ];
282 vec
283 });
284 }
285
286 #[bench]
bench_macro_from_list_vec(b: &mut Bencher)287 fn bench_macro_from_list_vec(b: &mut Bencher) {
288 b.iter(|| {
289 let vec: Vec<u64> = vec![
290 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
291 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
292 0x80000, 0x100000,
293 ];
294 vec
295 });
296 }
297