library/core/benches/iter.rs

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