aboutsummaryrefslogtreecommitdiff
path: root/vendor/num-integer/benches
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/num-integer/benches')
-rw-r--r--vendor/num-integer/benches/average.rs414
-rw-r--r--vendor/num-integer/benches/gcd.rs176
-rw-r--r--vendor/num-integer/benches/roots.rs170
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 649078c..0000000
--- 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) => Integer::div_floor(&z, &2),
- None => {
- if self > other {
- let diff = self - other;
- other + Integer::div_floor(&diff, &2)
- } else {
- let diff = other - self;
- self + Integer::div_floor(&diff, &2)
- }
- }
- }
- }
- fn naive_average_ceil(&self, other: &$T) -> $T {
- match self.checked_add(*other) {
- Some(z) => Integer::div_ceil(&z, &2),
- None => {
- if self > other {
- let diff = self - other;
- self - Integer::div_floor(&diff, &2)
- } else {
- let diff = other - self;
- other - Integer::div_floor(&diff, &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 082d5ee..0000000
--- 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 7f67278..0000000
--- 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);
Copyright © 2024 Valentin A. Popov. All Rights Reverse Engineered.