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