1 //! Benchmark sqrt and cbrt
2
3 #![feature(test)]
4
5 extern crate num_integer;
6 extern crate num_traits;
7 extern crate test;
8
9 use num_integer::Integer;
10 use num_traits::checked_pow;
11 use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
12 use test::{black_box, Bencher};
13
14 trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
15
16 impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
17
bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32) where T: BenchInteger, F: Fn(&T) -> T,18 fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32)
19 where
20 T: BenchInteger,
21 F: Fn(&T) -> T,
22 {
23 // Pre-validate the results...
24 for i in v {
25 let rt = f(i);
26 if *i >= T::zero() {
27 let rt1 = rt + T::one();
28 assert!(rt.pow(n) <= *i);
29 if let Some(x) = checked_pow(rt1, n as usize) {
30 assert!(*i < x);
31 }
32 } else {
33 let rt1 = rt - T::one();
34 assert!(rt < T::zero());
35 assert!(*i <= rt.pow(n));
36 if let Some(x) = checked_pow(rt1, n as usize) {
37 assert!(x < *i);
38 }
39 };
40 }
41
42 // Now just run as fast as we can!
43 b.iter(|| {
44 for i in v {
45 black_box(f(i));
46 }
47 });
48 }
49
50 // Simple PRNG so we don't have to worry about rand compatibility
lcg<T>(x: T) -> T where u32: AsPrimitive<T>, T: BenchInteger,51 fn lcg<T>(x: T) -> T
52 where
53 u32: AsPrimitive<T>,
54 T: BenchInteger,
55 {
56 // LCG parameters from Numerical Recipes
57 // (but we're applying it to arbitrary sizes)
58 const LCG_A: u32 = 1664525;
59 const LCG_C: u32 = 1013904223;
60 x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
61 }
62
bench_rand<T, F>(b: &mut Bencher, f: F, n: u32) where u32: AsPrimitive<T>, T: BenchInteger, F: Fn(&T) -> T,63 fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32)
64 where
65 u32: AsPrimitive<T>,
66 T: BenchInteger,
67 F: Fn(&T) -> T,
68 {
69 let mut x: T = 3u32.as_();
70 let v: Vec<T> = (0..1000)
71 .map(|_| {
72 x = lcg(x);
73 x
74 })
75 .collect();
76 bench(b, &v, f, n);
77 }
78
bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32) where u32: AsPrimitive<T>, T: BenchInteger, F: Fn(&T) -> T,79 fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32)
80 where
81 u32: AsPrimitive<T>,
82 T: BenchInteger,
83 F: Fn(&T) -> T,
84 {
85 let mut x: T = 3u32.as_();
86 let v: Vec<T> = (0..1000)
87 .map(|_| {
88 x = lcg(x);
89 while x < T::zero() {
90 x = lcg(x);
91 }
92 x
93 })
94 .collect();
95 bench(b, &v, f, n);
96 }
97
bench_small<T, F>(b: &mut Bencher, f: F, n: u32) where u32: AsPrimitive<T>, T: BenchInteger, F: Fn(&T) -> T,98 fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32)
99 where
100 u32: AsPrimitive<T>,
101 T: BenchInteger,
102 F: Fn(&T) -> T,
103 {
104 let v: Vec<T> = (0..1000).map(|i| i.as_()).collect();
105 bench(b, &v, f, n);
106 }
107
bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32) where u32: AsPrimitive<T>, T: BenchInteger, F: Fn(&T) -> T,108 fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32)
109 where
110 u32: AsPrimitive<T>,
111 T: BenchInteger,
112 F: Fn(&T) -> T,
113 {
114 let v: Vec<T> = (0..1000)
115 .map(|i| i.as_().mod_floor(&T::max_value()))
116 .collect();
117 bench(b, &v, f, n);
118 }
119
120 macro_rules! bench_roots {
121 ($($T:ident),*) => {$(
122 mod $T {
123 use test::Bencher;
124 use num_integer::Roots;
125
126 #[bench]
127 fn sqrt_rand(b: &mut Bencher) {
128 ::bench_rand_pos(b, $T::sqrt, 2);
129 }
130
131 #[bench]
132 fn sqrt_small(b: &mut Bencher) {
133 ::bench_small_pos(b, $T::sqrt, 2);
134 }
135
136 #[bench]
137 fn cbrt_rand(b: &mut Bencher) {
138 ::bench_rand(b, $T::cbrt, 3);
139 }
140
141 #[bench]
142 fn cbrt_small(b: &mut Bencher) {
143 ::bench_small(b, $T::cbrt, 3);
144 }
145
146 #[bench]
147 fn fourth_root_rand(b: &mut Bencher) {
148 ::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4);
149 }
150
151 #[bench]
152 fn fourth_root_small(b: &mut Bencher) {
153 ::bench_small_pos(b, |x: &$T| x.nth_root(4), 4);
154 }
155
156 #[bench]
157 fn fifth_root_rand(b: &mut Bencher) {
158 ::bench_rand(b, |x: &$T| x.nth_root(5), 5);
159 }
160
161 #[bench]
162 fn fifth_root_small(b: &mut Bencher) {
163 ::bench_small(b, |x: &$T| x.nth_root(5), 5);
164 }
165 }
166 )*}
167 }
168
169 bench_roots!(i8, i16, i32, i64, i128);
170 bench_roots!(u8, u16, u32, u64, u128);
171