diff options
Diffstat (limited to 'third_party/rust/prio/benches')
| -rw-r--r-- | third_party/rust/prio/benches/cycle_counts.rs | 63 | ||||
| -rw-r--r-- | third_party/rust/prio/benches/speed_tests.rs | 127 |
2 files changed, 70 insertions, 120 deletions
diff --git a/third_party/rust/prio/benches/cycle_counts.rs b/third_party/rust/prio/benches/cycle_counts.rs index 43a4ccdad0..5ab704cd44 100644 --- a/third_party/rust/prio/benches/cycle_counts.rs +++ b/third_party/rust/prio/benches/cycle_counts.rs @@ -5,15 +5,12 @@ use iai::black_box; #[cfg(feature = "experimental")] use prio::{ codec::{Decode, Encode, ParameterizedDecode}, - field::{Field255, FieldElement}, + field::{Field255, FieldElement, FieldPrio2}, idpf::{Idpf, IdpfInput, IdpfPublicShare, RingBufferCache}, - vdaf::{poplar1::Poplar1IdpfValue, xof::Seed}, -}; -#[cfg(feature = "prio2")] -use prio::{ - field::FieldPrio2, vdaf::{ + poplar1::Poplar1IdpfValue, prio2::{Prio2, Prio2PrepareShare}, + xof::Seed, Aggregator, Share, }, }; @@ -45,7 +42,7 @@ fn prng_4096() -> Vec<Field128> { prng(4096) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_client(size: usize) -> Vec<Share<FieldPrio2, 32>> { let prio2 = Prio2::new(size).unwrap(); let input = vec![0u32; size]; @@ -53,22 +50,22 @@ fn prio2_client(size: usize) -> Vec<Share<FieldPrio2, 32>> { prio2.shard(&black_box(input), &black_box(nonce)).unwrap().1 } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_client_10() -> Vec<Share<FieldPrio2, 32>> { prio2_client(10) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_client_100() -> Vec<Share<FieldPrio2, 32>> { prio2_client(100) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_client_1000() -> Vec<Share<FieldPrio2, 32>> { prio2_client(1000) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_shard_and_prepare(size: usize) -> Prio2PrepareShare { let prio2 = Prio2::new(size).unwrap(); let input = vec![0u32; size]; @@ -80,24 +77,24 @@ fn prio2_shard_and_prepare(size: usize) -> Prio2PrepareShare { .1 } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_shard_and_prepare_10() -> Prio2PrepareShare { prio2_shard_and_prepare(10) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_shard_and_prepare_100() -> Prio2PrepareShare { prio2_shard_and_prepare(100) } -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2_shard_and_prepare_1000() -> Prio2PrepareShare { prio2_shard_and_prepare(1000) } fn prio3_client_count() -> Vec<Prio3InputShare<Field64, 16>> { let prio3 = Prio3::new_count(2).unwrap(); - let measurement = 1; + let measurement = true; let nonce = [0; 16]; prio3 .shard(&black_box(measurement), &black_box(nonce)) @@ -241,7 +238,7 @@ fn idpf_codec() { .unwrap(); let bits = 4; let public_share = IdpfPublicShare::<Poplar1IdpfValue<Field64>, Poplar1IdpfValue<Field255>>::get_decoded_with_param(&bits, &data).unwrap(); - let encoded = public_share.get_encoded(); + let encoded = public_share.get_encoded().unwrap(); let _ = black_box(encoded.len()); } @@ -261,34 +258,10 @@ macro_rules! main_base { }; } -#[cfg(feature = "prio2")] -macro_rules! main_add_prio2 { - ( $( $func_name:ident ),* $(,)* ) => { - main_base!( - prio2_client_10, - prio2_client_100, - prio2_client_1000, - prio2_shard_and_prepare_10, - prio2_shard_and_prepare_100, - prio2_shard_and_prepare_1000, - $( $func_name, )* - ); - }; -} - -#[cfg(not(feature = "prio2"))] -macro_rules! main_add_prio2 { - ( $( $func_name:ident ),* $(,)* ) => { - main_base!( - $( $func_name, )* - ); - }; -} - #[cfg(feature = "multithreaded")] macro_rules! main_add_multithreaded { ( $( $func_name:ident ),* $(,)* ) => { - main_add_prio2!( + main_base!( prio3_client_count_vec_multithreaded_1000, $( $func_name, )* ); @@ -298,7 +271,7 @@ macro_rules! main_add_multithreaded { #[cfg(not(feature = "multithreaded"))] macro_rules! main_add_multithreaded { ( $( $func_name:ident ),* $(,)* ) => { - main_add_prio2!( + main_base!( $( $func_name, )* ); }; @@ -308,6 +281,12 @@ macro_rules! main_add_multithreaded { macro_rules! main_add_experimental { ( $( $func_name:ident ),* $(,)* ) => { main_add_multithreaded!( + prio2_client_10, + prio2_client_100, + prio2_client_1000, + prio2_shard_and_prepare_10, + prio2_shard_and_prepare_100, + prio2_shard_and_prepare_1000, idpf_codec, idpf_poplar_gen_8, idpf_poplar_gen_128, diff --git a/third_party/rust/prio/benches/speed_tests.rs b/third_party/rust/prio/benches/speed_tests.rs index 66458b1ada..d90085a74d 100644 --- a/third_party/rust/prio/benches/speed_tests.rs +++ b/third_party/rust/prio/benches/speed_tests.rs @@ -15,7 +15,9 @@ use num_rational::Ratio; use num_traits::ToPrimitive; #[cfg(feature = "experimental")] use prio::dp::distributions::DiscreteGaussian; -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] +use prio::idpf::test_utils::generate_zipf_distributed_batch; +#[cfg(feature = "experimental")] use prio::vdaf::prio2::Prio2; use prio::{ benchmarked::*, @@ -35,8 +37,6 @@ use rand::prelude::*; #[cfg(feature = "experimental")] use std::iter; use std::time::Duration; -#[cfg(feature = "experimental")] -use zipf::ZipfDistribution; /// Seed for generation of random benchmark inputs. /// @@ -116,7 +116,7 @@ fn poly_mul(c: &mut Criterion) { } /// Benchmark prio2. -#[cfg(feature = "prio2")] +#[cfg(feature = "experimental")] fn prio2(c: &mut Criterion) { let mut group = c.benchmark_group("prio2_shard"); for input_length in [10, 100, 1_000] { @@ -164,14 +164,14 @@ fn prio3(c: &mut Criterion) { c.bench_function("prio3count_shard", |b| { let vdaf = Prio3::new_count(num_shares).unwrap(); - let measurement = black_box(1); + let measurement = black_box(true); let nonce = black_box([0u8; 16]); b.iter(|| vdaf.shard(&measurement, &nonce).unwrap()); }); c.bench_function("prio3count_prepare_init", |b| { let vdaf = Prio3::new_count(num_shares).unwrap(); - let measurement = black_box(1); + let measurement = black_box(true); let nonce = black_box([0u8; 16]); let verify_key = black_box([0u8; 16]); let (public_share, input_shares) = vdaf.shard(&measurement, &nonce).unwrap(); @@ -712,7 +712,7 @@ fn poplar1(c: &mut Criterion) { for size in test_sizes.iter() { group.throughput(Throughput::Bytes(*size as u64 / 8)); group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| { - let vdaf = Poplar1::new_shake128(size); + let vdaf = Poplar1::new_turboshake128(size); let mut rng = StdRng::seed_from_u64(RNG_SEED); let nonce = rng.gen::<[u8; 16]>(); @@ -736,7 +736,7 @@ fn poplar1(c: &mut Criterion) { for size in test_sizes.iter() { group.measurement_time(Duration::from_secs(30)); // slower benchmark group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| { - let vdaf = Poplar1::new_shake128(size); + let vdaf = Poplar1::new_turboshake128(size); let mut rng = StdRng::seed_from_u64(RNG_SEED); b.iter_batched( @@ -746,7 +746,7 @@ fn poplar1(c: &mut Criterion) { // Parameters are chosen to match Chris Wood's experimental setup: // https://github.com/chris-wood/heavy-hitter-comparison - let (measurements, prefix_tree) = poplar1_generate_zipf_distributed_batch( + let (measurements, prefix_tree) = generate_zipf_distributed_batch( &mut rng, // rng size, // bits 10, // threshold @@ -794,83 +794,54 @@ fn poplar1(c: &mut Criterion) { group.finish(); } -/// Generate a set of Poplar1 measurements with the given bit length `bits`. They are sampled -/// according to the Zipf distribution with parameters `zipf_support` and `zipf_exponent`. Return -/// the measurements, along with the prefix tree for the desired threshold. -/// -/// The prefix tree consists of a sequence of candidate prefixes for each level. For a given level, -/// the candidate prefixes are computed from the hit counts of the prefixes at the previous level: -/// For any prefix `p` whose hit count is at least the desired threshold, add `p || 0` and `p || 1` -/// to the list. +/// Benchmark VIDPF performance. #[cfg(feature = "experimental")] -fn poplar1_generate_zipf_distributed_batch( - rng: &mut impl Rng, - bits: usize, - threshold: usize, - measurement_count: usize, - zipf_support: usize, - zipf_exponent: f64, -) -> (Vec<IdpfInput>, Vec<Vec<IdpfInput>>) { - // Generate random inputs. - let mut inputs = Vec::with_capacity(zipf_support); - for _ in 0..zipf_support { - let bools: Vec<bool> = (0..bits).map(|_| rng.gen()).collect(); - inputs.push(IdpfInput::from_bools(&bools)); - } +fn vidpf(c: &mut Criterion) { + use prio::vidpf::{Vidpf, VidpfInput, VidpfWeight}; - // Sample a number of inputs according to the Zipf distribution. - let mut samples = Vec::with_capacity(measurement_count); - let zipf = ZipfDistribution::new(zipf_support, zipf_exponent).unwrap(); - for _ in 0..measurement_count { - samples.push(inputs[zipf.sample(rng) - 1].clone()); - } + let test_sizes = [8usize, 8 * 16, 8 * 256]; + const NONCE_SIZE: usize = 16; + const NONCE: &[u8; NONCE_SIZE] = b"Test Nonce VIDPF"; - // Compute the prefix tree for the desired threshold. - let mut prefix_tree = Vec::with_capacity(bits); - prefix_tree.push(vec![ - IdpfInput::from_bools(&[false]), - IdpfInput::from_bools(&[true]), - ]); - - for level in 0..bits - 1 { - // Compute the hit count of each prefix from the previous level. - let mut hit_counts = vec![0; prefix_tree[level].len()]; - for (hit_count, prefix) in hit_counts.iter_mut().zip(prefix_tree[level].iter()) { - for sample in samples.iter() { - let mut is_prefix = true; - for j in 0..prefix.len() { - if prefix[j] != sample[j] { - is_prefix = false; - break; - } - } - if is_prefix { - *hit_count += 1; - } - } - } + let mut group = c.benchmark_group("vidpf_gen"); + for size in test_sizes.iter() { + group.throughput(Throughput::Bytes(*size as u64 / 8)); + group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| { + let bits = iter::repeat_with(random).take(size).collect::<Vec<bool>>(); + let input = VidpfInput::from_bools(&bits); + let weight = VidpfWeight::from(vec![Field255::one(), Field255::one()]); - // Compute the next set of candidate prefixes. - let mut next_prefixes = Vec::new(); - for (hit_count, prefix) in hit_counts.iter().zip(prefix_tree[level].iter()) { - if *hit_count >= threshold { - next_prefixes.push(prefix.clone_with_suffix(&[false])); - next_prefixes.push(prefix.clone_with_suffix(&[true])); - } - } - prefix_tree.push(next_prefixes); + let vidpf = Vidpf::<VidpfWeight<Field255>, NONCE_SIZE>::new(2); + + b.iter(|| { + let _ = vidpf.gen(&input, &weight, NONCE).unwrap(); + }); + }); } + group.finish(); - (samples, prefix_tree) + let mut group = c.benchmark_group("vidpf_eval"); + for size in test_sizes.iter() { + group.throughput(Throughput::Bytes(*size as u64 / 8)); + group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| { + let bits = iter::repeat_with(random).take(size).collect::<Vec<bool>>(); + let input = VidpfInput::from_bools(&bits); + let weight = VidpfWeight::from(vec![Field255::one(), Field255::one()]); + let vidpf = Vidpf::<VidpfWeight<Field255>, NONCE_SIZE>::new(2); + + let (public, keys) = vidpf.gen(&input, &weight, NONCE).unwrap(); + + b.iter(|| { + let _ = vidpf.eval(&keys[0], &public, &input, NONCE).unwrap(); + }); + }); + } + group.finish(); } -#[cfg(all(feature = "prio2", feature = "experimental"))] -criterion_group!(benches, poplar1, prio3, prio2, poly_mul, prng, idpf, dp_noise); -#[cfg(all(not(feature = "prio2"), feature = "experimental"))] -criterion_group!(benches, poplar1, prio3, poly_mul, prng, idpf, dp_noise); -#[cfg(all(feature = "prio2", not(feature = "experimental")))] -criterion_group!(benches, prio3, prio2, prng, poly_mul); -#[cfg(all(not(feature = "prio2"), not(feature = "experimental")))] +#[cfg(feature = "experimental")] +criterion_group!(benches, poplar1, prio3, prio2, poly_mul, prng, idpf, dp_noise, vidpf); +#[cfg(not(feature = "experimental"))] criterion_group!(benches, prio3, prng, poly_mul); criterion_main!(benches); |