Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 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 | ); |