Debian Codegraph @

.cargo/vendor/strength_reduce/benches/strength_reduce_benchmarks.rs

raw
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 }