Debian Codegraph @

.cargo/vendor/itertools/benches/tree_reduce.rs

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