library/alloc/benches/btree/set.rs

   1 use std::collections::BTreeSet;
   2
   3 use rand::Rng;
   4 use test::Bencher;
   5
   6 fn random(n: usize) -> BTreeSet<usize> {
   7     let mut rng = crate::bench_rng();
   8     let mut set = BTreeSet::new();
   9     while set.len() < n {
  10         set.insert(rng.gen());
  11     }
  12     assert_eq!(set.len(), n);
  13     set
  14 }
  15
  16 fn neg(n: usize) -> BTreeSet<i32> {
  17     let set: BTreeSet<i32> = (-(n as i32)..=-1).collect();
  18     assert_eq!(set.len(), n);
  19     set
  20 }
  21
  22 fn pos(n: usize) -> BTreeSet<i32> {
  23     let set: BTreeSet<i32> = (1..=(n as i32)).collect();
  24     assert_eq!(set.len(), n);
  25     set
  26 }
  27
  28 fn stagger(n1: usize, factor: usize) -> [BTreeSet<u32>; 2] {
  29     let n2 = n1 * factor;
  30     let mut sets = [BTreeSet::new(), BTreeSet::new()];
  31     for i in 0..(n1 + n2) {
  32         let b = i % (factor + 1) != 0;
  33         sets[b as usize].insert(i as u32);
  34     }
  35     assert_eq!(sets[0].len(), n1);
  36     assert_eq!(sets[1].len(), n2);
  37     sets
  38 }
  39
  40 macro_rules! set_bench {
  41     ($name: ident, $set_func: ident, $result_func: ident, $sets: expr) => {
  42         #[bench]
  43         pub fn $name(b: &mut Bencher) {
  44             // setup
  45             let sets = $sets;
  46
  47             // measure
  48             b.iter(|| sets[0].$set_func(&sets[1]).$result_func())
  49         }
  50     };
  51 }
  52
  53 fn slim_set(n: usize) -> BTreeSet<usize> {
  54     (0..n).collect::<BTreeSet<_>>()
  55 }
  56
  57 #[bench]
  58 pub fn clone_100(b: &mut Bencher) {
  59     let src = slim_set(100);
  60     b.iter(|| src.clone())
  61 }
  62
  63 #[bench]
  64 pub fn clone_100_and_clear(b: &mut Bencher) {
  65     let src = slim_set(100);
  66     b.iter(|| src.clone().clear())
  67 }
  68
  69 #[bench]
  70 pub fn clone_100_and_drain_all(b: &mut Bencher) {
  71     let src = slim_set(100);
  72     b.iter(|| src.clone().drain_filter(|_| true).count())
  73 }
  74
  75 #[bench]
  76 pub fn clone_100_and_drain_half(b: &mut Bencher) {
  77     let src = slim_set(100);
  78     b.iter(|| {
  79         let mut set = src.clone();
  80         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 100 / 2);
  81         assert_eq!(set.len(), 100 / 2);
  82     })
  83 }
  84
  85 #[bench]
  86 pub fn clone_100_and_into_iter(b: &mut Bencher) {
  87     let src = slim_set(100);
  88     b.iter(|| src.clone().into_iter().count())
  89 }
  90
  91 #[bench]
  92 pub fn clone_100_and_pop_all(b: &mut Bencher) {
  93     let src = slim_set(100);
  94     b.iter(|| {
  95         let mut set = src.clone();
  96         while set.pop_first().is_some() {}
  97         set
  98     });
  99 }
 100
 101 #[bench]
 102 pub fn clone_100_and_remove_all(b: &mut Bencher) {
 103     let src = slim_set(100);
 104     b.iter(|| {
 105         let mut set = src.clone();
 106         while let Some(elt) = set.iter().copied().next() {
 107             let ok = set.remove(&elt);
 108             debug_assert!(ok);
 109         }
 110         set
 111     });
 112 }
 113
 114 #[bench]
 115 pub fn clone_100_and_remove_half(b: &mut Bencher) {
 116     let src = slim_set(100);
 117     b.iter(|| {
 118         let mut set = src.clone();
 119         for i in (0..100).step_by(2) {
 120             let ok = set.remove(&i);
 121             debug_assert!(ok);
 122         }
 123         assert_eq!(set.len(), 100 / 2);
 124         set
 125     })
 126 }
 127
 128 #[bench]
 129 pub fn clone_10k(b: &mut Bencher) {
 130     let src = slim_set(10_000);
 131     b.iter(|| src.clone())
 132 }
 133
 134 #[bench]
 135 pub fn clone_10k_and_clear(b: &mut Bencher) {
 136     let src = slim_set(10_000);
 137     b.iter(|| src.clone().clear())
 138 }
 139
 140 #[bench]
 141 pub fn clone_10k_and_drain_all(b: &mut Bencher) {
 142     let src = slim_set(10_000);
 143     b.iter(|| src.clone().drain_filter(|_| true).count())
 144 }
 145
 146 #[bench]
 147 pub fn clone_10k_and_drain_half(b: &mut Bencher) {
 148     let src = slim_set(10_000);
 149     b.iter(|| {
 150         let mut set = src.clone();
 151         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 10_000 / 2);
 152         assert_eq!(set.len(), 10_000 / 2);
 153     })
 154 }
 155
 156 #[bench]
 157 pub fn clone_10k_and_into_iter(b: &mut Bencher) {
 158     let src = slim_set(10_000);
 159     b.iter(|| src.clone().into_iter().count())
 160 }
 161
 162 #[bench]
 163 pub fn clone_10k_and_pop_all(b: &mut Bencher) {
 164     let src = slim_set(10_000);
 165     b.iter(|| {
 166         let mut set = src.clone();
 167         while set.pop_first().is_some() {}
 168         set
 169     });
 170 }
 171
 172 #[bench]
 173 pub fn clone_10k_and_remove_all(b: &mut Bencher) {
 174     let src = slim_set(10_000);
 175     b.iter(|| {
 176         let mut set = src.clone();
 177         while let Some(elt) = set.iter().copied().next() {
 178             let ok = set.remove(&elt);
 179             debug_assert!(ok);
 180         }
 181         set
 182     });
 183 }
 184
 185 #[bench]
 186 pub fn clone_10k_and_remove_half(b: &mut Bencher) {
 187     let src = slim_set(10_000);
 188     b.iter(|| {
 189         let mut set = src.clone();
 190         for i in (0..10_000).step_by(2) {
 191             let ok = set.remove(&i);
 192             debug_assert!(ok);
 193         }
 194         assert_eq!(set.len(), 10_000 / 2);
 195         set
 196     })
 197 }
 198
 199 set_bench! {intersection_100_neg_vs_100_pos, intersection, count, [neg(100), pos(100)]}
 200 set_bench! {intersection_100_neg_vs_10k_pos, intersection, count, [neg(100), pos(10_000)]}
 201 set_bench! {intersection_100_pos_vs_100_neg, intersection, count, [pos(100), neg(100)]}
 202 set_bench! {intersection_100_pos_vs_10k_neg, intersection, count, [pos(100), neg(10_000)]}
 203 set_bench! {intersection_10k_neg_vs_100_pos, intersection, count, [neg(10_000), pos(100)]}
 204 set_bench! {intersection_10k_neg_vs_10k_pos, intersection, count, [neg(10_000), pos(10_000)]}
 205 set_bench! {intersection_10k_pos_vs_100_neg, intersection, count, [pos(10_000), neg(100)]}
 206 set_bench! {intersection_10k_pos_vs_10k_neg, intersection, count, [pos(10_000), neg(10_000)]}
 207 set_bench! {intersection_random_100_vs_100, intersection, count, [random(100), random(100)]}
 208 set_bench! {intersection_random_100_vs_10k, intersection, count, [random(100), random(10_000)]}
 209 set_bench! {intersection_random_10k_vs_100, intersection, count, [random(10_000), random(100)]}
 210 set_bench! {intersection_random_10k_vs_10k, intersection, count, [random(10_000), random(10_000)]}
 211 set_bench! {intersection_staggered_100_vs_100, intersection, count, stagger(100, 1)}
 212 set_bench! {intersection_staggered_10k_vs_10k, intersection, count, stagger(10_000, 1)}
 213 set_bench! {intersection_staggered_100_vs_10k, intersection, count, stagger(100, 100)}
 214 set_bench! {difference_random_100_vs_100, difference, count, [random(100), random(100)]}
 215 set_bench! {difference_random_100_vs_10k, difference, count, [random(100), random(10_000)]}
 216 set_bench! {difference_random_10k_vs_100, difference, count, [random(10_000), random(100)]}
 217 set_bench! {difference_random_10k_vs_10k, difference, count, [random(10_000), random(10_000)]}
 218 set_bench! {difference_staggered_100_vs_100, difference, count, stagger(100, 1)}
 219 set_bench! {difference_staggered_10k_vs_10k, difference, count, stagger(10_000, 1)}
 220 set_bench! {difference_staggered_100_vs_10k, difference, count, stagger(100, 100)}
 221 set_bench! {is_subset_100_vs_100, is_subset, clone, [pos(100), pos(100)]}
 222 set_bench! {is_subset_100_vs_10k, is_subset, clone, [pos(100), pos(10_000)]}
 223 set_bench! {is_subset_10k_vs_100, is_subset, clone, [pos(10_000), pos(100)]}
 224 set_bench! {is_subset_10k_vs_10k, is_subset, clone, [pos(10_000), pos(10_000)]}