1 use std::collections::BTreeSet;
6 fn random(n: usize) -> BTreeSet<usize> {
7 let mut rng = crate::bench_rng();
8 let mut set = BTreeSet::new();
10 set.insert(rng.gen());
12 assert_eq!(set.len(), n);
16 fn neg(n: usize) -> BTreeSet<i32> {
17 let set: BTreeSet<i32> = (-(n as i32)..=-1).collect();
18 assert_eq!(set.len(), n);
22 fn pos(n: usize) -> BTreeSet<i32> {
23 let set: BTreeSet<i32> = (1..=(n as i32)).collect();
24 assert_eq!(set.len(), n);
28 fn stagger(n1: usize, factor: usize) -> [BTreeSet<u32>; 2] {
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);
35 assert_eq!(sets[0].len(), n1);
36 assert_eq!(sets[1].len(), n2);
40 macro_rules! set_bench {
41 ($name: ident, $set_func: ident, $result_func: ident, $sets: expr) => {
43 pub fn $name(b: &mut Bencher) {
48 b.iter(|| sets[0].$set_func(&sets[1]).$result_func())
53 fn slim_set(n: usize) -> BTreeSet<usize> {
54 (0..n).collect::<BTreeSet<_>>()
58 pub fn clone_100(b: &mut Bencher) {
59 let src = slim_set(100);
60 b.iter(|| src.clone())
64 pub fn clone_100_and_clear(b: &mut Bencher) {
65 let src = slim_set(100);
66 b.iter(|| src.clone().clear())
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())
76 pub fn clone_100_and_drain_half(b: &mut Bencher) {
77 let src = slim_set(100);
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);
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())
92 pub fn clone_100_and_pop_all(b: &mut Bencher) {
93 let src = slim_set(100);
95 let mut set = src.clone();
96 while set.pop_first().is_some() {}
102 pub fn clone_100_and_remove_all(b: &mut Bencher) {
103 let src = slim_set(100);
105 let mut set = src.clone();
106 while let Some(elt) = set.iter().copied().next() {
107 let ok = set.remove(&elt);
115 pub fn clone_100_and_remove_half(b: &mut Bencher) {
116 let src = slim_set(100);
118 let mut set = src.clone();
119 for i in (0..100).step_by(2) {
120 let ok = set.remove(&i);
123 assert_eq!(set.len(), 100 / 2);
129 pub fn clone_10k(b: &mut Bencher) {
130 let src = slim_set(10_000);
131 b.iter(|| src.clone())
135 pub fn clone_10k_and_clear(b: &mut Bencher) {
136 let src = slim_set(10_000);
137 b.iter(|| src.clone().clear())
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())
147 pub fn clone_10k_and_drain_half(b: &mut Bencher) {
148 let src = slim_set(10_000);
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);
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())
163 pub fn clone_10k_and_pop_all(b: &mut Bencher) {
164 let src = slim_set(10_000);
166 let mut set = src.clone();
167 while set.pop_first().is_some() {}
173 pub fn clone_10k_and_remove_all(b: &mut Bencher) {
174 let src = slim_set(10_000);
176 let mut set = src.clone();
177 while let Some(elt) = set.iter().copied().next() {
178 let ok = set.remove(&elt);
186 pub fn clone_10k_and_remove_half(b: &mut Bencher) {
187 let src = slim_set(10_000);
189 let mut set = src.clone();
190 for i in (0..10_000).step_by(2) {
191 let ok = set.remove(&i);
194 assert_eq!(set.len(), 10_000 / 2);
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)]}