1 #![allow(deprecated)]
2 
3 use criterion::{criterion_group, criterion_main, Criterion};
4 use itertools::{cloned, Itertools};
5 
6 trait IterEx: Iterator {
7     // Another efficient implementation against which to compare,
8     // but needs `std` so is less desirable.
tree_reduce_vec<F>(self, mut f: F) -> Option<Self::Item> where F: FnMut(Self::Item, Self::Item) -> Self::Item, Self: Sized,9     fn tree_reduce_vec<F>(self, mut f: F) -> Option<Self::Item>
10     where
11         F: FnMut(Self::Item, Self::Item) -> Self::Item,
12         Self: Sized,
13     {
14         let hint = self.size_hint().0;
15         let cap = std::mem::size_of::<usize>() * 8 - hint.leading_zeros() as usize;
16         let mut stack = Vec::with_capacity(cap);
17         self.enumerate().for_each(|(mut i, mut x)| {
18             while (i & 1) != 0 {
19                 x = f(stack.pop().unwrap(), x);
20                 i >>= 1;
21             }
22             stack.push(x);
23         });
24         stack.into_iter().fold1(f)
25     }
26 }
27 impl<T: Iterator> IterEx for T {}
28 
29 macro_rules! def_benchs {
30     ($N:expr,
31      $FUN:ident,
32      $BENCH_NAME:ident,
33      ) => {
34         mod $BENCH_NAME {
35             use super::*;
36 
37             pub fn sum(c: &mut Criterion) {
38                 let v: Vec<u32> = (0..$N).collect();
39 
40                 c.bench_function(
41                     &(stringify!($BENCH_NAME).replace('_', " ") + " sum"),
42                     move |b| b.iter(|| cloned(&v).$FUN(|x, y| x + y)),
43                 );
44             }
45 
46             pub fn complex_iter(c: &mut Criterion) {
47                 let u = (3..).take($N / 2);
48                 let v = (5..).take($N / 2);
49                 let it = u.chain(v);
50 
51                 c.bench_function(
52                     &(stringify!($BENCH_NAME).replace('_', " ") + " complex iter"),
53                     move |b| b.iter(|| it.clone().map(|x| x as f32).$FUN(f32::atan2)),
54                 );
55             }
56 
57             pub fn string_format(c: &mut Criterion) {
58                 // This goes quadratic with linear `fold1`, so use a smaller
59                 // size to not waste too much time in travis.  The allocations
60                 // in here are so expensive anyway that it'll still take
61                 // way longer per iteration than the other two benchmarks.
62                 let v: Vec<u32> = (0..($N / 4)).collect();
63 
64                 c.bench_function(
65                     &(stringify!($BENCH_NAME).replace('_', " ") + " string format"),
66                     move |b| {
67                         b.iter(|| {
68                             cloned(&v)
69                                 .map(|x| x.to_string())
70                                 .$FUN(|x, y| format!("{} + {}", x, y))
71                         })
72                     },
73                 );
74             }
75         }
76 
77         criterion_group!(
78             $BENCH_NAME,
79             $BENCH_NAME::sum,
80             $BENCH_NAME::complex_iter,
81             $BENCH_NAME::string_format,
82         );
83     };
84 }
85 
86 def_benchs! {
87     10_000,
88     fold1,
89     fold1_10k,
90 }
91 
92 def_benchs! {
93     10_000,
94     tree_reduce,
95     tree_reduce_stack_10k,
96 }
97 
98 def_benchs! {
99     10_000,
100     tree_reduce_vec,
101     tree_reduce_vec_10k,
102 }
103 
104 def_benchs! {
105     100,
106     fold1,
107     fold1_100,
108 }
109 
110 def_benchs! {
111     100,
112     tree_reduce,
113     tree_reduce_stack_100,
114 }
115 
116 def_benchs! {
117     100,
118     tree_reduce_vec,
119     tree_reduce_vec_100,
120 }
121 
122 def_benchs! {
123     8,
124     fold1,
125     fold1_08,
126 }
127 
128 def_benchs! {
129     8,
130     tree_reduce,
131     tree_reduce_stack_08,
132 }
133 
134 def_benchs! {
135     8,
136     tree_reduce_vec,
137     tree_reduce_vec_08,
138 }
139 
140 criterion_main!(
141     fold1_10k,
142     tree_reduce_stack_10k,
143     tree_reduce_vec_10k,
144     fold1_100,
145     tree_reduce_stack_100,
146     tree_reduce_vec_100,
147     fold1_08,
148     tree_reduce_stack_08,
149     tree_reduce_vec_08,
150 );
151