1use criterion::{criterion_group, criterion_main, Criterion};
2use itertools::{Itertools, cloned};
3
4trait IterEx : Iterator {
5 // Another efficient implementation against which to compare,
6 // but needs `std` so is less desirable.
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}
24impl<T:Iterator> IterEx for T {}
25
26macro_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
80def_benchs!{
81 10_000,
82 fold1,
83 fold1_10k,
84}
85
86def_benchs!{
87 10_000,
88 tree_fold1,
89 tree_fold1_stack_10k,
90}
91
92def_benchs!{
93 10_000,
94 tree_fold1_vec,
95 tree_fold1_vec_10k,
96}
97
98def_benchs!{
99 100,
100 fold1,
101 fold1_100,
102}
103
104def_benchs!{
105 100,
106 tree_fold1,
107 tree_fold1_stack_100,
108}
109
110def_benchs!{
111 100,
112 tree_fold1_vec,
113 tree_fold1_vec_100,
114}
115
116def_benchs!{
117 8,
118 fold1,
119 fold1_08,
120}
121
122def_benchs!{
123 8,
124 tree_fold1,
125 tree_fold1_stack_08,
126}
127
128def_benchs!{
129 8,
130 tree_fold1_vec,
131 tree_fold1_vec_08,
132}
133
134criterion_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