vendor/zerovec/benches/vzv.rs

   1 // This file is part of ICU4X. For terms of use, please see the file
   2 // called LICENSE at the top level of the ICU4X source tree
   3 // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
   4
   5 use criterion::{black_box, criterion_group, criterion_main, Criterion};
   6 use rand::SeedableRng;
   7 use rand_distr::{Alphanumeric, Distribution, Uniform};
   8 use rand_pcg::Lcg64Xsh32;
   9 use std::ops::RangeInclusive;
  10
  11 use zerovec::VarZeroVec;
  12
  13 #[repr(align(8))]
  14 #[derive(Default)]
  15 struct AlignedBuffer(Vec<u8>);
  16
  17 /// Generates an array of random alphanumeric strings.
  18 ///
  19 /// - length = range of lengths for the strings (chosen uniformly at random)
  20 /// - count = number of strings to generate
  21 /// - seed = seed for the PRNG
  22 ///
  23 /// Returns a tuple including the vector and a u64 that can be used to seed the next PRNG.
  24 fn random_alphanums(lengths: RangeInclusive<usize>, count: usize, seed: u64) -> (Vec<String>, u64) {
  25     // Lcg64Xsh32 is a small, fast PRNG for reproducible benchmarks.
  26     let mut rng1 = Lcg64Xsh32::seed_from_u64(seed);
  27     let mut rng2 = Lcg64Xsh32::seed_from_u64(rand::Rng::gen(&mut rng1));
  28     let alpha_dist = Alphanumeric;
  29     let len_dist = Uniform::from(lengths);
  30     let string_vec = len_dist
  31         .sample_iter(&mut rng1)
  32         .take(count)
  33         .map(|len| {
  34             (&alpha_dist)
  35                 .sample_iter(&mut rng2)
  36                 .take(len)
  37                 .map(char::from)
  38                 .collect::<String>()
  39         })
  40         .collect();
  41     (string_vec, rand::Rng::gen(&mut rng1))
  42 }
  43
  44 fn overview_bench(c: &mut Criterion) {
  45     // Same as vzv/char_count/vzv but with different inputs
  46     let seed = 42;
  47     let (string_vec, _) = random_alphanums(2..=10, 100, seed);
  48     let bytes: Vec<u8> = VarZeroVec::<str>::from(&string_vec).into_bytes();
  49     let vzv = VarZeroVec::<str>::parse_byte_slice(black_box(bytes.as_slice())).unwrap();
  50
  51     c.bench_function("vzv/overview", |b| {
  52         b.iter(|| {
  53             black_box(&vzv)
  54                 .iter()
  55                 .fold(0, |sum, string| sum + string.chars().count())
  56         });
  57     });
  58
  59     #[cfg(feature = "bench")]
  60     {
  61         char_count_benches(c);
  62         binary_search_benches(c);
  63         vzv_precompute_bench(c);
  64     }
  65
  66     #[cfg(all(feature = "bench", feature = "serde"))]
  67     {
  68         serde_benches(c);
  69     }
  70 }
  71
  72 #[cfg(feature = "bench")]
  73 fn char_count_benches(c: &mut Criterion) {
  74     let seed = 2021;
  75     let (string_vec, _) = random_alphanums(2..=20, 100, seed);
  76     let bytes: Vec<u8> = VarZeroVec::<str>::from(&string_vec).into_bytes();
  77     let vzv = VarZeroVec::<str>::parse_byte_slice(black_box(bytes.as_slice())).unwrap();
  78
  79     // *** Count chars in vec of 100 strings ***
  80     c.bench_function("vzv/char_count/slice", |b| {
  81         b.iter(|| {
  82             black_box(&string_vec)
  83                 .iter()
  84                 .fold(0, |sum, string| sum + string.chars().count())
  85         });
  86     });
  87
  88     // *** Count chars in vec of 100 strings ***
  89     c.bench_function("vzv/char_count/vzv", |b| {
  90         b.iter(|| {
  91             black_box(&vzv)
  92                 .iter()
  93                 .fold(0, |sum, string| sum + string.chars().count())
  94         });
  95     });
  96 }
  97
  98 #[cfg(feature = "bench")]
  99 fn binary_search_benches(c: &mut Criterion) {
 100     let seed = 2021;
 101     let (string_vec, seed) = random_alphanums(2..=20, 500, seed);
 102     let (needles, _) = random_alphanums(2..=20, 10, seed);
 103     let bytes: Vec<u8> = VarZeroVec::<str>::from(&string_vec).into_bytes();
 104     let vzv = VarZeroVec::<str>::parse_byte_slice(black_box(bytes.as_slice())).unwrap();
 105     let single_needle = "lmnop".to_owned();
 106
 107     // *** Binary search vec of 500 strings 10 times ***
 108     c.bench_function("vzv/binary_search/slice", |b| {
 109         b.iter(|| {
 110             black_box(&needles)
 111                 .iter()
 112                 .map(|needle| black_box(&string_vec).binary_search(needle))
 113                 .filter(|r| r.is_ok())
 114                 .count()
 115         });
 116     });
 117
 118     // *** Binary search vec of 500 strings 10 times ***
 119     c.bench_function("vzv/binary_search/vzv", |b| {
 120         b.iter(|| {
 121             black_box(&needles)
 122                 .iter()
 123                 .map(|needle| black_box(&vzv).binary_search(needle))
 124                 .filter(|r| r.is_ok())
 125                 .count()
 126         });
 127     });
 128
 129     c.bench_function("vzv/binary_search/single/slice", |b| {
 130         b.iter(|| black_box(&string_vec).binary_search(black_box(&single_needle)));
 131     });
 132
 133     c.bench_function("vzv/binary_search/single/vzv", |b| {
 134         b.iter(|| black_box(&vzv).binary_search(black_box(&single_needle)));
 135     });
 136 }
 137
 138 #[cfg(all(feature = "bench", feature = "serde"))]
 139 fn serde_benches(c: &mut Criterion) {
 140     let seed = 2021;
 141     let (string_vec, _) = random_alphanums(2..=20, 100, seed);
 142     let bincode_vec = bincode::serialize(&string_vec).unwrap();
 143     let vzv: VarZeroVec<str> = VarZeroVec::from(&*string_vec);
 144     let bincode_vzv = bincode::serialize(&vzv).unwrap();
 145
 146     // *** Deserialize vec of 100 strings ***
 147     c.bench_function("vzv/deserialize/string/vec_owned", |b| {
 148         b.iter(|| bincode::deserialize::<Vec<String>>(black_box(&bincode_vec)));
 149     });
 150
 151     // *** Deserialize vec of 100 strings ***
 152     c.bench_function("vzv/deserialize/string/vec_borrowed", |b| {
 153         b.iter(|| bincode::deserialize::<Vec<&str>>(black_box(&bincode_vec)));
 154     });
 155
 156     // *** Deserialize vec of 100 strings ***
 157     c.bench_function("vzv/deserialize/string/vzv", |b| {
 158         b.iter(|| bincode::deserialize::<VarZeroVec<str>>(black_box(&bincode_vzv)));
 159     });
 160 }
 161
 162 #[cfg(feature = "bench")]
 163 // Testing differences between operating on slices with precomputed/non-precomputed indexing info
 164 fn vzv_precompute_bench(c: &mut Criterion) {
 165     let seed = 2021;
 166     let (string_vec, seed) = random_alphanums(2..=20, 500, seed);
 167     let (needles, _) = random_alphanums(2..=20, 10, seed);
 168     let bytes: Vec<u8> = VarZeroVec::<str>::from(&string_vec).into_bytes();
 169     let vzv = VarZeroVec::<str>::parse_byte_slice(black_box(bytes.as_slice())).unwrap();
 170     let borrowed = vzv.as_components();
 171     let slice = vzv.as_slice();
 172     let single_needle = "lmnop";
 173
 174     c.bench_function("vzv_precompute/get/precomputed", |b| {
 175         b.iter(|| black_box(&borrowed).get(100));
 176     });
 177
 178     c.bench_function("vzv_precompute/get/slice", |b| {
 179         b.iter(|| black_box(&slice).get(100));
 180     });
 181
 182     c.bench_function("vzv_precompute/search/precomputed", |b| {
 183         b.iter(|| black_box(&borrowed).binary_search(single_needle));
 184     });
 185
 186     c.bench_function("vzv_precompute/search/slice", |b| {
 187         b.iter(|| black_box(&slice).binary_search(single_needle));
 188     });
 189
 190     c.bench_function("vzv_precompute/search_multi/precomputed", |b| {
 191         b.iter(|| {
 192             black_box(&needles)
 193                 .iter()
 194                 .map(|needle| black_box(&borrowed).binary_search(needle))
 195                 .filter(|r| r.is_ok())
 196                 .count()
 197         });
 198     });
 199
 200     c.bench_function("vzv_precompute/search_multi/slice", |b| {
 201         b.iter(|| {
 202             black_box(&needles)
 203                 .iter()
 204                 .map(|needle| black_box(&slice).binary_search(needle))
 205                 .filter(|r| r.is_ok())
 206                 .count()
 207         });
 208     });
 209 }
 210
 211 criterion_group!(benches, overview_bench,);
 212 criterion_main!(benches);