library/alloc/benches/slice.rs

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