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 #[bench]
 173 fn random_removes(b: &mut Bencher) {
 174     let mut rng = thread_rng();
 175     b.iter(|| {
 176         let mut v = vec![(0, 0); 130];
 177         for _ in 0..100 {
 178             let l = v.len();
 179             v.remove(rng.gen::<usize>() % l);
 180         }
 181     })
 182 }
 183
 184 fn gen_ascending(len: usize) -> Vec<u64> {
 185     (0..len as u64).collect()
 186 }
 187
 188 fn gen_descending(len: usize) -> Vec<u64> {
 189     (0..len as u64).rev().collect()
 190 }
 191
 192 fn gen_random(len: usize) -> Vec<u64> {
 193     let mut rng = thread_rng();
 194     rng.gen_iter::<u64>().take(len).collect()
 195 }
 196
 197 fn gen_mostly_ascending(len: usize) -> Vec<u64> {
 198     let mut rng = thread_rng();
 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 = thread_rng();
 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_big_random(len: usize) -> Vec<[u64; 16]> {
 220     let mut rng = thread_rng();
 221     rng.gen_iter().map(|x| [x; 16]).take(len).collect()
 222 }
 223
 224 fn gen_big_ascending(len: usize) -> Vec<[u64; 16]> {
 225     (0..len as u64).map(|x| [x; 16]).take(len).collect()
 226 }
 227
 228 fn gen_big_descending(len: usize) -> Vec<[u64; 16]> {
 229     (0..len as u64).rev().map(|x| [x; 16]).take(len).collect()
 230 }
 231
 232 macro_rules! sort_bench {
 233     ($name:ident, $gen:expr, $len:expr) => {
 234         #[bench]
 235         fn $name(b: &mut Bencher) {
 236             b.iter(|| $gen($len).sort());
 237             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
 238         }
 239     }
 240 }
 241
 242 sort_bench!(sort_small_random, gen_random, 10);
 243 sort_bench!(sort_small_ascending, gen_ascending, 10);
 244 sort_bench!(sort_small_descending, gen_descending, 10);
 245
 246 sort_bench!(sort_small_big_random, gen_big_random, 10);
 247 sort_bench!(sort_small_big_ascending, gen_big_ascending, 10);
 248 sort_bench!(sort_small_big_descending, gen_big_descending, 10);
 249
 250 sort_bench!(sort_medium_random, gen_random, 100);
 251 sort_bench!(sort_medium_ascending, gen_ascending, 100);
 252 sort_bench!(sort_medium_descending, gen_descending, 100);
 253
 254 sort_bench!(sort_large_random, gen_random, 10000);
 255 sort_bench!(sort_large_ascending, gen_ascending, 10000);
 256 sort_bench!(sort_large_descending, gen_descending, 10000);
 257 sort_bench!(sort_large_mostly_ascending, gen_mostly_ascending, 10000);
 258 sort_bench!(sort_large_mostly_descending, gen_mostly_descending, 10000);
 259
 260 sort_bench!(sort_large_big_random, gen_big_random, 10000);
 261 sort_bench!(sort_large_big_ascending, gen_big_ascending, 10000);
 262 sort_bench!(sort_large_big_descending, gen_big_descending, 10000);
 263
 264 #[bench]
 265 fn sort_large_random_expensive(b: &mut Bencher) {
 266     let len = 10000;
 267     b.iter(|| {
 268         let mut v = gen_random(len);
 269         let mut count = 0;
 270         v.sort_by(|a: &u64, b: &u64| {
 271             count += 1;
 272             if count % 1_000_000_000 == 0 {
 273                 panic!("should not happen");
 274             }
 275             (*a as f64).cos().partial_cmp(&(*b as f64).cos()).unwrap()
 276         });
 277         black_box(count);
 278     });
 279     b.bytes = len as u64 * mem::size_of::<u64>() as u64;
 280 }