Debian Codegraph @

.cargo/vendor/itertools-0.10.5/benches/tree_fold1.rs

raw
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.
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 );