vendor/smallvec-0.6.13/benches/bench.rs

   1 #![feature(test)]
   2
   3 #[macro_use]
   4 extern crate smallvec;
   5 extern crate test;
   6
   7 use self::test::Bencher;
   8 use smallvec::{ExtendFromSlice, SmallVec};
   9
  10 const VEC_SIZE: usize = 16;
  11 const SPILLED_SIZE: usize = 100;
  12
  13 trait Vector<T>: for<'a> From<&'a [T]> + Extend<T> + ExtendFromSlice<T> {
  14     fn new() -> Self;
  15     fn push(&mut self, val: T);
  16     fn pop(&mut self) -> Option<T>;
  17     fn remove(&mut self, p: usize) -> T;
  18     fn insert(&mut self, n: usize, val: T);
  19     fn from_elem(val: T, n: usize) -> Self;
  20     fn from_elems(val: &[T]) -> Self;
  21 }
  22
  23 impl<T: Copy> Vector<T> for Vec<T> {
  24     fn new() -> Self {
  25         Self::with_capacity(VEC_SIZE)
  26     }
  27
  28     fn push(&mut self, val: T) {
  29         self.push(val)
  30     }
  31
  32     fn pop(&mut self) -> Option<T> {
  33         self.pop()
  34     }
  35
  36     fn remove(&mut self, p: usize) -> T {
  37         self.remove(p)
  38     }
  39
  40     fn insert(&mut self, n: usize, val: T) {
  41         self.insert(n, val)
  42     }
  43
  44     fn from_elem(val: T, n: usize) -> Self {
  45         vec![val; n]
  46     }
  47
  48     fn from_elems(val: &[T]) -> Self {
  49         val.to_owned()
  50     }
  51 }
  52
  53 impl<T: Copy> Vector<T> for SmallVec<[T; VEC_SIZE]> {
  54     fn new() -> Self {
  55         Self::new()
  56     }
  57
  58     fn push(&mut self, val: T) {
  59         self.push(val)
  60     }
  61
  62     fn pop(&mut self) -> Option<T> {
  63         self.pop()
  64     }
  65
  66     fn remove(&mut self, p: usize) -> T {
  67         self.remove(p)
  68     }
  69
  70     fn insert(&mut self, n: usize, val: T) {
  71         self.insert(n, val)
  72     }
  73
  74     fn from_elem(val: T, n: usize) -> Self {
  75         smallvec![val; n]
  76     }
  77
  78     fn from_elems(val: &[T]) -> Self {
  79         SmallVec::from_slice(val)
  80     }
  81 }
  82
  83 macro_rules! make_benches {
  84     ($typ:ty { $($b_name:ident => $g_name:ident($($args:expr),*),)* }) => {
  85         $(
  86             #[bench]
  87             fn $b_name(b: &mut Bencher) {
  88                 $g_name::<$typ>($($args,)* b)
  89             }
  90         )*
  91     }
  92 }
  93
  94 make_benches! {
  95     SmallVec<[u64; VEC_SIZE]> {
  96         bench_push => gen_push(SPILLED_SIZE as _),
  97         bench_push_small => gen_push(VEC_SIZE as _),
  98         bench_insert => gen_insert(SPILLED_SIZE as _),
  99         bench_insert_small => gen_insert(VEC_SIZE as _),
 100         bench_remove => gen_remove(SPILLED_SIZE as _),
 101         bench_remove_small => gen_remove(VEC_SIZE as _),
 102         bench_extend => gen_extend(SPILLED_SIZE as _),
 103         bench_extend_small => gen_extend(VEC_SIZE as _),
 104         bench_from_iter => gen_from_iter(SPILLED_SIZE as _),
 105         bench_from_iter_small => gen_from_iter(VEC_SIZE as _),
 106         bench_from_slice => gen_from_slice(SPILLED_SIZE as _),
 107         bench_from_slice_small => gen_from_slice(VEC_SIZE as _),
 108         bench_extend_from_slice => gen_extend_from_slice(SPILLED_SIZE as _),
 109         bench_extend_from_slice_small => gen_extend_from_slice(VEC_SIZE as _),
 110         bench_macro_from_elem => gen_from_elem(SPILLED_SIZE as _),
 111         bench_macro_from_elem_small => gen_from_elem(VEC_SIZE as _),
 112         bench_pushpop => gen_pushpop(),
 113     }
 114 }
 115
 116 make_benches! {
 117     Vec<u64> {
 118         bench_push_vec => gen_push(SPILLED_SIZE as _),
 119         bench_push_vec_small => gen_push(VEC_SIZE as _),
 120         bench_insert_vec => gen_insert(SPILLED_SIZE as _),
 121         bench_insert_vec_small => gen_insert(VEC_SIZE as _),
 122         bench_remove_vec => gen_remove(SPILLED_SIZE as _),
 123         bench_remove_vec_small => gen_remove(VEC_SIZE as _),
 124         bench_extend_vec => gen_extend(SPILLED_SIZE as _),
 125         bench_extend_vec_small => gen_extend(VEC_SIZE as _),
 126         bench_from_iter_vec => gen_from_iter(SPILLED_SIZE as _),
 127         bench_from_iter_vec_small => gen_from_iter(VEC_SIZE as _),
 128         bench_from_slice_vec => gen_from_slice(SPILLED_SIZE as _),
 129         bench_from_slice_vec_small => gen_from_slice(VEC_SIZE as _),
 130         bench_extend_from_slice_vec => gen_extend_from_slice(SPILLED_SIZE as _),
 131         bench_extend_from_slice_vec_small => gen_extend_from_slice(VEC_SIZE as _),
 132         bench_macro_from_elem_vec => gen_from_elem(SPILLED_SIZE as _),
 133         bench_macro_from_elem_vec_small => gen_from_elem(VEC_SIZE as _),
 134         bench_pushpop_vec => gen_pushpop(),
 135     }
 136 }
 137
 138 fn gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
 139     #[inline(never)]
 140     fn push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
 141         vec.push(x);
 142     }
 143
 144     b.iter(|| {
 145         let mut vec = V::new();
 146         for x in 0..n {
 147             push_noinline(&mut vec, x);
 148         }
 149         vec
 150     });
 151 }
 152
 153 fn gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher) {
 154     #[inline(never)]
 155     fn insert_noinline<V: Vector<u64>>(vec: &mut V, p: usize, x: u64) {
 156         vec.insert(p, x)
 157     }
 158
 159     b.iter(|| {
 160         let mut vec = V::new();
 161         // Add one element, with each iteration we insert one before the end.
 162         // This means that we benchmark the insertion operation and not the
 163         // time it takes to `ptr::copy` the data.
 164         vec.push(0);
 165         for x in 0..n {
 166             insert_noinline(&mut vec, x as _, x);
 167         }
 168         vec
 169     });
 170 }
 171
 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 x in (0..n - 1).rev() {
 182             remove_noinline(&mut vec, x);
 183         }
 184     });
 185 }
 186
 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
 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
 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
 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
 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
 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]
 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]
 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]
 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]
 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 }