Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 1 | #![feature(test)] |
| 2 | #![cfg(feature = "rand")] |
| 3 | |
| 4 | extern crate test; |
| 5 | |
| 6 | use num_bigint::{BigInt, BigUint, RandBigInt}; |
| 7 | use num_traits::{FromPrimitive, Num, One, Zero}; |
| 8 | use std::mem::replace; |
| 9 | use test::Bencher; |
| 10 | |
| 11 | mod rng; |
| 12 | use rng::get_rng; |
| 13 | |
| 14 | fn multiply_bench(b: &mut Bencher, xbits: u64, ybits: u64) { |
| 15 | let mut rng = get_rng(); |
| 16 | let x = rng.gen_bigint(xbits); |
| 17 | let y = rng.gen_bigint(ybits); |
| 18 | |
| 19 | b.iter(|| &x * &y); |
| 20 | } |
| 21 | |
| 22 | fn divide_bench(b: &mut Bencher, xbits: u64, ybits: u64) { |
| 23 | let mut rng = get_rng(); |
| 24 | let x = rng.gen_bigint(xbits); |
| 25 | let y = rng.gen_bigint(ybits); |
| 26 | |
| 27 | b.iter(|| &x / &y); |
| 28 | } |
| 29 | |
| 30 | fn remainder_bench(b: &mut Bencher, xbits: u64, ybits: u64) { |
| 31 | let mut rng = get_rng(); |
| 32 | let x = rng.gen_bigint(xbits); |
| 33 | let y = rng.gen_bigint(ybits); |
| 34 | |
| 35 | b.iter(|| &x % &y); |
| 36 | } |
| 37 | |
| 38 | fn factorial(n: usize) -> BigUint { |
| 39 | let mut f: BigUint = One::one(); |
| 40 | for i in 1..=n { |
| 41 | let bu: BigUint = FromPrimitive::from_usize(i).unwrap(); |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 42 | f *= bu; |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 43 | } |
| 44 | f |
| 45 | } |
| 46 | |
| 47 | /// Compute Fibonacci numbers |
| 48 | fn fib(n: usize) -> BigUint { |
| 49 | let mut f0: BigUint = Zero::zero(); |
| 50 | let mut f1: BigUint = One::one(); |
| 51 | for _ in 0..n { |
| 52 | let f2 = f0 + &f1; |
| 53 | f0 = replace(&mut f1, f2); |
| 54 | } |
| 55 | f0 |
| 56 | } |
| 57 | |
| 58 | /// Compute Fibonacci numbers with two ops per iteration |
| 59 | /// (add and subtract, like issue #200) |
| 60 | fn fib2(n: usize) -> BigUint { |
| 61 | let mut f0: BigUint = Zero::zero(); |
| 62 | let mut f1: BigUint = One::one(); |
| 63 | for _ in 0..n { |
| 64 | f1 += &f0; |
| 65 | f0 = &f1 - f0; |
| 66 | } |
| 67 | f0 |
| 68 | } |
| 69 | |
| 70 | #[bench] |
| 71 | fn multiply_0(b: &mut Bencher) { |
| 72 | multiply_bench(b, 1 << 8, 1 << 8); |
| 73 | } |
| 74 | |
| 75 | #[bench] |
| 76 | fn multiply_1(b: &mut Bencher) { |
| 77 | multiply_bench(b, 1 << 8, 1 << 16); |
| 78 | } |
| 79 | |
| 80 | #[bench] |
| 81 | fn multiply_2(b: &mut Bencher) { |
| 82 | multiply_bench(b, 1 << 16, 1 << 16); |
| 83 | } |
| 84 | |
| 85 | #[bench] |
| 86 | fn multiply_3(b: &mut Bencher) { |
| 87 | multiply_bench(b, 1 << 16, 1 << 17); |
| 88 | } |
| 89 | |
| 90 | #[bench] |
| 91 | fn divide_0(b: &mut Bencher) { |
| 92 | divide_bench(b, 1 << 8, 1 << 6); |
| 93 | } |
| 94 | |
| 95 | #[bench] |
| 96 | fn divide_1(b: &mut Bencher) { |
| 97 | divide_bench(b, 1 << 12, 1 << 8); |
| 98 | } |
| 99 | |
| 100 | #[bench] |
| 101 | fn divide_2(b: &mut Bencher) { |
| 102 | divide_bench(b, 1 << 16, 1 << 12); |
| 103 | } |
| 104 | |
| 105 | #[bench] |
| 106 | fn divide_big_little(b: &mut Bencher) { |
| 107 | divide_bench(b, 1 << 16, 1 << 4); |
| 108 | } |
| 109 | |
| 110 | #[bench] |
| 111 | fn remainder_0(b: &mut Bencher) { |
| 112 | remainder_bench(b, 1 << 8, 1 << 6); |
| 113 | } |
| 114 | |
| 115 | #[bench] |
| 116 | fn remainder_1(b: &mut Bencher) { |
| 117 | remainder_bench(b, 1 << 12, 1 << 8); |
| 118 | } |
| 119 | |
| 120 | #[bench] |
| 121 | fn remainder_2(b: &mut Bencher) { |
| 122 | remainder_bench(b, 1 << 16, 1 << 12); |
| 123 | } |
| 124 | |
| 125 | #[bench] |
| 126 | fn remainder_big_little(b: &mut Bencher) { |
| 127 | remainder_bench(b, 1 << 16, 1 << 4); |
| 128 | } |
| 129 | |
| 130 | #[bench] |
| 131 | fn factorial_100(b: &mut Bencher) { |
| 132 | b.iter(|| factorial(100)); |
| 133 | } |
| 134 | |
| 135 | #[bench] |
| 136 | fn fib_100(b: &mut Bencher) { |
| 137 | b.iter(|| fib(100)); |
| 138 | } |
| 139 | |
| 140 | #[bench] |
| 141 | fn fib_1000(b: &mut Bencher) { |
| 142 | b.iter(|| fib(1000)); |
| 143 | } |
| 144 | |
| 145 | #[bench] |
| 146 | fn fib_10000(b: &mut Bencher) { |
| 147 | b.iter(|| fib(10000)); |
| 148 | } |
| 149 | |
| 150 | #[bench] |
| 151 | fn fib2_100(b: &mut Bencher) { |
| 152 | b.iter(|| fib2(100)); |
| 153 | } |
| 154 | |
| 155 | #[bench] |
| 156 | fn fib2_1000(b: &mut Bencher) { |
| 157 | b.iter(|| fib2(1000)); |
| 158 | } |
| 159 | |
| 160 | #[bench] |
| 161 | fn fib2_10000(b: &mut Bencher) { |
| 162 | b.iter(|| fib2(10000)); |
| 163 | } |
| 164 | |
| 165 | #[bench] |
| 166 | fn fac_to_string(b: &mut Bencher) { |
| 167 | let fac = factorial(100); |
| 168 | b.iter(|| fac.to_string()); |
| 169 | } |
| 170 | |
| 171 | #[bench] |
| 172 | fn fib_to_string(b: &mut Bencher) { |
| 173 | let fib = fib(100); |
| 174 | b.iter(|| fib.to_string()); |
| 175 | } |
| 176 | |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 177 | fn to_str_radix_bench(b: &mut Bencher, radix: u32, bits: u64) { |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 178 | let mut rng = get_rng(); |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 179 | let x = rng.gen_bigint(bits); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 180 | b.iter(|| x.to_str_radix(radix)); |
| 181 | } |
| 182 | |
| 183 | #[bench] |
| 184 | fn to_str_radix_02(b: &mut Bencher) { |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 185 | to_str_radix_bench(b, 2, 1009); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 186 | } |
| 187 | |
| 188 | #[bench] |
| 189 | fn to_str_radix_08(b: &mut Bencher) { |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 190 | to_str_radix_bench(b, 8, 1009); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 191 | } |
| 192 | |
| 193 | #[bench] |
| 194 | fn to_str_radix_10(b: &mut Bencher) { |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 195 | to_str_radix_bench(b, 10, 1009); |
| 196 | } |
| 197 | |
| 198 | #[bench] |
| 199 | fn to_str_radix_10_2(b: &mut Bencher) { |
| 200 | to_str_radix_bench(b, 10, 10009); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 201 | } |
| 202 | |
| 203 | #[bench] |
| 204 | fn to_str_radix_16(b: &mut Bencher) { |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 205 | to_str_radix_bench(b, 16, 1009); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 206 | } |
| 207 | |
| 208 | #[bench] |
| 209 | fn to_str_radix_36(b: &mut Bencher) { |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 210 | to_str_radix_bench(b, 36, 1009); |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 211 | } |
| 212 | |
| 213 | fn from_str_radix_bench(b: &mut Bencher, radix: u32) { |
| 214 | let mut rng = get_rng(); |
| 215 | let x = rng.gen_bigint(1009); |
| 216 | let s = x.to_str_radix(radix); |
| 217 | assert_eq!(x, BigInt::from_str_radix(&s, radix).unwrap()); |
| 218 | b.iter(|| BigInt::from_str_radix(&s, radix)); |
| 219 | } |
| 220 | |
| 221 | #[bench] |
| 222 | fn from_str_radix_02(b: &mut Bencher) { |
| 223 | from_str_radix_bench(b, 2); |
| 224 | } |
| 225 | |
| 226 | #[bench] |
| 227 | fn from_str_radix_08(b: &mut Bencher) { |
| 228 | from_str_radix_bench(b, 8); |
| 229 | } |
| 230 | |
| 231 | #[bench] |
| 232 | fn from_str_radix_10(b: &mut Bencher) { |
| 233 | from_str_radix_bench(b, 10); |
| 234 | } |
| 235 | |
| 236 | #[bench] |
| 237 | fn from_str_radix_16(b: &mut Bencher) { |
| 238 | from_str_radix_bench(b, 16); |
| 239 | } |
| 240 | |
| 241 | #[bench] |
| 242 | fn from_str_radix_36(b: &mut Bencher) { |
| 243 | from_str_radix_bench(b, 36); |
| 244 | } |
| 245 | |
| 246 | fn rand_bench(b: &mut Bencher, bits: u64) { |
| 247 | let mut rng = get_rng(); |
| 248 | |
| 249 | b.iter(|| rng.gen_bigint(bits)); |
| 250 | } |
| 251 | |
| 252 | #[bench] |
| 253 | fn rand_64(b: &mut Bencher) { |
| 254 | rand_bench(b, 1 << 6); |
| 255 | } |
| 256 | |
| 257 | #[bench] |
| 258 | fn rand_256(b: &mut Bencher) { |
| 259 | rand_bench(b, 1 << 8); |
| 260 | } |
| 261 | |
| 262 | #[bench] |
| 263 | fn rand_1009(b: &mut Bencher) { |
| 264 | rand_bench(b, 1009); |
| 265 | } |
| 266 | |
| 267 | #[bench] |
| 268 | fn rand_2048(b: &mut Bencher) { |
| 269 | rand_bench(b, 1 << 11); |
| 270 | } |
| 271 | |
| 272 | #[bench] |
| 273 | fn rand_4096(b: &mut Bencher) { |
| 274 | rand_bench(b, 1 << 12); |
| 275 | } |
| 276 | |
| 277 | #[bench] |
| 278 | fn rand_8192(b: &mut Bencher) { |
| 279 | rand_bench(b, 1 << 13); |
| 280 | } |
| 281 | |
| 282 | #[bench] |
| 283 | fn rand_65536(b: &mut Bencher) { |
| 284 | rand_bench(b, 1 << 16); |
| 285 | } |
| 286 | |
| 287 | #[bench] |
| 288 | fn rand_131072(b: &mut Bencher) { |
| 289 | rand_bench(b, 1 << 17); |
| 290 | } |
| 291 | |
| 292 | #[bench] |
| 293 | fn shl(b: &mut Bencher) { |
| 294 | let n = BigUint::one() << 1000u32; |
| 295 | let mut m = n.clone(); |
| 296 | b.iter(|| { |
| 297 | m.clone_from(&n); |
| 298 | for i in 0..50 { |
| 299 | m <<= i; |
| 300 | } |
| 301 | }) |
| 302 | } |
| 303 | |
| 304 | #[bench] |
| 305 | fn shr(b: &mut Bencher) { |
| 306 | let n = BigUint::one() << 2000u32; |
| 307 | let mut m = n.clone(); |
| 308 | b.iter(|| { |
| 309 | m.clone_from(&n); |
| 310 | for i in 0..50 { |
| 311 | m >>= i; |
| 312 | } |
| 313 | }) |
| 314 | } |
| 315 | |
| 316 | #[bench] |
| 317 | fn hash(b: &mut Bencher) { |
| 318 | use std::collections::HashSet; |
| 319 | let mut rng = get_rng(); |
| 320 | let v: Vec<BigInt> = (1000..2000).map(|bits| rng.gen_bigint(bits)).collect(); |
| 321 | b.iter(|| { |
| 322 | let h: HashSet<&BigInt> = v.iter().collect(); |
| 323 | assert_eq!(h.len(), v.len()); |
| 324 | }); |
| 325 | } |
| 326 | |
| 327 | #[bench] |
| 328 | fn pow_bench(b: &mut Bencher) { |
| 329 | b.iter(|| { |
| 330 | let upper = 100_u32; |
| 331 | let mut i_big = BigUint::from(1u32); |
| 332 | for _i in 2..=upper { |
| 333 | i_big += 1u32; |
| 334 | for j in 2..=upper { |
| 335 | i_big.pow(j); |
| 336 | } |
| 337 | } |
| 338 | }); |
| 339 | } |
| 340 | |
| 341 | #[bench] |
| 342 | fn pow_bench_bigexp(b: &mut Bencher) { |
| 343 | use num_traits::Pow; |
| 344 | |
| 345 | b.iter(|| { |
| 346 | let upper = 100_u32; |
| 347 | let mut i_big = BigUint::from(1u32); |
| 348 | for _i in 2..=upper { |
| 349 | i_big += 1u32; |
| 350 | let mut j_big = BigUint::from(1u32); |
| 351 | for _j in 2..=upper { |
| 352 | j_big += 1u32; |
| 353 | Pow::pow(&i_big, &j_big); |
| 354 | } |
| 355 | } |
| 356 | }); |
| 357 | } |
| 358 | |
Joel Galenson | 7bace41 | 2021-09-22 14:05:35 -0700 | [diff] [blame] | 359 | #[bench] |
| 360 | fn pow_bench_1e1000(b: &mut Bencher) { |
| 361 | b.iter(|| BigUint::from(10u32).pow(1_000)); |
| 362 | } |
| 363 | |
| 364 | #[bench] |
| 365 | fn pow_bench_1e10000(b: &mut Bencher) { |
| 366 | b.iter(|| BigUint::from(10u32).pow(10_000)); |
| 367 | } |
| 368 | |
| 369 | #[bench] |
| 370 | fn pow_bench_1e100000(b: &mut Bencher) { |
| 371 | b.iter(|| BigUint::from(10u32).pow(100_000)); |
| 372 | } |
| 373 | |
Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 374 | /// This modulus is the prime from the 2048-bit MODP DH group: |
| 375 | /// https://tools.ietf.org/html/rfc3526#section-3 |
| 376 | const RFC3526_2048BIT_MODP_GROUP: &str = "\ |
| 377 | FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\ |
| 378 | 29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\ |
| 379 | EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\ |
| 380 | E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\ |
| 381 | EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\ |
| 382 | C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\ |
| 383 | 83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\ |
| 384 | 670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\ |
| 385 | E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\ |
| 386 | DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\ |
| 387 | 15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF"; |
| 388 | |
| 389 | #[bench] |
| 390 | fn modpow(b: &mut Bencher) { |
| 391 | let mut rng = get_rng(); |
| 392 | let base = rng.gen_biguint(2048); |
| 393 | let e = rng.gen_biguint(2048); |
| 394 | let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap(); |
| 395 | |
| 396 | b.iter(|| base.modpow(&e, &m)); |
| 397 | } |
| 398 | |
| 399 | #[bench] |
| 400 | fn modpow_even(b: &mut Bencher) { |
| 401 | let mut rng = get_rng(); |
| 402 | let base = rng.gen_biguint(2048); |
| 403 | let e = rng.gen_biguint(2048); |
| 404 | // Make the modulus even, so monty (base-2^32) doesn't apply. |
| 405 | let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap() - 1u32; |
| 406 | |
| 407 | b.iter(|| base.modpow(&e, &m)); |
| 408 | } |
| 409 | |
| 410 | #[bench] |
| 411 | fn to_u32_digits(b: &mut Bencher) { |
| 412 | let mut rng = get_rng(); |
| 413 | let n = rng.gen_biguint(2048); |
| 414 | |
| 415 | b.iter(|| n.to_u32_digits()); |
| 416 | } |
| 417 | |
| 418 | #[bench] |
| 419 | fn iter_u32_digits(b: &mut Bencher) { |
| 420 | let mut rng = get_rng(); |
| 421 | let n = rng.gen_biguint(2048); |
| 422 | |
| 423 | b.iter(|| n.iter_u32_digits().max()); |
| 424 | } |
| 425 | |
| 426 | #[bench] |
| 427 | fn to_u64_digits(b: &mut Bencher) { |
| 428 | let mut rng = get_rng(); |
| 429 | let n = rng.gen_biguint(2048); |
| 430 | |
| 431 | b.iter(|| n.to_u64_digits()); |
| 432 | } |
| 433 | |
| 434 | #[bench] |
| 435 | fn iter_u64_digits(b: &mut Bencher) { |
| 436 | let mut rng = get_rng(); |
| 437 | let n = rng.gen_biguint(2048); |
| 438 | |
| 439 | b.iter(|| n.iter_u64_digits().max()); |
| 440 | } |