| 1 |
#![feature(test)] |
| 2 |
extern crate test; |
| 3 |
extern crate strength_reduce; |
| 4 |
extern crate rand; |
| 5 |
|
| 6 |
// rustc incorrectly says these are unused |
| 7 |
#[allow(unused_imports)] |
| 8 |
use rand::{rngs::StdRng, SeedableRng, distributions::Distribution, distributions::Uniform}; |
| 9 |
|
| 10 |
const REPETITIONS: usize = 1000; |
| 11 |
|
| 12 |
macro_rules! bench_unsigned { |
| 13 |
($struct_name:ident, $primitive_type:ident) => ( |
| 14 |
#[inline(never)] |
| 15 |
fn compute_repeated_division_primitive(numerators: &[$primitive_type], divisor: $primitive_type) -> $primitive_type { |
| 16 |
let mut sum = 0; |
| 17 |
for numerator in numerators { |
| 18 |
sum += *numerator / divisor; |
| 19 |
} |
| 20 |
sum |
| 21 |
} |
| 22 |
|
| 23 |
#[inline(never)] |
| 24 |
fn compute_repeated_division(numerators: &[$primitive_type], divisor: strength_reduce::$struct_name) -> $primitive_type { |
| 25 |
let mut sum = 0; |
| 26 |
for numerator in numerators { |
| 27 |
sum += *numerator / divisor; |
| 28 |
} |
| 29 |
sum |
| 30 |
} |
| 31 |
|
| 32 |
#[inline(never)] |
| 33 |
fn compute_single_division(divisors: &[$primitive_type]) -> $primitive_type { |
| 34 |
let mut sum = 0; |
| 35 |
for divisor in divisors { |
| 36 |
let reduced_divisor = strength_reduce::$struct_name::new(*divisor); |
| 37 |
sum += 100 / reduced_divisor; |
| 38 |
} |
| 39 |
sum |
| 40 |
} |
| 41 |
|
| 42 |
#[inline(never)] |
| 43 |
fn compute_repeated_modulo_primitive(numerators: &[$primitive_type], divisor: $primitive_type) -> $primitive_type { |
| 44 |
let mut sum = 0; |
| 45 |
for numerator in numerators { |
| 46 |
sum += *numerator % divisor; |
| 47 |
} |
| 48 |
sum |
| 49 |
} |
| 50 |
|
| 51 |
#[inline(never)] |
| 52 |
fn compute_repeated_modulo(numerators: &[$primitive_type], divisor: strength_reduce::$struct_name) -> $primitive_type { |
| 53 |
let mut sum = 0; |
| 54 |
for numerator in numerators { |
| 55 |
sum += *numerator % divisor; |
| 56 |
} |
| 57 |
sum |
| 58 |
} |
| 59 |
|
| 60 |
#[inline(never)] |
| 61 |
fn compute_repeated_divrem(numerators: &[$primitive_type], divisor: strength_reduce::$struct_name) -> ($primitive_type, $primitive_type) { |
| 62 |
let mut div_sum = 0; |
| 63 |
let mut rem_sum = 0; |
| 64 |
for numerator in numerators { |
| 65 |
let (div_value, rem_value) = strength_reduce::$struct_name::div_rem(*numerator, divisor); |
| 66 |
div_sum += div_value; |
| 67 |
rem_sum += rem_value; |
| 68 |
} |
| 69 |
(div_sum, rem_sum) |
| 70 |
} |
| 71 |
|
| 72 |
fn gen_numerators() -> Vec<$primitive_type> { |
| 73 |
test::black_box((0..std::$primitive_type::MAX).rev().cycle().take(REPETITIONS).collect::<Vec<$primitive_type>>()) |
| 74 |
} |
| 75 |
|
| 76 |
#[bench] |
| 77 |
fn division_standard(b: &mut test::Bencher) { |
| 78 |
let numerators = gen_numerators(); |
| 79 |
let divisor = 6; |
| 80 |
b.iter(|| { test::black_box(compute_repeated_division_primitive(&numerators, divisor)); }); |
| 81 |
} |
| 82 |
|
| 83 |
#[bench] |
| 84 |
fn repeated_division_reduced_power2(b: &mut test::Bencher) { |
| 85 |
let reduced_divisor = strength_reduce::$struct_name::new(8); |
| 86 |
let numerators = gen_numerators(); |
| 87 |
b.iter(|| { test::black_box(compute_repeated_division(&numerators, reduced_divisor)); }); |
| 88 |
} |
| 89 |
|
| 90 |
#[bench] |
| 91 |
fn repeated_division_reduced(b: &mut test::Bencher) { |
| 92 |
let reduced_divisor = strength_reduce::$struct_name::new(6); |
| 93 |
let numerators = gen_numerators(); |
| 94 |
b.iter(|| { test::black_box(compute_repeated_division(&numerators, reduced_divisor)); }); |
| 95 |
} |
| 96 |
|
| 97 |
#[bench] |
| 98 |
fn modulo_standard(b: &mut test::Bencher) { |
| 99 |
let numerators = gen_numerators(); |
| 100 |
let divisor = 6; |
| 101 |
b.iter(|| { test::black_box(compute_repeated_modulo_primitive(&numerators, divisor)); }); |
| 102 |
} |
| 103 |
|
| 104 |
#[bench] |
| 105 |
fn repeated_modulo_reduced_power2(b: &mut test::Bencher) { |
| 106 |
let reduced_divisor = strength_reduce::$struct_name::new(8); |
| 107 |
let numerators = gen_numerators(); |
| 108 |
b.iter(|| { test::black_box(compute_repeated_modulo(&numerators, reduced_divisor)); }); |
| 109 |
} |
| 110 |
|
| 111 |
#[bench] |
| 112 |
fn repeated_modulo_reduced(b: &mut test::Bencher) { |
| 113 |
let reduced_divisor = strength_reduce::$struct_name::new(6); |
| 114 |
let numerators = gen_numerators(); |
| 115 |
b.iter(|| { test::black_box(compute_repeated_modulo(&numerators, reduced_divisor)); }); |
| 116 |
} |
| 117 |
|
| 118 |
#[bench] |
| 119 |
fn repeated_divrem_reduced_power2(b: &mut test::Bencher) { |
| 120 |
let reduced_divisor = strength_reduce::$struct_name::new(8); |
| 121 |
let numerators = gen_numerators(); |
| 122 |
b.iter(|| { test::black_box(compute_repeated_divrem(&numerators, reduced_divisor)); }); |
| 123 |
} |
| 124 |
|
| 125 |
#[bench] |
| 126 |
fn repeated_divrem_reduced(b: &mut test::Bencher) { |
| 127 |
let reduced_divisor = strength_reduce::$struct_name::new(6); |
| 128 |
let numerators = gen_numerators(); |
| 129 |
b.iter(|| { test::black_box(compute_repeated_divrem(&numerators, reduced_divisor)); }); |
| 130 |
} |
| 131 |
|
| 132 |
#[bench] |
| 133 |
fn single_division_reduced_power2(b: &mut test::Bencher) { |
| 134 |
let divisors = test::black_box(vec![8; REPETITIONS]); |
| 135 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 136 |
} |
| 137 |
|
| 138 |
#[bench] |
| 139 |
fn single_division_reduced(b: &mut test::Bencher) { |
| 140 |
let divisors = test::black_box(vec![core::$primitive_type::MAX; REPETITIONS]); |
| 141 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 142 |
} |
| 143 |
) |
| 144 |
} |
| 145 |
|
| 146 |
mod bench_u08 { |
| 147 |
use super::*; |
| 148 |
bench_unsigned!(StrengthReducedU8, u8); |
| 149 |
} |
| 150 |
mod bench_u16 { |
| 151 |
use super::*; |
| 152 |
bench_unsigned!(StrengthReducedU16, u16); |
| 153 |
} |
| 154 |
mod bench_u32 { |
| 155 |
use super::*; |
| 156 |
bench_unsigned!(StrengthReducedU32, u32); |
| 157 |
} |
| 158 |
mod bench_u64 { |
| 159 |
use super::*; |
| 160 |
bench_unsigned!(StrengthReducedU64, u64); |
| 161 |
|
| 162 |
// generates random divisors with values in the range [1<<bit_min, 1<<bit_max) |
| 163 |
fn generate_random_divisors(bit_min: u32, bit_max: u32, count: usize) -> Vec<u64> { |
| 164 |
assert!(bit_min < bit_max); |
| 165 |
assert!(bit_max <= 64); |
| 166 |
|
| 167 |
let min_value = 1u64 << bit_min; |
| 168 |
let max_value = 1u64.checked_shl(bit_max).map_or(core::u64::MAX, |v| v - 1); |
| 169 |
|
| 170 |
let mut gen = StdRng::seed_from_u64(5673573); |
| 171 |
let dist = Uniform::new_inclusive(min_value, max_value); |
| 172 |
|
| 173 |
(0..count).map(|_| dist.sample(&mut gen)).collect() |
| 174 |
} |
| 175 |
|
| 176 |
// since the constructor for StrengthReducedU64 is so dependent on input size, we're going to do a few more targeted "single division" tests at specific sizes, so we can measure each "size class" separately |
| 177 |
#[bench] |
| 178 |
fn targeted_single_division_32bit(b: &mut test::Bencher) { |
| 179 |
let divisors = test::black_box(generate_random_divisors(0, 32, REPETITIONS)); |
| 180 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 181 |
} |
| 182 |
#[bench] |
| 183 |
fn targeted_single_division_64bit(b: &mut test::Bencher) { |
| 184 |
let divisors = test::black_box(generate_random_divisors(32, 64, REPETITIONS)); |
| 185 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 186 |
} |
| 187 |
} |
| 188 |
mod bench_u128 { |
| 189 |
use super::*; |
| 190 |
bench_unsigned!(StrengthReducedU128, u128); |
| 191 |
|
| 192 |
// generates random divisors with values in the range [1<<bit_min, 1<<bit_max) |
| 193 |
fn generate_random_divisors(bit_min: u32, bit_max: u32, count: usize) -> Vec<u128> { |
| 194 |
assert!(bit_min < bit_max); |
| 195 |
assert!(bit_max <= 128); |
| 196 |
|
| 197 |
let min_value = 1u128 << bit_min; |
| 198 |
let max_value = 1u128.checked_shl(bit_max).map_or(core::u128::MAX, |v| v - 1); |
| 199 |
|
| 200 |
let mut gen = StdRng::seed_from_u64(5673573); |
| 201 |
let dist = Uniform::new_inclusive(min_value, max_value); |
| 202 |
|
| 203 |
(0..count).map(|_| dist.sample(&mut gen)).collect() |
| 204 |
} |
| 205 |
|
| 206 |
// since the constructor for StrengthReducedU128 is so dependent on input size, we're going to do a few more targeted "single division" tests at specific sizes, so we can measure each "size class" separately |
| 207 |
#[bench] |
| 208 |
fn targeted_single_division_032bit(b: &mut test::Bencher) { |
| 209 |
let divisors = test::black_box(generate_random_divisors(0, 32, REPETITIONS)); |
| 210 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 211 |
} |
| 212 |
#[bench] |
| 213 |
fn targeted_single_division_064bit(b: &mut test::Bencher) { |
| 214 |
let divisors = test::black_box(generate_random_divisors(32, 64, REPETITIONS)); |
| 215 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 216 |
} |
| 217 |
#[bench] |
| 218 |
fn targeted_single_division_096bit(b: &mut test::Bencher) { |
| 219 |
let divisors = test::black_box(generate_random_divisors(64, 96, REPETITIONS)); |
| 220 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 221 |
} |
| 222 |
#[bench] |
| 223 |
fn targeted_single_division_128bit(b: &mut test::Bencher) { |
| 224 |
let divisors = test::black_box(generate_random_divisors(96, 128, REPETITIONS)); |
| 225 |
b.iter(|| { test::black_box(compute_single_division(&divisors)); }); |
| 226 |
} |
| 227 |
} |