diff options
Diffstat (limited to 'vendor/num-integer/benches')
-rw-r--r-- | vendor/num-integer/benches/average.rs | 414 | ||||
-rw-r--r-- | vendor/num-integer/benches/gcd.rs | 176 | ||||
-rw-r--r-- | vendor/num-integer/benches/roots.rs | 170 |
3 files changed, 0 insertions, 760 deletions
diff --git a/vendor/num-integer/benches/average.rs b/vendor/num-integer/benches/average.rs deleted file mode 100644 index 05d824c84..000000000 --- a/vendor/num-integer/benches/average.rs +++ /dev/null @@ -1,414 +0,0 @@ -//! 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); diff --git a/vendor/num-integer/benches/gcd.rs b/vendor/num-integer/benches/gcd.rs deleted file mode 100644 index 082d5ee09..000000000 --- a/vendor/num-integer/benches/gcd.rs +++ /dev/null @@ -1,176 +0,0 @@ -//! Benchmark comparing the current GCD implemtation against an older one. - -#![feature(test)] - -extern crate num_integer; -extern crate num_traits; -extern crate test; - -use num_integer::Integer; -use num_traits::{AsPrimitive, Bounded, Signed}; -use test::{black_box, Bencher}; - -trait GcdOld: Integer { - fn gcd_old(&self, other: &Self) -> Self; -} - -macro_rules! impl_gcd_old_for_isize { - ($T:ty) => { - impl GcdOld for $T { - /// Calculates the Greatest Common Divisor (GCD) of the number and - /// `other`. The result is always positive. - #[inline] - fn gcd_old(&self, other: &Self) -> Self { - // Use Stein's algorithm - let mut m = *self; - let mut n = *other; - if m == 0 || n == 0 { - return (m | n).abs(); - } - - // find common factors of 2 - let shift = (m | n).trailing_zeros(); - - // The algorithm needs positive numbers, but the minimum value - // can't be represented as a positive one. - // It's also a power of two, so the gcd can be - // calculated by bitshifting in that case - - // Assuming two's complement, the number created by the shift - // is positive for all numbers except gcd = abs(min value) - // The call to .abs() causes a panic in debug mode - if m == Self::min_value() || n == Self::min_value() { - return (1 << shift).abs(); - } - - // guaranteed to be positive now, rest like unsigned algorithm - m = m.abs(); - n = n.abs(); - - // divide n and m by 2 until odd - // m inside loop - n >>= n.trailing_zeros(); - - while m != 0 { - m >>= m.trailing_zeros(); - if n > m { - std::mem::swap(&mut n, &mut m) - } - m -= n; - } - - n << shift - } - } - }; -} - -impl_gcd_old_for_isize!(i8); -impl_gcd_old_for_isize!(i16); -impl_gcd_old_for_isize!(i32); -impl_gcd_old_for_isize!(i64); -impl_gcd_old_for_isize!(isize); -impl_gcd_old_for_isize!(i128); - -macro_rules! impl_gcd_old_for_usize { - ($T:ty) => { - impl GcdOld for $T { - /// Calculates the Greatest Common Divisor (GCD) of the number and - /// `other`. The result is always positive. - #[inline] - fn gcd_old(&self, other: &Self) -> Self { - // Use Stein's algorithm - let mut m = *self; - let mut n = *other; - if m == 0 || n == 0 { - return m | n; - } - - // find common factors of 2 - let shift = (m | n).trailing_zeros(); - - // divide n and m by 2 until odd - // m inside loop - n >>= n.trailing_zeros(); - - while m != 0 { - m >>= m.trailing_zeros(); - if n > m { - std::mem::swap(&mut n, &mut m) - } - m -= n; - } - - n << shift - } - } - }; -} - -impl_gcd_old_for_usize!(u8); -impl_gcd_old_for_usize!(u16); -impl_gcd_old_for_usize!(u32); -impl_gcd_old_for_usize!(u64); -impl_gcd_old_for_usize!(usize); -impl_gcd_old_for_usize!(u128); - -/// Return an iterator that yields all Fibonacci numbers fitting into a u128. -fn fibonacci() -> impl Iterator<Item = u128> { - (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| { - let tmp = *a; - *a = *b; - *b += tmp; - Some(*b) - }) -} - -fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T) -where - T: AsPrimitive<u128>, - u128: AsPrimitive<T>, -{ - let max_value: u128 = T::max_value().as_(); - let pairs: Vec<(T, T)> = fibonacci() - .collect::<Vec<_>>() - .windows(2) - .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value) - .map(|pair| (pair[0].as_(), pair[1].as_())) - .collect(); - b.iter(|| { - for &(ref m, ref n) in &pairs { - black_box(gcd(m, n)); - } - }); -} - -macro_rules! bench_gcd { - ($T:ident) => { - mod $T { - use crate::{run_bench, GcdOld}; - use num_integer::Integer; - use test::Bencher; - - #[bench] - fn bench_gcd(b: &mut Bencher) { - run_bench(b, $T::gcd); - } - - #[bench] - fn bench_gcd_old(b: &mut Bencher) { - run_bench(b, $T::gcd_old); - } - } - }; -} - -bench_gcd!(u8); -bench_gcd!(u16); -bench_gcd!(u32); -bench_gcd!(u64); -bench_gcd!(u128); - -bench_gcd!(i8); -bench_gcd!(i16); -bench_gcd!(i32); -bench_gcd!(i64); -bench_gcd!(i128); diff --git a/vendor/num-integer/benches/roots.rs b/vendor/num-integer/benches/roots.rs deleted file mode 100644 index 7f672786a..000000000 --- a/vendor/num-integer/benches/roots.rs +++ /dev/null @@ -1,170 +0,0 @@ -//! Benchmark sqrt and cbrt - -#![feature(test)] - -extern crate num_integer; -extern crate num_traits; -extern crate test; - -use num_integer::Integer; -use num_traits::checked_pow; -use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul}; -use test::{black_box, Bencher}; - -trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} - -impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} - -fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32) -where - T: BenchInteger, - F: Fn(&T) -> T, -{ - // Pre-validate the results... - for i in v { - let rt = f(i); - if *i >= T::zero() { - let rt1 = rt + T::one(); - assert!(rt.pow(n) <= *i); - if let Some(x) = checked_pow(rt1, n as usize) { - assert!(*i < x); - } - } else { - let rt1 = rt - T::one(); - assert!(rt < T::zero()); - assert!(*i <= rt.pow(n)); - if let Some(x) = checked_pow(rt1, n as usize) { - assert!(x < *i); - } - }; - } - - // Now just run as fast as we can! - b.iter(|| { - for i in v { - black_box(f(i)); - } - }); -} - -// 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_()) -} - -fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive<T>, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let mut x: T = 3u32.as_(); - let v: Vec<T> = (0..1000) - .map(|_| { - x = lcg(x); - x - }) - .collect(); - bench(b, &v, f, n); -} - -fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive<T>, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let mut x: T = 3u32.as_(); - let v: Vec<T> = (0..1000) - .map(|_| { - x = lcg(x); - while x < T::zero() { - x = lcg(x); - } - x - }) - .collect(); - bench(b, &v, f, n); -} - -fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive<T>, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let v: Vec<T> = (0..1000).map(|i| i.as_()).collect(); - bench(b, &v, f, n); -} - -fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive<T>, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let v: Vec<T> = (0..1000) - .map(|i| i.as_().mod_floor(&T::max_value())) - .collect(); - bench(b, &v, f, n); -} - -macro_rules! bench_roots { - ($($T:ident),*) => {$( - mod $T { - use test::Bencher; - use num_integer::Roots; - - #[bench] - fn sqrt_rand(b: &mut Bencher) { - ::bench_rand_pos(b, $T::sqrt, 2); - } - - #[bench] - fn sqrt_small(b: &mut Bencher) { - ::bench_small_pos(b, $T::sqrt, 2); - } - - #[bench] - fn cbrt_rand(b: &mut Bencher) { - ::bench_rand(b, $T::cbrt, 3); - } - - #[bench] - fn cbrt_small(b: &mut Bencher) { - ::bench_small(b, $T::cbrt, 3); - } - - #[bench] - fn fourth_root_rand(b: &mut Bencher) { - ::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4); - } - - #[bench] - fn fourth_root_small(b: &mut Bencher) { - ::bench_small_pos(b, |x: &$T| x.nth_root(4), 4); - } - - #[bench] - fn fifth_root_rand(b: &mut Bencher) { - ::bench_rand(b, |x: &$T| x.nth_root(5), 5); - } - - #[bench] - fn fifth_root_small(b: &mut Bencher) { - ::bench_small(b, |x: &$T| x.nth_root(5), 5); - } - } - )*} -} - -bench_roots!(i8, i16, i32, i64, i128); -bench_roots!(u8, u16, u32, u64, u128); |