library/core/benches/iter.rs

   1 use core::iter::*;
   2 use test::{black_box, Bencher};
   3
   4 #[bench]
   5 fn bench_rposition(b: &mut Bencher) {
   6     let it: Vec<usize> = (0..300).collect();
   7     b.iter(|| {
   8         it.iter().rposition(|&x| x <= 150);
   9     });
  10 }
  11
  12 #[bench]
  13 fn bench_skip_while(b: &mut Bencher) {
  14     b.iter(|| {
  15         let it = 0..100;
  16         let mut sum = 0;
  17         it.skip_while(|&x| {
  18             sum += x;
  19             sum < 4000
  20         })
  21         .all(|_| true);
  22     });
  23 }
  24
  25 #[bench]
  26 fn bench_multiple_take(b: &mut Bencher) {
  27     let mut it = (0..42).cycle();
  28     b.iter(|| {
  29         let n = it.next().unwrap();
  30         for _ in 0..n {
  31             it.clone().take(it.next().unwrap()).all(|_| true);
  32         }
  33     });
  34 }
  35
  36 fn scatter(x: i32) -> i32 {
  37     (x * 31) % 127
  38 }
  39
  40 #[bench]
  41 fn bench_max_by_key(b: &mut Bencher) {
  42     b.iter(|| {
  43         let it = 0..100;
  44         it.map(black_box).max_by_key(|&x| scatter(x))
  45     })
  46 }
  47
  48 // https://www.reddit.com/r/rust/comments/31syce/using_iterators_to_find_the_index_of_the_min_or/
  49 #[bench]
  50 fn bench_max_by_key2(b: &mut Bencher) {
  51     fn max_index_iter(array: &[i32]) -> usize {
  52         array.iter().enumerate().max_by_key(|&(_, item)| item).unwrap().0
  53     }
  54
  55     let mut data = vec![0; 1638];
  56     data[514] = 9999;
  57
  58     b.iter(|| max_index_iter(&data));
  59 }
  60
  61 #[bench]
  62 fn bench_max(b: &mut Bencher) {
  63     b.iter(|| {
  64         let it = 0..100;
  65         it.map(black_box).map(scatter).max()
  66     })
  67 }
  68
  69 pub fn copy_zip(xs: &[u8], ys: &mut [u8]) {
  70     for (a, b) in ys.iter_mut().zip(xs) {
  71         *a = *b;
  72     }
  73 }
  74
  75 pub fn add_zip(xs: &[f32], ys: &mut [f32]) {
  76     for (a, b) in ys.iter_mut().zip(xs) {
  77         *a += *b;
  78     }
  79 }
  80
  81 #[bench]
  82 fn bench_zip_copy(b: &mut Bencher) {
  83     let source = vec![0u8; 16 * 1024];
  84     let mut dst = black_box(vec![0u8; 16 * 1024]);
  85     b.iter(|| copy_zip(&source, &mut dst))
  86 }
  87
  88 #[bench]
  89 fn bench_zip_add(b: &mut Bencher) {
  90     let source = vec![1.; 16 * 1024];
  91     let mut dst = vec![0.; 16 * 1024];
  92     b.iter(|| add_zip(&source, &mut dst));
  93 }
  94
  95 /// `Iterator::for_each` implemented as a plain loop.
  96 fn for_each_loop<I, F>(iter: I, mut f: F)
  97 where
  98     I: Iterator,
  99     F: FnMut(I::Item),
 100 {
 101     for item in iter {
 102         f(item);
 103     }
 104 }
 105
 106 /// `Iterator::for_each` implemented with `fold` for internal iteration.
 107 /// (except when `by_ref()` effectively disables that optimization.)
 108 fn for_each_fold<I, F>(iter: I, mut f: F)
 109 where
 110     I: Iterator,
 111     F: FnMut(I::Item),
 112 {
 113     iter.fold((), move |(), item| f(item));
 114 }
 115
 116 #[bench]
 117 fn bench_for_each_chain_loop(b: &mut Bencher) {
 118     b.iter(|| {
 119         let mut acc = 0;
 120         let iter = (0i64..1000000).chain(0..1000000).map(black_box);
 121         for_each_loop(iter, |x| acc += x);
 122         acc
 123     });
 124 }
 125
 126 #[bench]
 127 fn bench_for_each_chain_fold(b: &mut Bencher) {
 128     b.iter(|| {
 129         let mut acc = 0;
 130         let iter = (0i64..1000000).chain(0..1000000).map(black_box);
 131         for_each_fold(iter, |x| acc += x);
 132         acc
 133     });
 134 }
 135
 136 #[bench]
 137 fn bench_for_each_chain_ref_fold(b: &mut Bencher) {
 138     b.iter(|| {
 139         let mut acc = 0;
 140         let mut iter = (0i64..1000000).chain(0..1000000).map(black_box);
 141         for_each_fold(iter.by_ref(), |x| acc += x);
 142         acc
 143     });
 144 }
 145
 146 /// Helper to benchmark `sum` for iterators taken by value which
 147 /// can optimize `fold`, and by reference which cannot.
 148 macro_rules! bench_sums {
 149     ($bench_sum:ident, $bench_ref_sum:ident, $iter:expr) => {
 150         #[bench]
 151         fn $bench_sum(b: &mut Bencher) {
 152             b.iter(|| -> i64 { $iter.map(black_box).sum() });
 153         }
 154
 155         #[bench]
 156         fn $bench_ref_sum(b: &mut Bencher) {
 157             b.iter(|| -> i64 { $iter.map(black_box).by_ref().sum() });
 158         }
 159     };
 160 }
 161
 162 bench_sums! {
 163     bench_flat_map_sum,
 164     bench_flat_map_ref_sum,
 165     (0i64..1000).flat_map(|x| x..x+1000)
 166 }
 167
 168 bench_sums! {
 169     bench_flat_map_chain_sum,
 170     bench_flat_map_chain_ref_sum,
 171     (0i64..1000000).flat_map(|x| once(x).chain(once(x)))
 172 }
 173
 174 bench_sums! {
 175     bench_enumerate_sum,
 176     bench_enumerate_ref_sum,
 177     (0i64..1000000).enumerate().map(|(i, x)| x * i as i64)
 178 }
 179
 180 bench_sums! {
 181     bench_enumerate_chain_sum,
 182     bench_enumerate_chain_ref_sum,
 183     (0i64..1000000).chain(0..1000000).enumerate().map(|(i, x)| x * i as i64)
 184 }
 185
 186 bench_sums! {
 187     bench_filter_sum,
 188     bench_filter_ref_sum,
 189     (0i64..1000000).filter(|x| x % 3 == 0)
 190 }
 191
 192 bench_sums! {
 193     bench_filter_chain_sum,
 194     bench_filter_chain_ref_sum,
 195     (0i64..1000000).chain(0..1000000).filter(|x| x % 3 == 0)
 196 }
 197
 198 bench_sums! {
 199     bench_filter_map_sum,
 200     bench_filter_map_ref_sum,
 201     (0i64..1000000).filter_map(|x| x.checked_mul(x))
 202 }
 203
 204 bench_sums! {
 205     bench_filter_map_chain_sum,
 206     bench_filter_map_chain_ref_sum,
 207     (0i64..1000000).chain(0..1000000).filter_map(|x| x.checked_mul(x))
 208 }
 209
 210 bench_sums! {
 211     bench_fuse_sum,
 212     bench_fuse_ref_sum,
 213     (0i64..1000000).fuse()
 214 }
 215
 216 bench_sums! {
 217     bench_fuse_chain_sum,
 218     bench_fuse_chain_ref_sum,
 219     (0i64..1000000).chain(0..1000000).fuse()
 220 }
 221
 222 bench_sums! {
 223     bench_inspect_sum,
 224     bench_inspect_ref_sum,
 225     (0i64..1000000).inspect(|_| {})
 226 }
 227
 228 bench_sums! {
 229     bench_inspect_chain_sum,
 230     bench_inspect_chain_ref_sum,
 231     (0i64..1000000).chain(0..1000000).inspect(|_| {})
 232 }
 233
 234 bench_sums! {
 235     bench_peekable_sum,
 236     bench_peekable_ref_sum,
 237     (0i64..1000000).peekable()
 238 }
 239
 240 bench_sums! {
 241     bench_peekable_chain_sum,
 242     bench_peekable_chain_ref_sum,
 243     (0i64..1000000).chain(0..1000000).peekable()
 244 }
 245
 246 bench_sums! {
 247     bench_skip_sum,
 248     bench_skip_ref_sum,
 249     (0i64..1000000).skip(1000)
 250 }
 251
 252 bench_sums! {
 253     bench_skip_chain_sum,
 254     bench_skip_chain_ref_sum,
 255     (0i64..1000000).chain(0..1000000).skip(1000)
 256 }
 257
 258 bench_sums! {
 259     bench_skip_while_sum,
 260     bench_skip_while_ref_sum,
 261     (0i64..1000000).skip_while(|&x| x < 1000)
 262 }
 263
 264 bench_sums! {
 265     bench_skip_while_chain_sum,
 266     bench_skip_while_chain_ref_sum,
 267     (0i64..1000000).chain(0..1000000).skip_while(|&x| x < 1000)
 268 }
 269
 270 bench_sums! {
 271     bench_take_while_chain_sum,
 272     bench_take_while_chain_ref_sum,
 273     (0i64..1000000).chain(1000000..).take_while(|&x| x < 1111111)
 274 }
 275
 276 bench_sums! {
 277     bench_cycle_take_sum,
 278     bench_cycle_take_ref_sum,
 279     (0..10000).cycle().take(1000000)
 280 }
 281
 282 bench_sums! {
 283     bench_cycle_skip_take_sum,
 284     bench_cycle_skip_take_ref_sum,
 285     (0..100000).cycle().skip(1000000).take(1000000)
 286 }
 287
 288 bench_sums! {
 289     bench_cycle_take_skip_sum,
 290     bench_cycle_take_skip_ref_sum,
 291     (0..100000).cycle().take(1000000).skip(100000)
 292 }
 293
 294 bench_sums! {
 295     bench_skip_cycle_skip_zip_add_sum,
 296     bench_skip_cycle_skip_zip_add_ref_sum,
 297     (0..100000).skip(100).cycle().skip(100)
 298       .zip((0..100000).cycle().skip(10))
 299       .map(|(a,b)| a+b)
 300       .skip(100000)
 301       .take(1000000)
 302 }
 303
 304 // Checks whether Skip<Zip<A,B>> is as fast as Zip<Skip<A>, Skip<B>>, from
 305 // https://users.rust-lang.org/t/performance-difference-between-iterator-zip-and-skip-order/15743
 306 #[bench]
 307 fn bench_zip_then_skip(b: &mut Bencher) {
 308     let v: Vec<_> = (0..100_000).collect();
 309     let t: Vec<_> = (0..100_000).collect();
 310
 311     b.iter(|| {
 312         let s = v
 313             .iter()
 314             .zip(t.iter())
 315             .skip(10000)
 316             .take_while(|t| *t.0 < 10100)
 317             .map(|(a, b)| *a + *b)
 318             .sum::<u64>();
 319         assert_eq!(s, 2009900);
 320     });
 321 }
 322 #[bench]
 323 fn bench_skip_then_zip(b: &mut Bencher) {
 324     let v: Vec<_> = (0..100_000).collect();
 325     let t: Vec<_> = (0..100_000).collect();
 326
 327     b.iter(|| {
 328         let s = v
 329             .iter()
 330             .skip(10000)
 331             .zip(t.iter().skip(10000))
 332             .take_while(|t| *t.0 < 10100)
 333             .map(|(a, b)| *a + *b)
 334             .sum::<u64>();
 335         assert_eq!(s, 2009900);
 336     });
 337 }
 338
 339 #[bench]
 340 fn bench_filter_count(b: &mut Bencher) {
 341     b.iter(|| (0i64..1000000).map(black_box).filter(|x| x % 3 == 0).count())
 342 }
 343
 344 #[bench]
 345 fn bench_filter_ref_count(b: &mut Bencher) {
 346     b.iter(|| (0i64..1000000).map(black_box).by_ref().filter(|x| x % 3 == 0).count())
 347 }
 348
 349 #[bench]
 350 fn bench_filter_chain_count(b: &mut Bencher) {
 351     b.iter(|| (0i64..1000000).chain(0..1000000).map(black_box).filter(|x| x % 3 == 0).count())
 352 }
 353
 354 #[bench]
 355 fn bench_filter_chain_ref_count(b: &mut Bencher) {
 356     b.iter(|| {
 357         (0i64..1000000).chain(0..1000000).map(black_box).by_ref().filter(|x| x % 3 == 0).count()
 358     })
 359 }
 360
 361 #[bench]
 362 fn bench_partial_cmp(b: &mut Bencher) {
 363     b.iter(|| (0..100000).map(black_box).partial_cmp((0..100000).map(black_box)))
 364 }
 365
 366 #[bench]
 367 fn bench_lt(b: &mut Bencher) {
 368     b.iter(|| (0..100000).map(black_box).lt((0..100000).map(black_box)))
 369 }
 370
 371 #[bench]
 372 fn bench_trusted_random_access_adapters(b: &mut Bencher) {
 373     let vec1: Vec<_> = (0usize..100000).collect();
 374     let vec2 = black_box(vec1.clone());
 375     b.iter(|| {
 376         let mut iter = vec1
 377             .iter()
 378             .copied()
 379             .enumerate()
 380             .map(|(idx, e)| idx.wrapping_add(e))
 381             .zip(vec2.iter().copied())
 382             .map(|(a, b)| a.wrapping_add(b))
 383             .fuse();
 384         let mut acc: usize = 0;
 385         let size = iter.size();
 386         for i in 0..size {
 387             // SAFETY: TRA requirements are satisfied by 0..size iteration and then dropping the
 388             // iterator.
 389             acc = acc.wrapping_add(unsafe { iter.__iterator_get_unchecked(i) });
 390         }
 391         acc
 392     })
 393 }