diff options
Diffstat (limited to 'vendor/crypto-bigint/benches/bench.rs')
| -rw-r--r-- | vendor/crypto-bigint/benches/bench.rs | 205 |
1 files changed, 119 insertions, 86 deletions
diff --git a/vendor/crypto-bigint/benches/bench.rs b/vendor/crypto-bigint/benches/bench.rs index e04778053..8be5f5928 100644 --- a/vendor/crypto-bigint/benches/bench.rs +++ b/vendor/crypto-bigint/benches/bench.rs @@ -1,115 +1,148 @@ use criterion::{ - criterion_group, criterion_main, measurement::Measurement, BenchmarkGroup, Criterion, + criterion_group, criterion_main, measurement::Measurement, BatchSize, BenchmarkGroup, Criterion, }; use crypto_bigint::{ modular::runtime_mod::{DynResidue, DynResidueParams}, - NonZero, Random, Reciprocal, Uint, U256, + Limb, NonZero, Random, Reciprocal, U128, U256, }; use rand_core::OsRng; -fn bench_division<'a, M: Measurement>(group: &mut BenchmarkGroup<'a, M>) { - const TEST_SET: usize = 10; - let xs = (0..TEST_SET) - .map(|_| Uint::<4>::random(&mut OsRng)) - .collect::<Vec<_>>(); - let ys = (0..TEST_SET) - .map(|_| NonZero::new(Uint::<2>::ZERO.concat(&Uint::<2>::random(&mut OsRng))).unwrap()) - .collect::<Vec<_>>(); - group.bench_function("div/rem, 4/2, full size", |b| { - b.iter(|| { - xs.iter() - .zip(ys.iter()) - .map(|(x, y)| x.div_rem(y)) - .for_each(drop) - }) +fn bench_division<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) { + group.bench_function("div/rem, U256/U128, full size", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let y_half = U128::random(&mut OsRng); + let y: U256 = (y_half, U128::ZERO).into(); + (x, NonZero::new(y).unwrap()) + }, + |(x, y)| x.div_rem(&y), + BatchSize::SmallInput, + ) }); - group.bench_function("rem, 4/2, full size", |b| { - b.iter(|| { - xs.iter() - .zip(ys.iter()) - .map(|(x, y)| x.rem(y)) - .for_each(drop) - }) + group.bench_function("rem, U256/U128, full size", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let y_half = U128::random(&mut OsRng); + let y: U256 = (y_half, U128::ZERO).into(); + (x, NonZero::new(y).unwrap()) + }, + |(x, y)| x.rem(&y), + BatchSize::SmallInput, + ) }); - let ys = (0..TEST_SET) - .map(|_| Uint::<1>::random(&mut OsRng)) - .collect::<Vec<_>>(); - let ys_full = ys - .iter() - .map(|y| NonZero::new(Uint::<4>::from(y.as_limbs()[0])).unwrap()) - .collect::<Vec<_>>(); - let ys_limb = ys - .iter() - .map(|y| NonZero::new(y.as_limbs()[0]).unwrap()) - .collect::<Vec<_>>(); - group.bench_function("div/rem, 4/1, full size", |b| { - b.iter(|| { - xs.iter() - .zip(ys_full.iter()) - .map(|(x, y)| x.div_rem(y)) - .for_each(drop) - }) + group.bench_function("div/rem, U256/Limb, full size", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let y_small = Limb::random(&mut OsRng); + let y = U256::from_word(y_small.0); + (x, NonZero::new(y).unwrap()) + }, + |(x, y)| x.div_rem(&y), + BatchSize::SmallInput, + ) }); - group.bench_function("div/rem, 4/1, single limb", |b| { - b.iter(|| { - xs.iter() - .zip(ys_limb.iter()) - .map(|(x, y)| x.div_rem_limb(*y)) - .for_each(drop) - }) + + group.bench_function("div/rem, U256/Limb, single limb", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let y = Limb::random(&mut OsRng); + (x, NonZero::new(y).unwrap()) + }, + |(x, y)| x.div_rem_limb(y), + BatchSize::SmallInput, + ) }); - let reciprocals = ys_limb - .iter() - .map(|y| Reciprocal::new(**y)) - .collect::<Vec<_>>(); - group.bench_function("div/rem, 4/1, single limb with reciprocal", |b| { - b.iter(|| { - xs.iter() - .zip(reciprocals.iter()) - .map(|(x, r)| x.div_rem_limb_with_reciprocal(r)) - .for_each(drop) - }) + group.bench_function("div/rem, U256/Limb, single limb with reciprocal", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let y = Limb::random(&mut OsRng); + let r = Reciprocal::new(y); + (x, r) + }, + |(x, r)| x.div_rem_limb_with_reciprocal(&r), + BatchSize::SmallInput, + ) }); } -fn bench_modpow<'a, M: Measurement>(group: &mut BenchmarkGroup<'a, M>) { - const TEST_SET: usize = 10; - let xs = (0..TEST_SET) - .map(|_| U256::random(&mut OsRng)) - .collect::<Vec<_>>(); - let moduli = (0..TEST_SET) - .map(|_| U256::random(&mut OsRng) | U256::ONE) - .collect::<Vec<_>>(); - let powers = (0..TEST_SET) - .map(|_| U256::random(&mut OsRng) | (U256::ONE << (U256::BITS - 1))) - .collect::<Vec<_>>(); +fn bench_montgomery_ops<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) { + let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE)); + group.bench_function("multiplication, U256*U256", |b| { + b.iter_batched( + || { + let x = DynResidue::new(&U256::random(&mut OsRng), params); + let y = DynResidue::new(&U256::random(&mut OsRng), params); + (x, y) + }, + |(x, y)| x * y, + BatchSize::SmallInput, + ) + }); + + let m = U256::random(&mut OsRng) | U256::ONE; + let params = DynResidueParams::new(&m); + group.bench_function("modpow, U256^U256", |b| { + b.iter_batched( + || { + let x = U256::random(&mut OsRng); + let x_m = DynResidue::new(&x, params); + let p = U256::random(&mut OsRng) | (U256::ONE << (U256::BITS - 1)); + (x_m, p) + }, + |(x, p)| x.pow(&p), + BatchSize::SmallInput, + ) + }); +} - let params = moduli.iter().map(DynResidueParams::new).collect::<Vec<_>>(); - let xs_m = xs - .iter() - .zip(params.iter()) - .map(|(x, p)| DynResidue::new(x, *p)) - .collect::<Vec<_>>(); +fn bench_montgomery_conversion<M: Measurement>(group: &mut BenchmarkGroup<'_, M>) { + group.bench_function("DynResidueParams creation", |b| { + b.iter_batched( + || U256::random(&mut OsRng) | U256::ONE, + |modulus| DynResidueParams::new(&modulus), + BatchSize::SmallInput, + ) + }); - group.bench_function("modpow, 4^4", |b| { - b.iter(|| { - xs_m.iter() - .zip(powers.iter()) - .map(|(x, p)| x.pow(p)) - .for_each(drop) - }) + let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE)); + group.bench_function("DynResidue creation", |b| { + b.iter_batched( + || U256::random(&mut OsRng), + |x| DynResidue::new(&x, params), + BatchSize::SmallInput, + ) + }); + + let params = DynResidueParams::new(&(U256::random(&mut OsRng) | U256::ONE)); + group.bench_function("DynResidue retrieve", |b| { + b.iter_batched( + || DynResidue::new(&U256::random(&mut OsRng), params), + |x| x.retrieve(), + BatchSize::SmallInput, + ) }); } fn bench_wrapping_ops(c: &mut Criterion) { let mut group = c.benchmark_group("wrapping ops"); bench_division(&mut group); - bench_modpow(&mut group); group.finish(); } -criterion_group!(benches, bench_wrapping_ops); +fn bench_montgomery(c: &mut Criterion) { + let mut group = c.benchmark_group("Montgomery arithmetic"); + bench_montgomery_conversion(&mut group); + bench_montgomery_ops(&mut group); + group.finish(); +} + +criterion_group!(benches, bench_wrapping_ops, bench_montgomery); criterion_main!(benches); |