library/core/benches/iter.rs

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