From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/benches/btree/set.rs | 224 +++++++++++++++++++++++++++++++++++++ 1 file changed, 224 insertions(+) create mode 100644 library/alloc/benches/btree/set.rs (limited to 'library/alloc/benches/btree/set.rs') diff --git a/library/alloc/benches/btree/set.rs b/library/alloc/benches/btree/set.rs new file mode 100644 index 000000000..3f4b0e0f1 --- /dev/null +++ b/library/alloc/benches/btree/set.rs @@ -0,0 +1,224 @@ +use std::collections::BTreeSet; + +use rand::Rng; +use test::Bencher; + +fn random(n: usize) -> BTreeSet { + let mut rng = crate::bench_rng(); + let mut set = BTreeSet::new(); + while set.len() < n { + set.insert(rng.gen()); + } + assert_eq!(set.len(), n); + set +} + +fn neg(n: usize) -> BTreeSet { + let set: BTreeSet = (-(n as i32)..=-1).collect(); + assert_eq!(set.len(), n); + set +} + +fn pos(n: usize) -> BTreeSet { + let set: BTreeSet = (1..=(n as i32)).collect(); + assert_eq!(set.len(), n); + set +} + +fn stagger(n1: usize, factor: usize) -> [BTreeSet; 2] { + let n2 = n1 * factor; + let mut sets = [BTreeSet::new(), BTreeSet::new()]; + for i in 0..(n1 + n2) { + let b = i % (factor + 1) != 0; + sets[b as usize].insert(i as u32); + } + assert_eq!(sets[0].len(), n1); + assert_eq!(sets[1].len(), n2); + sets +} + +macro_rules! set_bench { + ($name: ident, $set_func: ident, $result_func: ident, $sets: expr) => { + #[bench] + pub fn $name(b: &mut Bencher) { + // setup + let sets = $sets; + + // measure + b.iter(|| sets[0].$set_func(&sets[1]).$result_func()) + } + }; +} + +fn slim_set(n: usize) -> BTreeSet { + (0..n).collect::>() +} + +#[bench] +pub fn clone_100(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| src.clone()) +} + +#[bench] +pub fn clone_100_and_clear(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| src.clone().clear()) +} + +#[bench] +pub fn clone_100_and_drain_all(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| src.clone().drain_filter(|_| true).count()) +} + +#[bench] +pub fn clone_100_and_drain_half(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| { + let mut set = src.clone(); + assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 100 / 2); + assert_eq!(set.len(), 100 / 2); + }) +} + +#[bench] +pub fn clone_100_and_into_iter(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| src.clone().into_iter().count()) +} + +#[bench] +pub fn clone_100_and_pop_all(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| { + let mut set = src.clone(); + while set.pop_first().is_some() {} + set + }); +} + +#[bench] +pub fn clone_100_and_remove_all(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| { + let mut set = src.clone(); + while let Some(elt) = set.iter().copied().next() { + let ok = set.remove(&elt); + debug_assert!(ok); + } + set + }); +} + +#[bench] +pub fn clone_100_and_remove_half(b: &mut Bencher) { + let src = slim_set(100); + b.iter(|| { + let mut set = src.clone(); + for i in (0..100).step_by(2) { + let ok = set.remove(&i); + debug_assert!(ok); + } + assert_eq!(set.len(), 100 / 2); + set + }) +} + +#[bench] +pub fn clone_10k(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| src.clone()) +} + +#[bench] +pub fn clone_10k_and_clear(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| src.clone().clear()) +} + +#[bench] +pub fn clone_10k_and_drain_all(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| src.clone().drain_filter(|_| true).count()) +} + +#[bench] +pub fn clone_10k_and_drain_half(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| { + let mut set = src.clone(); + assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 10_000 / 2); + assert_eq!(set.len(), 10_000 / 2); + }) +} + +#[bench] +pub fn clone_10k_and_into_iter(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| src.clone().into_iter().count()) +} + +#[bench] +pub fn clone_10k_and_pop_all(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| { + let mut set = src.clone(); + while set.pop_first().is_some() {} + set + }); +} + +#[bench] +pub fn clone_10k_and_remove_all(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| { + let mut set = src.clone(); + while let Some(elt) = set.iter().copied().next() { + let ok = set.remove(&elt); + debug_assert!(ok); + } + set + }); +} + +#[bench] +pub fn clone_10k_and_remove_half(b: &mut Bencher) { + let src = slim_set(10_000); + b.iter(|| { + let mut set = src.clone(); + for i in (0..10_000).step_by(2) { + let ok = set.remove(&i); + debug_assert!(ok); + } + assert_eq!(set.len(), 10_000 / 2); + set + }) +} + +set_bench! {intersection_100_neg_vs_100_pos, intersection, count, [neg(100), pos(100)]} +set_bench! {intersection_100_neg_vs_10k_pos, intersection, count, [neg(100), pos(10_000)]} +set_bench! {intersection_100_pos_vs_100_neg, intersection, count, [pos(100), neg(100)]} +set_bench! {intersection_100_pos_vs_10k_neg, intersection, count, [pos(100), neg(10_000)]} +set_bench! {intersection_10k_neg_vs_100_pos, intersection, count, [neg(10_000), pos(100)]} +set_bench! {intersection_10k_neg_vs_10k_pos, intersection, count, [neg(10_000), pos(10_000)]} +set_bench! {intersection_10k_pos_vs_100_neg, intersection, count, [pos(10_000), neg(100)]} +set_bench! {intersection_10k_pos_vs_10k_neg, intersection, count, [pos(10_000), neg(10_000)]} +set_bench! {intersection_random_100_vs_100, intersection, count, [random(100), random(100)]} +set_bench! {intersection_random_100_vs_10k, intersection, count, [random(100), random(10_000)]} +set_bench! {intersection_random_10k_vs_100, intersection, count, [random(10_000), random(100)]} +set_bench! {intersection_random_10k_vs_10k, intersection, count, [random(10_000), random(10_000)]} +set_bench! {intersection_staggered_100_vs_100, intersection, count, stagger(100, 1)} +set_bench! {intersection_staggered_10k_vs_10k, intersection, count, stagger(10_000, 1)} +set_bench! {intersection_staggered_100_vs_10k, intersection, count, stagger(100, 100)} +set_bench! {difference_random_100_vs_100, difference, count, [random(100), random(100)]} +set_bench! {difference_random_100_vs_10k, difference, count, [random(100), random(10_000)]} +set_bench! {difference_random_10k_vs_100, difference, count, [random(10_000), random(100)]} +set_bench! {difference_random_10k_vs_10k, difference, count, [random(10_000), random(10_000)]} +set_bench! {difference_staggered_100_vs_100, difference, count, stagger(100, 1)} +set_bench! {difference_staggered_10k_vs_10k, difference, count, stagger(10_000, 1)} +set_bench! {difference_staggered_100_vs_10k, difference, count, stagger(100, 100)} +set_bench! {is_subset_100_vs_100, is_subset, clone, [pos(100), pos(100)]} +set_bench! {is_subset_100_vs_10k, is_subset, clone, [pos(100), pos(10_000)]} +set_bench! {is_subset_10k_vs_100, is_subset, clone, [pos(10_000), pos(100)]} +set_bench! {is_subset_10k_vs_10k, is_subset, clone, [pos(10_000), pos(10_000)]} -- cgit v1.2.3