library/alloc/benches/slice.rs

   1 use std::{mem, ptr};
   2
   3 use rand::distributions::{Alphanumeric, DistString, Standard};
   4 use rand::Rng;
   5 use test::{black_box, Bencher};
   6
   7 #[bench]
   8 fn iterator(b: &mut Bencher) {
   9     // peculiar numbers to stop LLVM from optimising the summation
  10     // out.
  11     let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
  12
  13     b.iter(|| {
  14         let mut sum = 0;
  15         for x in &v {
  16             sum += *x;
  17         }
  18         // sum == 11806, to stop dead code elimination.
  19         if sum == 0 {
  20             panic!()
  21         }
  22     })
  23 }
  24
  25 #[bench]
  26 fn mut_iterator(b: &mut Bencher) {
  27     let mut v = vec![0; 100];
  28
  29     b.iter(|| {
  30         let mut i = 0;
  31         for x in &mut v {
  32             *x = i;
  33             i += 1;
  34         }
  35     })
  36 }
  37
  38 #[bench]
  39 fn concat(b: &mut Bencher) {
  40     let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
  41     b.iter(|| {
  42         xss.concat();
  43     });
  44 }
  45
  46 #[bench]
  47 fn join(b: &mut Bencher) {
  48     let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
  49     b.iter(|| xss.join(&0));
  50 }
  51
  52 #[bench]
  53 fn push(b: &mut Bencher) {
  54     let mut vec = Vec::<i32>::new();
  55     b.iter(|| {
  56         vec.push(0);
  57         black_box(&vec);
  58     });
  59 }
  60
  61 #[bench]
  62 fn starts_with_same_vector(b: &mut Bencher) {
  63     let vec: Vec<_> = (0..100).collect();
  64     b.iter(|| vec.starts_with(&vec))
  65 }
  66
  67 #[bench]
  68 fn starts_with_single_element(b: &mut Bencher) {
  69     let vec: Vec<_> = vec![0];
  70     b.iter(|| vec.starts_with(&vec))
  71 }
  72
  73 #[bench]
  74 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
  75     let vec: Vec<_> = (0..100).collect();
  76     let mut match_vec: Vec<_> = (0..99).collect();
  77     match_vec.push(0);
  78     b.iter(|| vec.starts_with(&match_vec))
  79 }
  80
  81 #[bench]
  82 fn ends_with_same_vector(b: &mut Bencher) {
  83     let vec: Vec<_> = (0..100).collect();
  84     b.iter(|| vec.ends_with(&vec))
  85 }
  86
  87 #[bench]
  88 fn ends_with_single_element(b: &mut Bencher) {
  89     let vec: Vec<_> = vec![0];
  90     b.iter(|| vec.ends_with(&vec))
  91 }
  92
  93 #[bench]
  94 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
  95     let vec: Vec<_> = (0..100).collect();
  96     let mut match_vec: Vec<_> = (0..100).collect();
  97     match_vec[0] = 200;
  98     b.iter(|| vec.starts_with(&match_vec))
  99 }
 100
 101 #[bench]
 102 fn contains_last_element(b: &mut Bencher) {
 103     let vec: Vec<_> = (0..100).collect();
 104     b.iter(|| vec.contains(&99))
 105 }
 106
 107 #[bench]
 108 fn zero_1kb_from_elem(b: &mut Bencher) {
 109     b.iter(|| vec![0u8; 1024]);
 110 }
 111
 112 #[bench]
 113 fn zero_1kb_set_memory(b: &mut Bencher) {
 114     b.iter(|| {
 115         let mut v = Vec::<u8>::with_capacity(1024);
 116         unsafe {
 117             let vp = v.as_mut_ptr();
 118             ptr::write_bytes(vp, 0, 1024);
 119             v.set_len(1024);
 120         }
 121         v
 122     });
 123 }
 124
 125 #[bench]
 126 fn zero_1kb_loop_set(b: &mut Bencher) {
 127     b.iter(|| {
 128         let mut v = Vec::<u8>::with_capacity(1024);
 129         unsafe {
 130             v.set_len(1024);
 131         }
 132         for i in 0..1024 {
 133             v[i] = 0;
 134         }
 135     });
 136 }
 137
 138 #[bench]
 139 fn zero_1kb_mut_iter(b: &mut Bencher) {
 140     b.iter(|| {
 141         let mut v = Vec::<u8>::with_capacity(1024);
 142         unsafe {
 143             v.set_len(1024);
 144         }
 145         for x in &mut v {
 146             *x = 0;
 147         }
 148         v
 149     });
 150 }
 151
 152 #[bench]
 153 fn random_inserts(b: &mut Bencher) {
 154     let mut rng = crate::bench_rng();
 155     b.iter(|| {
 156         let mut v = vec![(0, 0); 30];
 157         for _ in 0..100 {
 158             let l = v.len();
 159             v.insert(rng.gen::<usize>() % (l + 1), (1, 1));
 160         }
 161     })
 162 }
 163
 164 #[bench]
 165 fn random_removes(b: &mut Bencher) {
 166     let mut rng = crate::bench_rng();
 167     b.iter(|| {
 168         let mut v = vec![(0, 0); 130];
 169         for _ in 0..100 {
 170             let l = v.len();
 171             v.remove(rng.gen::<usize>() % l);
 172         }
 173     })
 174 }
 175
 176 fn gen_ascending(len: usize) -> Vec<u64> {
 177     (0..len as u64).collect()
 178 }
 179
 180 fn gen_descending(len: usize) -> Vec<u64> {
 181     (0..len as u64).rev().collect()
 182 }
 183
 184 fn gen_random(len: usize) -> Vec<u64> {
 185     let mut rng = crate::bench_rng();
 186     (&mut rng).sample_iter(&Standard).take(len).collect()
 187 }
 188
 189 fn gen_random_bytes(len: usize) -> Vec<u8> {
 190     let mut rng = crate::bench_rng();
 191     (&mut rng).sample_iter(&Standard).take(len).collect()
 192 }
 193
 194 fn gen_mostly_ascending(len: usize) -> Vec<u64> {
 195     let mut rng = crate::bench_rng();
 196     let mut v = gen_ascending(len);
 197     for _ in (0usize..).take_while(|x| x * x <= len) {
 198         let x = rng.gen::<usize>() % len;
 199         let y = rng.gen::<usize>() % len;
 200         v.swap(x, y);
 201     }
 202     v
 203 }
 204
 205 fn gen_mostly_descending(len: usize) -> Vec<u64> {
 206     let mut rng = crate::bench_rng();
 207     let mut v = gen_descending(len);
 208     for _ in (0usize..).take_while(|x| x * x <= len) {
 209         let x = rng.gen::<usize>() % len;
 210         let y = rng.gen::<usize>() % len;
 211         v.swap(x, y);
 212     }
 213     v
 214 }
 215
 216 fn gen_strings(len: usize) -> Vec<String> {
 217     let mut rng = crate::bench_rng();
 218     let mut v = vec![];
 219     for _ in 0..len {
 220         let n = rng.gen::<usize>() % 20 + 1;
 221         v.push(Alphanumeric.sample_string(&mut rng, n));
 222     }
 223     v
 224 }
 225
 226 fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
 227     let mut rng = crate::bench_rng();
 228     (&mut rng).sample_iter(&Standard).map(|x| [x; 16]).take(len).collect()
 229 }
 230
 231 macro_rules! sort {
 232     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 233         #[bench]
 234         fn $name(b: &mut Bencher) {
 235             let v = $gen($len);
 236             b.iter(|| v.clone().$f());
 237             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
 238         }
 239     };
 240 }
 241
 242 macro_rules! sort_strings {
 243     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 244         #[bench]
 245         fn $name(b: &mut Bencher) {
 246             let v = $gen($len);
 247             let v = v.iter().map(|s| &**s).collect::<Vec<&str>>();
 248             b.iter(|| v.clone().$f());
 249             b.bytes = $len * mem::size_of::<&str>() as u64;
 250         }
 251     };
 252 }
 253
 254 macro_rules! sort_expensive {
 255     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 256         #[bench]
 257         fn $name(b: &mut Bencher) {
 258             let v = $gen($len);
 259             b.iter(|| {
 260                 let mut v = v.clone();
 261                 let mut count = 0;
 262                 v.$f(|a: &u64, b: &u64| {
 263                     count += 1;
 264                     if count % 1_000_000_000 == 0 {
 265                         panic!("should not happen");
 266                     }
 267                     (*a as f64).cos().partial_cmp(&(*b as f64).cos()).unwrap()
 268                 });
 269                 black_box(count);
 270             });
 271             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
 272         }
 273     };
 274 }
 275
 276 macro_rules! sort_lexicographic {
 277     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
 278         #[bench]
 279         fn $name(b: &mut Bencher) {
 280             let v = $gen($len);
 281             b.iter(|| v.clone().$f(|x| x.to_string()));
 282             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
 283         }
 284     };
 285 }
 286
 287 sort!(sort, sort_small_ascending, gen_ascending, 10);
 288 sort!(sort, sort_small_descending, gen_descending, 10);
 289 sort!(sort, sort_small_random, gen_random, 10);
 290 sort!(sort, sort_small_big, gen_big_random, 10);
 291 sort!(sort, sort_medium_random, gen_random, 100);
 292 sort!(sort, sort_large_ascending, gen_ascending, 10000);
 293 sort!(sort, sort_large_descending, gen_descending, 10000);
 294 sort!(sort, sort_large_mostly_ascending, gen_mostly_ascending, 10000);
 295 sort!(sort, sort_large_mostly_descending, gen_mostly_descending, 10000);
 296 sort!(sort, sort_large_random, gen_random, 10000);
 297 sort!(sort, sort_large_big, gen_big_random, 10000);
 298 sort_strings!(sort, sort_large_strings, gen_strings, 10000);
 299 sort_expensive!(sort_by, sort_large_expensive, gen_random, 10000);
 300
 301 sort!(sort_unstable, sort_unstable_small_ascending, gen_ascending, 10);
 302 sort!(sort_unstable, sort_unstable_small_descending, gen_descending, 10);
 303 sort!(sort_unstable, sort_unstable_small_random, gen_random, 10);
 304 sort!(sort_unstable, sort_unstable_small_big, gen_big_random, 10);
 305 sort!(sort_unstable, sort_unstable_medium_random, gen_random, 100);
 306 sort!(sort_unstable, sort_unstable_large_ascending, gen_ascending, 10000);
 307 sort!(sort_unstable, sort_unstable_large_descending, gen_descending, 10000);
 308 sort!(sort_unstable, sort_unstable_large_mostly_ascending, gen_mostly_ascending, 10000);
 309 sort!(sort_unstable, sort_unstable_large_mostly_descending, gen_mostly_descending, 10000);
 310 sort!(sort_unstable, sort_unstable_large_random, gen_random, 10000);
 311 sort!(sort_unstable, sort_unstable_large_big, gen_big_random, 10000);
 312 sort_strings!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
 313 sort_expensive!(sort_unstable_by, sort_unstable_large_expensive, gen_random, 10000);
 314
 315 sort_lexicographic!(sort_by_key, sort_by_key_lexicographic, gen_random, 10000);
 316 sort_lexicographic!(sort_unstable_by_key, sort_unstable_by_key_lexicographic, gen_random, 10000);
 317 sort_lexicographic!(sort_by_cached_key, sort_by_cached_key_lexicographic, gen_random, 10000);
 318
 319 macro_rules! reverse {
 320     ($name:ident, $ty:ty, $f:expr) => {
 321         #[bench]
 322         fn $name(b: &mut Bencher) {
 323             // odd length and offset by 1 to be as unaligned as possible
 324             let n = 0xFFFFF;
 325             let mut v: Vec<_> = (0..1 + (n / mem::size_of::<$ty>() as u64)).map($f).collect();
 326             b.iter(|| black_box(&mut v[1..]).reverse());
 327             b.bytes = n;
 328         }
 329     };
 330 }
 331
 332 reverse!(reverse_u8, u8, |x| x as u8);
 333 reverse!(reverse_u16, u16, |x| x as u16);
 334 reverse!(reverse_u8x3, [u8; 3], |x| [x as u8, (x >> 8) as u8, (x >> 16) as u8]);
 335 reverse!(reverse_u32, u32, |x| x as u32);
 336 reverse!(reverse_u64, u64, |x| x as u64);
 337 reverse!(reverse_u128, u128, |x| x as u128);
 338 #[repr(simd)]
 339 struct F64x4(f64, f64, f64, f64);
 340 reverse!(reverse_simd_f64x4, F64x4, |x| {
 341     let x = x as f64;
 342     F64x4(x, x, x, x)
 343 });
 344
 345 macro_rules! rotate {
 346     ($name:ident, $gen:expr, $len:expr, $mid:expr) => {
 347         #[bench]
 348         fn $name(b: &mut Bencher) {
 349             let size = mem::size_of_val(&$gen(1)[0]);
 350             let mut v = $gen($len * 8 / size);
 351             b.iter(|| black_box(&mut v).rotate_left(($mid * 8 + size - 1) / size));
 352             b.bytes = (v.len() * size) as u64;
 353         }
 354     };
 355 }
 356
 357 rotate!(rotate_tiny_by1, gen_random, 16, 1);
 358 rotate!(rotate_tiny_half, gen_random, 16, 16 / 2);
 359 rotate!(rotate_tiny_half_plus_one, gen_random, 16, 16 / 2 + 1);
 360
 361 rotate!(rotate_medium_by1, gen_random, 9158, 1);
 362 rotate!(rotate_medium_by727_u64, gen_random, 9158, 727);
 363 rotate!(rotate_medium_by727_bytes, gen_random_bytes, 9158, 727);
 364 rotate!(rotate_medium_by727_strings, gen_strings, 9158, 727);
 365 rotate!(rotate_medium_half, gen_random, 9158, 9158 / 2);
 366 rotate!(rotate_medium_half_plus_one, gen_random, 9158, 9158 / 2 + 1);
 367
 368 // Intended to use more RAM than the machine has cache
 369 rotate!(rotate_huge_by1, gen_random, 5 * 1024 * 1024, 1);
 370 rotate!(rotate_huge_by9199_u64, gen_random, 5 * 1024 * 1024, 9199);
 371 rotate!(rotate_huge_by9199_bytes, gen_random_bytes, 5 * 1024 * 1024, 9199);
 372 rotate!(rotate_huge_by9199_strings, gen_strings, 5 * 1024 * 1024, 9199);
 373 rotate!(rotate_huge_by9199_big, gen_big_random, 5 * 1024 * 1024, 9199);
 374 rotate!(rotate_huge_by1234577_u64, gen_random, 5 * 1024 * 1024, 1234577);
 375 rotate!(rotate_huge_by1234577_bytes, gen_random_bytes, 5 * 1024 * 1024, 1234577);
 376 rotate!(rotate_huge_by1234577_strings, gen_strings, 5 * 1024 * 1024, 1234577);
 377 rotate!(rotate_huge_by1234577_big, gen_big_random, 5 * 1024 * 1024, 1234577);
 378 rotate!(rotate_huge_half, gen_random, 5 * 1024 * 1024, 5 * 1024 * 1024 / 2);
 379 rotate!(rotate_huge_half_plus_one, gen_random, 5 * 1024 * 1024, 5 * 1024 * 1024 / 2 + 1);