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