src/libcollections/benches/slice.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::{mem, ptr};
  12 use std::__rand::{Rng, thread_rng};
  13
  14 use test::{Bencher, black_box};
  15
  16 #[bench]
  17 fn iterator(b: &mut Bencher) {
  18     // peculiar numbers to stop LLVM from optimising the summation
  19     // out.
  20     let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
  21
  22     b.iter(|| {
  23         let mut sum = 0;
  24         for x in &v {
  25             sum += *x;
  26         }
  27         // sum == 11806, to stop dead code elimination.
  28         if sum == 0 {
  29             panic!()
  30         }
  31     })
  32 }
  33
  34 #[bench]
  35 fn mut_iterator(b: &mut Bencher) {
  36     let mut v = vec![0; 100];
  37
  38     b.iter(|| {
  39         let mut i = 0;
  40         for x in &mut v {
  41             *x = i;
  42             i += 1;
  43         }
  44     })
  45 }
  46
  47 #[bench]
  48 fn concat(b: &mut Bencher) {
  49     let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
  50     b.iter(|| {
  51         xss.concat();
  52     });
  53 }
  54
  55 #[bench]
  56 fn join(b: &mut Bencher) {
  57     let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
  58     b.iter(|| xss.join(&0));
  59 }
  60
  61 #[bench]
  62 fn push(b: &mut Bencher) {
  63     let mut vec = Vec::<i32>::new();
  64     b.iter(|| {
  65         vec.push(0);
  66         black_box(&vec);
  67     });
  68 }
  69
  70 #[bench]
  71 fn starts_with_same_vector(b: &mut Bencher) {
  72     let vec: Vec<_> = (0..100).collect();
  73     b.iter(|| vec.starts_with(&vec))
  74 }
  75
  76 #[bench]
  77 fn starts_with_single_element(b: &mut Bencher) {
  78     let vec: Vec<_> = vec![0];
  79     b.iter(|| vec.starts_with(&vec))
  80 }
  81
  82 #[bench]
  83 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
  84     let vec: Vec<_> = (0..100).collect();
  85     let mut match_vec: Vec<_> = (0..99).collect();
  86     match_vec.push(0);
  87     b.iter(|| vec.starts_with(&match_vec))
  88 }
  89
  90 #[bench]
  91 fn ends_with_same_vector(b: &mut Bencher) {
  92     let vec: Vec<_> = (0..100).collect();
  93     b.iter(|| vec.ends_with(&vec))
  94 }
  95
  96 #[bench]
  97 fn ends_with_single_element(b: &mut Bencher) {
  98     let vec: Vec<_> = vec![0];
  99     b.iter(|| vec.ends_with(&vec))
 100 }
 101
 102 #[bench]
 103 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
 104     let vec: Vec<_> = (0..100).collect();
 105     let mut match_vec: Vec<_> = (0..100).collect();
 106     match_vec[0] = 200;
 107     b.iter(|| vec.starts_with(&match_vec))
 108 }
 109
 110 #[bench]
 111 fn contains_last_element(b: &mut Bencher) {
 112     let vec: Vec<_> = (0..100).collect();
 113     b.iter(|| vec.contains(&99))
 114 }
 115
 116 #[bench]
 117 fn zero_1kb_from_elem(b: &mut Bencher) {
 118     b.iter(|| vec![0u8; 1024]);
 119 }
 120
 121 #[bench]
 122 fn zero_1kb_set_memory(b: &mut Bencher) {
 123     b.iter(|| {
 124         let mut v = Vec::<u8>::with_capacity(1024);
 125         unsafe {
 126             let vp = v.as_mut_ptr();
 127             ptr::write_bytes(vp, 0, 1024);
 128             v.set_len(1024);
 129         }
 130         v
 131     });
 132 }
 133
 134 #[bench]
 135 fn zero_1kb_loop_set(b: &mut Bencher) {
 136     b.iter(|| {
 137         let mut v = Vec::<u8>::with_capacity(1024);
 138         unsafe {
 139             v.set_len(1024);
 140         }
 141         for i in 0..1024 {
 142             v[i] = 0;
 143         }
 144     });
 145 }
 146
 147 #[bench]
 148 fn zero_1kb_mut_iter(b: &mut Bencher) {
 149     b.iter(|| {
 150         let mut v = Vec::<u8>::with_capacity(1024);
 151         unsafe {
 152             v.set_len(1024);
 153         }
 154         for x in &mut v {
 155             *x = 0;
 156         }
 157         v
 158     });
 159 }
 160
 161 #[bench]
 162 fn random_inserts(b: &mut Bencher) {
 163     let mut rng = thread_rng();
 164     b.iter(|| {
 165         let mut v = vec![(0, 0); 30];
 166         for _ in 0..100 {
 167             let l = v.len();
 168             v.insert(rng.gen::<usize>() % (l + 1), (1, 1));
 169         }
 170     })
 171 }
 172
 173 #[bench]
 174 fn random_removes(b: &mut Bencher) {
 175     let mut rng = thread_rng();
 176     b.iter(|| {
 177         let mut v = vec![(0, 0); 130];
 178         for _ in 0..100 {
 179             let l = v.len();
 180             v.remove(rng.gen::<usize>() % l);
 181         }
 182     })
 183 }
 184
 185 fn gen_ascending(len: usize) -> Vec<u64> {
 186     (0..len as u64).collect()
 187 }
 188
 189 fn gen_descending(len: usize) -> Vec<u64> {
 190     (0..len as u64).rev().collect()
 191 }
 192
 193 fn gen_random(len: usize) -> Vec<u64> {
 194     let mut rng = thread_rng();
 195     rng.gen_iter::<u64>().take(len).collect()
 196 }
 197
 198 fn gen_mostly_ascending(len: usize) -> Vec<u64> {
 199     let mut rng = thread_rng();
 200     let mut v = gen_ascending(len);
 201     for _ in (0usize..).take_while(|x| x * x <= len) {
 202         let x = rng.gen::<usize>() % len;
 203         let y = rng.gen::<usize>() % len;
 204         v.swap(x, y);
 205     }
 206     v
 207 }
 208
 209 fn gen_mostly_descending(len: usize) -> Vec<u64> {
 210     let mut rng = thread_rng();
 211     let mut v = gen_descending(len);
 212     for _ in (0usize..).take_while(|x| x * x <= len) {
 213         let x = rng.gen::<usize>() % len;
 214         let y = rng.gen::<usize>() % len;
 215         v.swap(x, y);
 216     }
 217     v
 218 }
 219
 220 fn gen_strings(len: usize) -> Vec<String> {
 221     let mut rng = thread_rng();
 222     let mut v = vec![];
 223     for _ in 0..len {
 224         let n = rng.gen::<usize>() % 20 + 1;
 225         v.push(rng.gen_ascii_chars().take(n).collect());
 226     }
 227     v
 228 }
 229
 230 fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
 231     let mut rng = thread_rng();
 232     rng.gen_iter().map(|x| [x; 16]).take(len).collect()
 233 }
 234
 235 macro_rules! sort {
 236     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 237         #[bench]
 238         fn $name(b: &mut Bencher) {
 239             b.iter(|| $gen($len).$f());
 240             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
 241         }
 242     }
 243 }
 244
 245 macro_rules! sort_expensive {
 246     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 247         #[bench]
 248         fn $name(b: &mut Bencher) {
 249             b.iter(|| {
 250                 let mut v = $gen($len);
 251                 let mut count = 0;
 252                 v.$f(|a: &u64, b: &u64| {
 253                     count += 1;
 254                     if count % 1_000_000_000 == 0 {
 255                         panic!("should not happen");
 256                     }
 257                     (*a as f64).cos().partial_cmp(&(*b as f64).cos()).unwrap()
 258                 });
 259                 black_box(count);
 260             });
 261             b.bytes = $len as u64 * mem::size_of::<u64>() as u64;
 262         }
 263     }
 264 }
 265
 266 sort!(sort, sort_small_ascending, gen_ascending, 10);
 267 sort!(sort, sort_small_descending, gen_descending, 10);
 268 sort!(sort, sort_small_random, gen_random, 10);
 269 sort!(sort, sort_small_big_random, gen_big_random, 10);
 270 sort!(sort, sort_medium_random, gen_random, 100);
 271 sort!(sort, sort_large_ascending, gen_ascending, 10000);
 272 sort!(sort, sort_large_descending, gen_descending, 10000);
 273 sort!(sort, sort_large_mostly_ascending, gen_mostly_ascending, 10000);
 274 sort!(sort, sort_large_mostly_descending, gen_mostly_descending, 10000);
 275 sort!(sort, sort_large_random, gen_random, 10000);
 276 sort!(sort, sort_large_big_random, gen_big_random, 10000);
 277 sort!(sort, sort_large_strings, gen_strings, 10000);
 278 sort_expensive!(sort_by, sort_large_random_expensive, gen_random, 10000);
 279
 280 sort!(sort_unstable, sort_unstable_small_ascending, gen_ascending, 10);
 281 sort!(sort_unstable, sort_unstable_small_descending, gen_descending, 10);
 282 sort!(sort_unstable, sort_unstable_small_random, gen_random, 10);
 283 sort!(sort_unstable, sort_unstable_small_big_random, gen_big_random, 10);
 284 sort!(sort_unstable, sort_unstable_medium_random, gen_random, 100);
 285 sort!(sort_unstable, sort_unstable_large_ascending, gen_ascending, 10000);
 286 sort!(sort_unstable, sort_unstable_large_descending, gen_descending, 10000);
 287 sort!(sort_unstable, sort_unstable_large_mostly_ascending, gen_mostly_ascending, 10000);
 288 sort!(sort_unstable, sort_unstable_large_mostly_descending, gen_mostly_descending, 10000);
 289 sort!(sort_unstable, sort_unstable_large_random, gen_random, 10000);
 290 sort!(sort_unstable, sort_unstable_large_big_random, gen_big_random, 10000);
 291 sort!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
 292 sort_expensive!(sort_unstable_by, sort_unstable_large_random_expensive, gen_random, 10000);
 293
 294 macro_rules! reverse {
 295     ($name:ident, $ty:ty, $f:expr) => {
 296         #[bench]
 297         fn $name(b: &mut Bencher) {
 298             // odd length and offset by 1 to be as unaligned as possible
 299             let n = 0xFFFFF;
 300             let mut v: Vec<_> =
 301                 (0..1+(n / mem::size_of::<$ty>() as u64))
 302                 .map($f)
 303                 .collect();
 304             b.iter(|| black_box(&mut v[1..]).reverse());
 305             b.bytes = n;
 306         }
 307     }
 308 }
 309
 310 reverse!(reverse_u8, u8, |x| x as u8);
 311 reverse!(reverse_u16, u16, |x| x as u16);
 312 reverse!(reverse_u8x3, [u8;3], |x| [x as u8, (x>>8) as u8, (x>>16) as u8]);
 313 reverse!(reverse_u32, u32, |x| x as u32);
 314 reverse!(reverse_u64, u64, |x| x as u64);
 315 reverse!(reverse_u128, u128, |x| x as u128);
 316 #[repr(simd)] struct F64x4(f64, f64, f64, f64);
 317 reverse!(reverse_simd_f64x4, F64x4, |x| { let x = x as f64; F64x4(x,x,x,x) });