| //! Benchmark sqrt and cbrt |
| |
| #![feature(test)] |
| |
| extern crate num_integer; |
| extern crate num_traits; |
| extern crate test; |
| |
| use num_integer::Integer; |
| use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul}; |
| use std::cmp::{max, min}; |
| use std::fmt::Debug; |
| use test::{black_box, Bencher}; |
| |
| // --- Utilities for RNG ---------------------------------------------------- |
| |
| trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} |
| |
| impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} |
| |
| // Simple PRNG so we don't have to worry about rand compatibility |
| fn lcg<T>(x: T) -> T |
| where |
| u32: AsPrimitive<T>, |
| T: BenchInteger, |
| { |
| // LCG parameters from Numerical Recipes |
| // (but we're applying it to arbitrary sizes) |
| const LCG_A: u32 = 1664525; |
| const LCG_C: u32 = 1013904223; |
| x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_()) |
| } |
| |
| // --- Alt. Implementations ------------------------------------------------- |
| |
| trait NaiveAverage { |
| fn naive_average_ceil(&self, other: &Self) -> Self; |
| fn naive_average_floor(&self, other: &Self) -> Self; |
| } |
| |
| trait UncheckedAverage { |
| fn unchecked_average_ceil(&self, other: &Self) -> Self; |
| fn unchecked_average_floor(&self, other: &Self) -> Self; |
| } |
| |
| trait ModuloAverage { |
| fn modulo_average_ceil(&self, other: &Self) -> Self; |
| fn modulo_average_floor(&self, other: &Self) -> Self; |
| } |
| |
| macro_rules! naive_average { |
| ($T:ident) => { |
| impl super::NaiveAverage for $T { |
| fn naive_average_floor(&self, other: &$T) -> $T { |
| match self.checked_add(*other) { |
| Some(z) => z.div_floor(&2), |
| None => { |
| if self > other { |
| let diff = self - other; |
| other + diff.div_floor(&2) |
| } else { |
| let diff = other - self; |
| self + diff.div_floor(&2) |
| } |
| } |
| } |
| } |
| fn naive_average_ceil(&self, other: &$T) -> $T { |
| match self.checked_add(*other) { |
| Some(z) => z.div_ceil(&2), |
| None => { |
| if self > other { |
| let diff = self - other; |
| self - diff.div_floor(&2) |
| } else { |
| let diff = other - self; |
| other - diff.div_floor(&2) |
| } |
| } |
| } |
| } |
| } |
| }; |
| } |
| |
| macro_rules! unchecked_average { |
| ($T:ident) => { |
| impl super::UncheckedAverage for $T { |
| fn unchecked_average_floor(&self, other: &$T) -> $T { |
| self.wrapping_add(*other) / 2 |
| } |
| fn unchecked_average_ceil(&self, other: &$T) -> $T { |
| (self.wrapping_add(*other) / 2).wrapping_add(1) |
| } |
| } |
| }; |
| } |
| |
| macro_rules! modulo_average { |
| ($T:ident) => { |
| impl super::ModuloAverage for $T { |
| fn modulo_average_ceil(&self, other: &$T) -> $T { |
| let (q1, r1) = self.div_mod_floor(&2); |
| let (q2, r2) = other.div_mod_floor(&2); |
| q1 + q2 + (r1 | r2) |
| } |
| fn modulo_average_floor(&self, other: &$T) -> $T { |
| let (q1, r1) = self.div_mod_floor(&2); |
| let (q2, r2) = other.div_mod_floor(&2); |
| q1 + q2 + (r1 * r2) |
| } |
| } |
| }; |
| } |
| |
| // --- Bench functions ------------------------------------------------------ |
| |
| fn bench_unchecked<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) |
| where |
| T: Integer + Debug + Copy, |
| F: Fn(&T, &T) -> T, |
| { |
| b.iter(|| { |
| for (x, y) in v { |
| black_box(f(x, y)); |
| } |
| }); |
| } |
| |
| fn bench_ceil<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) |
| where |
| T: Integer + Debug + Copy, |
| F: Fn(&T, &T) -> T, |
| { |
| for &(i, j) in v { |
| let rt = f(&i, &j); |
| let (a, b) = (min(i, j), max(i, j)); |
| // if both number are the same sign, check rt is in the middle |
| if (a < T::zero()) == (b < T::zero()) { |
| if (b - a).is_even() { |
| assert_eq!(rt - a, b - rt); |
| } else { |
| assert_eq!(rt - a, b - rt + T::one()); |
| } |
| // if both number have a different sign, |
| } else { |
| if (a + b).is_even() { |
| assert_eq!(rt, (a + b) / (T::one() + T::one())) |
| } else { |
| assert_eq!(rt, (a + b + T::one()) / (T::one() + T::one())) |
| } |
| } |
| } |
| bench_unchecked(b, v, f); |
| } |
| |
| fn bench_floor<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) |
| where |
| T: Integer + Debug + Copy, |
| F: Fn(&T, &T) -> T, |
| { |
| for &(i, j) in v { |
| let rt = f(&i, &j); |
| let (a, b) = (min(i, j), max(i, j)); |
| // if both number are the same sign, check rt is in the middle |
| if (a < T::zero()) == (b < T::zero()) { |
| if (b - a).is_even() { |
| assert_eq!(rt - a, b - rt); |
| } else { |
| assert_eq!(rt - a + T::one(), b - rt); |
| } |
| // if both number have a different sign, |
| } else { |
| if (a + b).is_even() { |
| assert_eq!(rt, (a + b) / (T::one() + T::one())) |
| } else { |
| assert_eq!(rt, (a + b - T::one()) / (T::one() + T::one())) |
| } |
| } |
| } |
| bench_unchecked(b, v, f); |
| } |
| |
| // --- Bench implementation ------------------------------------------------- |
| |
| macro_rules! bench_average { |
| ($($T:ident),*) => {$( |
| mod $T { |
| use test::Bencher; |
| use num_integer::{Average, Integer}; |
| use super::{UncheckedAverage, NaiveAverage, ModuloAverage}; |
| use super::{bench_ceil, bench_floor, bench_unchecked}; |
| |
| naive_average!($T); |
| unchecked_average!($T); |
| modulo_average!($T); |
| |
| const SIZE: $T = 30; |
| |
| fn overflowing() -> Vec<($T, $T)> { |
| (($T::max_value()-SIZE)..$T::max_value()) |
| .flat_map(|x| -> Vec<_> { |
| (($T::max_value()-100)..($T::max_value()-100+SIZE)) |
| .map(|y| (x, y)) |
| .collect() |
| }) |
| .collect() |
| } |
| |
| fn small() -> Vec<($T, $T)> { |
| (0..SIZE) |
| .flat_map(|x| -> Vec<_> {(0..SIZE).map(|y| (x, y)).collect()}) |
| .collect() |
| } |
| |
| fn rand() -> Vec<($T, $T)> { |
| small() |
| .into_iter() |
| .map(|(x, y)| (super::lcg(x), super::lcg(y))) |
| .collect() |
| } |
| |
| mod ceil { |
| |
| use super::*; |
| |
| mod small { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = small(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = small(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = small(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = small(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); |
| } |
| } |
| |
| mod overflowing { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); |
| } |
| } |
| |
| mod rand { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = rand(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = rand(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = rand(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = rand(); |
| bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); |
| } |
| } |
| |
| } |
| |
| mod floor { |
| |
| use super::*; |
| |
| mod small { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = small(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = small(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = small(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = small(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); |
| } |
| } |
| |
| mod overflowing { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = overflowing(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); |
| } |
| } |
| |
| mod rand { |
| |
| use super::*; |
| |
| #[bench] |
| fn optimized(b: &mut Bencher) { |
| let v = rand(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); |
| } |
| |
| #[bench] |
| fn naive(b: &mut Bencher) { |
| let v = rand(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); |
| } |
| |
| #[bench] |
| fn unchecked(b: &mut Bencher) { |
| let v = rand(); |
| bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); |
| } |
| |
| #[bench] |
| fn modulo(b: &mut Bencher) { |
| let v = rand(); |
| bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); |
| } |
| } |
| |
| } |
| |
| } |
| )*} |
| } |
| |
| bench_average!(i8, i16, i32, i64, i128, isize); |
| bench_average!(u8, u16, u32, u64, u128, usize); |
