| 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(); |
| 42 |
f *= bu; |
| 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 multiply_4(b: &mut Bencher) { |
| 92 |
multiply_bench(b, 1 << 12, 1 << 13); |
| 93 |
} |
| 94 |
|
| 95 |
#[bench] |
| 96 |
fn multiply_5(b: &mut Bencher) { |
| 97 |
multiply_bench(b, 1 << 12, 1 << 14); |
| 98 |
} |
| 99 |
|
| 100 |
#[bench] |
| 101 |
fn divide_0(b: &mut Bencher) { |
| 102 |
divide_bench(b, 1 << 8, 1 << 6); |
| 103 |
} |
| 104 |
|
| 105 |
#[bench] |
| 106 |
fn divide_1(b: &mut Bencher) { |
| 107 |
divide_bench(b, 1 << 12, 1 << 8); |
| 108 |
} |
| 109 |
|
| 110 |
#[bench] |
| 111 |
fn divide_2(b: &mut Bencher) { |
| 112 |
divide_bench(b, 1 << 16, 1 << 12); |
| 113 |
} |
| 114 |
|
| 115 |
#[bench] |
| 116 |
fn divide_big_little(b: &mut Bencher) { |
| 117 |
divide_bench(b, 1 << 16, 1 << 4); |
| 118 |
} |
| 119 |
|
| 120 |
#[bench] |
| 121 |
fn remainder_0(b: &mut Bencher) { |
| 122 |
remainder_bench(b, 1 << 8, 1 << 6); |
| 123 |
} |
| 124 |
|
| 125 |
#[bench] |
| 126 |
fn remainder_1(b: &mut Bencher) { |
| 127 |
remainder_bench(b, 1 << 12, 1 << 8); |
| 128 |
} |
| 129 |
|
| 130 |
#[bench] |
| 131 |
fn remainder_2(b: &mut Bencher) { |
| 132 |
remainder_bench(b, 1 << 16, 1 << 12); |
| 133 |
} |
| 134 |
|
| 135 |
#[bench] |
| 136 |
fn remainder_big_little(b: &mut Bencher) { |
| 137 |
remainder_bench(b, 1 << 16, 1 << 4); |
| 138 |
} |
| 139 |
|
| 140 |
#[bench] |
| 141 |
fn factorial_100(b: &mut Bencher) { |
| 142 |
b.iter(|| factorial(100)); |
| 143 |
} |
| 144 |
|
| 145 |
#[bench] |
| 146 |
fn fib_100(b: &mut Bencher) { |
| 147 |
b.iter(|| fib(100)); |
| 148 |
} |
| 149 |
|
| 150 |
#[bench] |
| 151 |
fn fib_1000(b: &mut Bencher) { |
| 152 |
b.iter(|| fib(1000)); |
| 153 |
} |
| 154 |
|
| 155 |
#[bench] |
| 156 |
fn fib_10000(b: &mut Bencher) { |
| 157 |
b.iter(|| fib(10000)); |
| 158 |
} |
| 159 |
|
| 160 |
#[bench] |
| 161 |
fn fib2_100(b: &mut Bencher) { |
| 162 |
b.iter(|| fib2(100)); |
| 163 |
} |
| 164 |
|
| 165 |
#[bench] |
| 166 |
fn fib2_1000(b: &mut Bencher) { |
| 167 |
b.iter(|| fib2(1000)); |
| 168 |
} |
| 169 |
|
| 170 |
#[bench] |
| 171 |
fn fib2_10000(b: &mut Bencher) { |
| 172 |
b.iter(|| fib2(10000)); |
| 173 |
} |
| 174 |
|
| 175 |
#[bench] |
| 176 |
fn fac_to_string(b: &mut Bencher) { |
| 177 |
let fac = factorial(100); |
| 178 |
b.iter(|| fac.to_string()); |
| 179 |
} |
| 180 |
|
| 181 |
#[bench] |
| 182 |
fn fib_to_string(b: &mut Bencher) { |
| 183 |
let fib = fib(100); |
| 184 |
b.iter(|| fib.to_string()); |
| 185 |
} |
| 186 |
|
| 187 |
fn to_str_radix_bench(b: &mut Bencher, radix: u32, bits: u64) { |
| 188 |
let mut rng = get_rng(); |
| 189 |
let x = rng.gen_bigint(bits); |
| 190 |
b.iter(|| x.to_str_radix(radix)); |
| 191 |
} |
| 192 |
|
| 193 |
#[bench] |
| 194 |
fn to_str_radix_02(b: &mut Bencher) { |
| 195 |
to_str_radix_bench(b, 2, 1009); |
| 196 |
} |
| 197 |
|
| 198 |
#[bench] |
| 199 |
fn to_str_radix_08(b: &mut Bencher) { |
| 200 |
to_str_radix_bench(b, 8, 1009); |
| 201 |
} |
| 202 |
|
| 203 |
#[bench] |
| 204 |
fn to_str_radix_10(b: &mut Bencher) { |
| 205 |
to_str_radix_bench(b, 10, 1009); |
| 206 |
} |
| 207 |
|
| 208 |
#[bench] |
| 209 |
fn to_str_radix_10_2(b: &mut Bencher) { |
| 210 |
to_str_radix_bench(b, 10, 10009); |
| 211 |
} |
| 212 |
|
| 213 |
#[bench] |
| 214 |
fn to_str_radix_16(b: &mut Bencher) { |
| 215 |
to_str_radix_bench(b, 16, 1009); |
| 216 |
} |
| 217 |
|
| 218 |
#[bench] |
| 219 |
fn to_str_radix_36(b: &mut Bencher) { |
| 220 |
to_str_radix_bench(b, 36, 1009); |
| 221 |
} |
| 222 |
|
| 223 |
fn from_str_radix_bench(b: &mut Bencher, radix: u32) { |
| 224 |
let mut rng = get_rng(); |
| 225 |
let x = rng.gen_bigint(1009); |
| 226 |
let s = x.to_str_radix(radix); |
| 227 |
assert_eq!(x, BigInt::from_str_radix(&s, radix).unwrap()); |
| 228 |
b.iter(|| BigInt::from_str_radix(&s, radix)); |
| 229 |
} |
| 230 |
|
| 231 |
#[bench] |
| 232 |
fn from_str_radix_02(b: &mut Bencher) { |
| 233 |
from_str_radix_bench(b, 2); |
| 234 |
} |
| 235 |
|
| 236 |
#[bench] |
| 237 |
fn from_str_radix_08(b: &mut Bencher) { |
| 238 |
from_str_radix_bench(b, 8); |
| 239 |
} |
| 240 |
|
| 241 |
#[bench] |
| 242 |
fn from_str_radix_10(b: &mut Bencher) { |
| 243 |
from_str_radix_bench(b, 10); |
| 244 |
} |
| 245 |
|
| 246 |
#[bench] |
| 247 |
fn from_str_radix_16(b: &mut Bencher) { |
| 248 |
from_str_radix_bench(b, 16); |
| 249 |
} |
| 250 |
|
| 251 |
#[bench] |
| 252 |
fn from_str_radix_36(b: &mut Bencher) { |
| 253 |
from_str_radix_bench(b, 36); |
| 254 |
} |
| 255 |
|
| 256 |
fn rand_bench(b: &mut Bencher, bits: u64) { |
| 257 |
let mut rng = get_rng(); |
| 258 |
|
| 259 |
b.iter(|| rng.gen_bigint(bits)); |
| 260 |
} |
| 261 |
|
| 262 |
#[bench] |
| 263 |
fn rand_64(b: &mut Bencher) { |
| 264 |
rand_bench(b, 1 << 6); |
| 265 |
} |
| 266 |
|
| 267 |
#[bench] |
| 268 |
fn rand_256(b: &mut Bencher) { |
| 269 |
rand_bench(b, 1 << 8); |
| 270 |
} |
| 271 |
|
| 272 |
#[bench] |
| 273 |
fn rand_1009(b: &mut Bencher) { |
| 274 |
rand_bench(b, 1009); |
| 275 |
} |
| 276 |
|
| 277 |
#[bench] |
| 278 |
fn rand_2048(b: &mut Bencher) { |
| 279 |
rand_bench(b, 1 << 11); |
| 280 |
} |
| 281 |
|
| 282 |
#[bench] |
| 283 |
fn rand_4096(b: &mut Bencher) { |
| 284 |
rand_bench(b, 1 << 12); |
| 285 |
} |
| 286 |
|
| 287 |
#[bench] |
| 288 |
fn rand_8192(b: &mut Bencher) { |
| 289 |
rand_bench(b, 1 << 13); |
| 290 |
} |
| 291 |
|
| 292 |
#[bench] |
| 293 |
fn rand_65536(b: &mut Bencher) { |
| 294 |
rand_bench(b, 1 << 16); |
| 295 |
} |
| 296 |
|
| 297 |
#[bench] |
| 298 |
fn rand_131072(b: &mut Bencher) { |
| 299 |
rand_bench(b, 1 << 17); |
| 300 |
} |
| 301 |
|
| 302 |
#[bench] |
| 303 |
fn shl(b: &mut Bencher) { |
| 304 |
let n = BigUint::one() << 1000u32; |
| 305 |
let mut m = n.clone(); |
| 306 |
b.iter(|| { |
| 307 |
m.clone_from(&n); |
| 308 |
for i in 0..50 { |
| 309 |
m <<= i; |
| 310 |
} |
| 311 |
}) |
| 312 |
} |
| 313 |
|
| 314 |
#[bench] |
| 315 |
fn shr(b: &mut Bencher) { |
| 316 |
let n = BigUint::one() << 2000u32; |
| 317 |
let mut m = n.clone(); |
| 318 |
b.iter(|| { |
| 319 |
m.clone_from(&n); |
| 320 |
for i in 0..50 { |
| 321 |
m >>= i; |
| 322 |
} |
| 323 |
}) |
| 324 |
} |
| 325 |
|
| 326 |
#[bench] |
| 327 |
fn hash(b: &mut Bencher) { |
| 328 |
use std::collections::HashSet; |
| 329 |
let mut rng = get_rng(); |
| 330 |
let v: Vec<BigInt> = (1000..2000).map(|bits| rng.gen_bigint(bits)).collect(); |
| 331 |
b.iter(|| { |
| 332 |
let h: HashSet<&BigInt> = v.iter().collect(); |
| 333 |
assert_eq!(h.len(), v.len()); |
| 334 |
}); |
| 335 |
} |
| 336 |
|
| 337 |
#[bench] |
| 338 |
fn pow_bench(b: &mut Bencher) { |
| 339 |
b.iter(|| { |
| 340 |
let upper = 100_u32; |
| 341 |
let mut i_big = BigUint::from(1u32); |
| 342 |
for _i in 2..=upper { |
| 343 |
i_big += 1u32; |
| 344 |
for j in 2..=upper { |
| 345 |
i_big.pow(j); |
| 346 |
} |
| 347 |
} |
| 348 |
}); |
| 349 |
} |
| 350 |
|
| 351 |
#[bench] |
| 352 |
fn pow_bench_bigexp(b: &mut Bencher) { |
| 353 |
use num_traits::Pow; |
| 354 |
|
| 355 |
b.iter(|| { |
| 356 |
let upper = 100_u32; |
| 357 |
let mut i_big = BigUint::from(1u32); |
| 358 |
for _i in 2..=upper { |
| 359 |
i_big += 1u32; |
| 360 |
let mut j_big = BigUint::from(1u32); |
| 361 |
for _j in 2..=upper { |
| 362 |
j_big += 1u32; |
| 363 |
Pow::pow(&i_big, &j_big); |
| 364 |
} |
| 365 |
} |
| 366 |
}); |
| 367 |
} |
| 368 |
|
| 369 |
#[bench] |
| 370 |
fn pow_bench_1e1000(b: &mut Bencher) { |
| 371 |
b.iter(|| BigUint::from(10u32).pow(1_000)); |
| 372 |
} |
| 373 |
|
| 374 |
#[bench] |
| 375 |
fn pow_bench_1e10000(b: &mut Bencher) { |
| 376 |
b.iter(|| BigUint::from(10u32).pow(10_000)); |
| 377 |
} |
| 378 |
|
| 379 |
#[bench] |
| 380 |
fn pow_bench_1e100000(b: &mut Bencher) { |
| 381 |
b.iter(|| BigUint::from(10u32).pow(100_000)); |
| 382 |
} |
| 383 |
|
| 384 |
/// This modulus is the prime from the 2048-bit MODP DH group: |
| 385 |
/// https://tools.ietf.org/html/rfc3526#section-3 |
| 386 |
const RFC3526_2048BIT_MODP_GROUP: &str = "\ |
| 387 |
FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\ |
| 388 |
29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\ |
| 389 |
EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\ |
| 390 |
E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\ |
| 391 |
EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\ |
| 392 |
C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\ |
| 393 |
83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\ |
| 394 |
670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\ |
| 395 |
E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\ |
| 396 |
DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\ |
| 397 |
15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF"; |
| 398 |
|
| 399 |
#[bench] |
| 400 |
fn modpow(b: &mut Bencher) { |
| 401 |
let mut rng = get_rng(); |
| 402 |
let base = rng.gen_biguint(2048); |
| 403 |
let e = rng.gen_biguint(2048); |
| 404 |
let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap(); |
| 405 |
|
| 406 |
b.iter(|| base.modpow(&e, &m)); |
| 407 |
} |
| 408 |
|
| 409 |
#[bench] |
| 410 |
fn modpow_even(b: &mut Bencher) { |
| 411 |
let mut rng = get_rng(); |
| 412 |
let base = rng.gen_biguint(2048); |
| 413 |
let e = rng.gen_biguint(2048); |
| 414 |
// Make the modulus even, so monty (base-2^32) doesn't apply. |
| 415 |
let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap() - 1u32; |
| 416 |
|
| 417 |
b.iter(|| base.modpow(&e, &m)); |
| 418 |
} |
| 419 |
|
| 420 |
#[bench] |
| 421 |
fn to_u32_digits(b: &mut Bencher) { |
| 422 |
let mut rng = get_rng(); |
| 423 |
let n = rng.gen_biguint(2048); |
| 424 |
|
| 425 |
b.iter(|| n.to_u32_digits()); |
| 426 |
} |
| 427 |
|
| 428 |
#[bench] |
| 429 |
fn iter_u32_digits(b: &mut Bencher) { |
| 430 |
let mut rng = get_rng(); |
| 431 |
let n = rng.gen_biguint(2048); |
| 432 |
|
| 433 |
b.iter(|| n.iter_u32_digits().max()); |
| 434 |
} |
| 435 |
|
| 436 |
#[bench] |
| 437 |
fn to_u64_digits(b: &mut Bencher) { |
| 438 |
let mut rng = get_rng(); |
| 439 |
let n = rng.gen_biguint(2048); |
| 440 |
|
| 441 |
b.iter(|| n.to_u64_digits()); |
| 442 |
} |
| 443 |
|
| 444 |
#[bench] |
| 445 |
fn iter_u64_digits(b: &mut Bencher) { |
| 446 |
let mut rng = get_rng(); |
| 447 |
let n = rng.gen_biguint(2048); |
| 448 |
|
| 449 |
b.iter(|| n.iter_u64_digits().max()); |
| 450 |
} |