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