1 //! Benchmark sqrt and cbrt
2
3 #![feature(test)]
4
5 extern crate test;
6
7 use num_integer::Integer;
8 use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
9 use std::cmp::{max, min};
10 use std::fmt::Debug;
11 use test::{black_box, Bencher};
12
13 // --- Utilities for RNG ----------------------------------------------------
14
15 trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
16
17 impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
18
19 // Simple PRNG so we don't have to worry about rand compatibility
lcg<T>(x: T) -> T where u32: AsPrimitive<T>, T: BenchInteger,20 fn lcg<T>(x: T) -> T
21 where
22 u32: AsPrimitive<T>,
23 T: BenchInteger,
24 {
25 // LCG parameters from Numerical Recipes
26 // (but we're applying it to arbitrary sizes)
27 const LCG_A: u32 = 1664525;
28 const LCG_C: u32 = 1013904223;
29 x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
30 }
31
32 // --- Alt. Implementations -------------------------------------------------
33
34 trait NaiveAverage {
naive_average_ceil(&self, other: &Self) -> Self35 fn naive_average_ceil(&self, other: &Self) -> Self;
naive_average_floor(&self, other: &Self) -> Self36 fn naive_average_floor(&self, other: &Self) -> Self;
37 }
38
39 trait UncheckedAverage {
unchecked_average_ceil(&self, other: &Self) -> Self40 fn unchecked_average_ceil(&self, other: &Self) -> Self;
unchecked_average_floor(&self, other: &Self) -> Self41 fn unchecked_average_floor(&self, other: &Self) -> Self;
42 }
43
44 trait ModuloAverage {
modulo_average_ceil(&self, other: &Self) -> Self45 fn modulo_average_ceil(&self, other: &Self) -> Self;
modulo_average_floor(&self, other: &Self) -> Self46 fn modulo_average_floor(&self, other: &Self) -> Self;
47 }
48
49 macro_rules! naive_average {
50 ($T:ident) => {
51 impl super::NaiveAverage for $T {
52 fn naive_average_floor(&self, other: &$T) -> $T {
53 match self.checked_add(*other) {
54 Some(z) => Integer::div_floor(&z, &2),
55 None => {
56 if self > other {
57 let diff = self - other;
58 other + Integer::div_floor(&diff, &2)
59 } else {
60 let diff = other - self;
61 self + Integer::div_floor(&diff, &2)
62 }
63 }
64 }
65 }
66 fn naive_average_ceil(&self, other: &$T) -> $T {
67 match self.checked_add(*other) {
68 Some(z) => Integer::div_ceil(&z, &2),
69 None => {
70 if self > other {
71 let diff = self - other;
72 self - Integer::div_floor(&diff, &2)
73 } else {
74 let diff = other - self;
75 other - Integer::div_floor(&diff, &2)
76 }
77 }
78 }
79 }
80 }
81 };
82 }
83
84 macro_rules! unchecked_average {
85 ($T:ident) => {
86 impl super::UncheckedAverage for $T {
87 fn unchecked_average_floor(&self, other: &$T) -> $T {
88 self.wrapping_add(*other) / 2
89 }
90 fn unchecked_average_ceil(&self, other: &$T) -> $T {
91 (self.wrapping_add(*other) / 2).wrapping_add(1)
92 }
93 }
94 };
95 }
96
97 macro_rules! modulo_average {
98 ($T:ident) => {
99 impl super::ModuloAverage for $T {
100 fn modulo_average_ceil(&self, other: &$T) -> $T {
101 let (q1, r1) = self.div_mod_floor(&2);
102 let (q2, r2) = other.div_mod_floor(&2);
103 q1 + q2 + (r1 | r2)
104 }
105 fn modulo_average_floor(&self, other: &$T) -> $T {
106 let (q1, r1) = self.div_mod_floor(&2);
107 let (q2, r2) = other.div_mod_floor(&2);
108 q1 + q2 + (r1 * r2)
109 }
110 }
111 };
112 }
113
114 // --- Bench functions ------------------------------------------------------
115
bench_unchecked<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) where T: Integer + Debug + Copy, F: Fn(&T, &T) -> T,116 fn bench_unchecked<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
117 where
118 T: Integer + Debug + Copy,
119 F: Fn(&T, &T) -> T,
120 {
121 b.iter(|| {
122 for (x, y) in v {
123 black_box(f(x, y));
124 }
125 });
126 }
127
bench_ceil<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) where T: Integer + Debug + Copy, F: Fn(&T, &T) -> T,128 fn bench_ceil<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
129 where
130 T: Integer + Debug + Copy,
131 F: Fn(&T, &T) -> T,
132 {
133 for &(i, j) in v {
134 let rt = f(&i, &j);
135 let (a, b) = (min(i, j), max(i, j));
136 // if both number are the same sign, check rt is in the middle
137 if (a < T::zero()) == (b < T::zero()) {
138 if (b - a).is_even() {
139 assert_eq!(rt - a, b - rt);
140 } else {
141 assert_eq!(rt - a, b - rt + T::one());
142 }
143 // if both number have a different sign,
144 } else if (a + b).is_even() {
145 assert_eq!(rt, (a + b) / (T::one() + T::one()))
146 } else {
147 assert_eq!(rt, (a + b + T::one()) / (T::one() + T::one()))
148 }
149 }
150 bench_unchecked(b, v, f);
151 }
152
bench_floor<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) where T: Integer + Debug + Copy, F: Fn(&T, &T) -> T,153 fn bench_floor<T, F>(b: &mut Bencher, v: &[(T, T)], f: F)
154 where
155 T: Integer + Debug + Copy,
156 F: Fn(&T, &T) -> T,
157 {
158 for &(i, j) in v {
159 let rt = f(&i, &j);
160 let (a, b) = (min(i, j), max(i, j));
161 // if both number are the same sign, check rt is in the middle
162 if (a < T::zero()) == (b < T::zero()) {
163 if (b - a).is_even() {
164 assert_eq!(rt - a, b - rt);
165 } else {
166 assert_eq!(rt - a + T::one(), b - rt);
167 }
168 // if both number have a different sign,
169 } else if (a + b).is_even() {
170 assert_eq!(rt, (a + b) / (T::one() + T::one()))
171 } else {
172 assert_eq!(rt, (a + b - T::one()) / (T::one() + T::one()))
173 }
174 }
175 bench_unchecked(b, v, f);
176 }
177
178 // --- Bench implementation -------------------------------------------------
179
180 macro_rules! bench_average {
181 ($($T:ident),*) => {$(
182 mod $T {
183 use test::Bencher;
184 use num_integer::{Average, Integer};
185 use super::{UncheckedAverage, NaiveAverage, ModuloAverage};
186 use super::{bench_ceil, bench_floor, bench_unchecked};
187
188 naive_average!($T);
189 unchecked_average!($T);
190 modulo_average!($T);
191
192 const SIZE: $T = 30;
193
194 fn overflowing() -> Vec<($T, $T)> {
195 (($T::max_value()-SIZE)..$T::max_value())
196 .flat_map(|x| -> Vec<_> {
197 (($T::max_value()-100)..($T::max_value()-100+SIZE))
198 .map(|y| (x, y))
199 .collect()
200 })
201 .collect()
202 }
203
204 fn small() -> Vec<($T, $T)> {
205 (0..SIZE)
206 .flat_map(|x| -> Vec<_> {(0..SIZE).map(|y| (x, y)).collect()})
207 .collect()
208 }
209
210 fn rand() -> Vec<($T, $T)> {
211 small()
212 .into_iter()
213 .map(|(x, y)| (super::lcg(x), super::lcg(y)))
214 .collect()
215 }
216
217 mod ceil {
218
219 use super::*;
220
221 mod small {
222
223 use super::*;
224
225 #[bench]
226 fn optimized(b: &mut Bencher) {
227 let v = small();
228 bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
229 }
230
231 #[bench]
232 fn naive(b: &mut Bencher) {
233 let v = small();
234 bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
235 }
236
237 #[bench]
238 fn unchecked(b: &mut Bencher) {
239 let v = small();
240 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
241 }
242
243 #[bench]
244 fn modulo(b: &mut Bencher) {
245 let v = small();
246 bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
247 }
248 }
249
250 mod overflowing {
251
252 use super::*;
253
254 #[bench]
255 fn optimized(b: &mut Bencher) {
256 let v = overflowing();
257 bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
258 }
259
260 #[bench]
261 fn naive(b: &mut Bencher) {
262 let v = overflowing();
263 bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
264 }
265
266 #[bench]
267 fn unchecked(b: &mut Bencher) {
268 let v = overflowing();
269 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
270 }
271
272 #[bench]
273 fn modulo(b: &mut Bencher) {
274 let v = overflowing();
275 bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
276 }
277 }
278
279 mod rand {
280
281 use super::*;
282
283 #[bench]
284 fn optimized(b: &mut Bencher) {
285 let v = rand();
286 bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y));
287 }
288
289 #[bench]
290 fn naive(b: &mut Bencher) {
291 let v = rand();
292 bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y));
293 }
294
295 #[bench]
296 fn unchecked(b: &mut Bencher) {
297 let v = rand();
298 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y));
299 }
300
301 #[bench]
302 fn modulo(b: &mut Bencher) {
303 let v = rand();
304 bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y));
305 }
306 }
307
308 }
309
310 mod floor {
311
312 use super::*;
313
314 mod small {
315
316 use super::*;
317
318 #[bench]
319 fn optimized(b: &mut Bencher) {
320 let v = small();
321 bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
322 }
323
324 #[bench]
325 fn naive(b: &mut Bencher) {
326 let v = small();
327 bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
328 }
329
330 #[bench]
331 fn unchecked(b: &mut Bencher) {
332 let v = small();
333 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
334 }
335
336 #[bench]
337 fn modulo(b: &mut Bencher) {
338 let v = small();
339 bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
340 }
341 }
342
343 mod overflowing {
344
345 use super::*;
346
347 #[bench]
348 fn optimized(b: &mut Bencher) {
349 let v = overflowing();
350 bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
351 }
352
353 #[bench]
354 fn naive(b: &mut Bencher) {
355 let v = overflowing();
356 bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
357 }
358
359 #[bench]
360 fn unchecked(b: &mut Bencher) {
361 let v = overflowing();
362 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
363 }
364
365 #[bench]
366 fn modulo(b: &mut Bencher) {
367 let v = overflowing();
368 bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
369 }
370 }
371
372 mod rand {
373
374 use super::*;
375
376 #[bench]
377 fn optimized(b: &mut Bencher) {
378 let v = rand();
379 bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y));
380 }
381
382 #[bench]
383 fn naive(b: &mut Bencher) {
384 let v = rand();
385 bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y));
386 }
387
388 #[bench]
389 fn unchecked(b: &mut Bencher) {
390 let v = rand();
391 bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y));
392 }
393
394 #[bench]
395 fn modulo(b: &mut Bencher) {
396 let v = rand();
397 bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y));
398 }
399 }
400
401 }
402
403 }
404 )*}
405 }
406
407 bench_average!(i8, i16, i32, i64, i128, isize);
408 bench_average!(u8, u16, u32, u64, u128, usize);
409