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