improve worst-case performance of BTreeSet difference and intersection

1 files changed, 57 insertions, 57 deletions

diff --git a/src/liballoc/benches/btree/set.rs b/src/liballoc/benches/btree/set.rs
index 08e1db5fbb7..6357ea3ea11 100644
--- a/src/liballoc/benches/btree/set.rs
+++ b/src/liballoc/benches/btree/set.rs
@@ -3,59 +3,49 @@ use std::collections::BTreeSet;
 use rand::{thread_rng, Rng};
 use test::{black_box, Bencher};
 
-fn random(n1: u32, n2: u32) -> [BTreeSet<usize>; 2] {
+fn random(n: usize) -> BTreeSet<usize> {
     let mut rng = thread_rng();
-    let mut set1 = BTreeSet::new();
-    let mut set2 = BTreeSet::new();
-    for _ in 0..n1 {
-        let i = rng.gen::<usize>();
-        set1.insert(i);
+    let mut set = BTreeSet::new();
+    while set.len() < n {
+        set.insert(rng.gen());
     }
-    for _ in 0..n2 {
-        let i = rng.gen::<usize>();
-        set2.insert(i);
-    }
-    [set1, set2]
+    assert_eq!(set.len(), n);
+    set
 }
 
-fn staggered(n1: u32, n2: u32) -> [BTreeSet<u32>; 2] {
-    let mut even = BTreeSet::new();
-    let mut odd = BTreeSet::new();
-    for i in 0..n1 {
-        even.insert(i * 2);
-    }
-    for i in 0..n2 {
-        odd.insert(i * 2 + 1);
+fn neg(n: usize) -> BTreeSet<i32> {
+    let mut set = BTreeSet::new();
+    for i in -(n as i32)..=-1 {
+        set.insert(i);
     }
-    [even, odd]
+    assert_eq!(set.len(), n);
+    set
 }
 
-fn neg_vs_pos(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
-    let mut neg = BTreeSet::new();
-    let mut pos = BTreeSet::new();
-    for i in -(n1 as i32)..=-1 {
-        neg.insert(i);
-    }
-    for i in 1..=(n2 as i32) {
-        pos.insert(i);
+fn pos(n: usize) -> BTreeSet<i32> {
+    let mut set = BTreeSet::new();
+    for i in 1..=(n as i32) {
+        set.insert(i);
     }
-    [neg, pos]
+    assert_eq!(set.len(), n);
+    set
 }
 
-fn pos_vs_neg(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
-    let mut neg = BTreeSet::new();
-    let mut pos = BTreeSet::new();
-    for i in -(n1 as i32)..=-1 {
-        neg.insert(i);
-    }
-    for i in 1..=(n2 as i32) {
-        pos.insert(i);
+
+fn stagger(n1: usize, factor: usize) -> [BTreeSet<u32>; 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);
     }
-    [pos, neg]
+    assert_eq!(sets[0].len(), n1);
+    assert_eq!(sets[1].len(), n2);
+    sets
 }
 
-macro_rules! set_intersection_bench {
-    ($name: ident, $sets: expr) => {
+macro_rules! set_bench {
+    ($name: ident, $set_func: ident, $result_func: ident, $sets: expr) => {
         #[bench]
         pub fn $name(b: &mut Bencher) {
             // setup
@@ -63,26 +53,36 @@ macro_rules! set_intersection_bench {
 
             // measure
             b.iter(|| {
-                let x = sets[0].intersection(&sets[1]).count();
+                let x = sets[0].$set_func(&sets[1]).$result_func();
                 black_box(x);
             })
         }
     };
 }
 
-set_intersection_bench! {intersect_random_100,          random(100, 100)}
-set_intersection_bench! {intersect_random_10k,          random(10_000, 10_000)}
-set_intersection_bench! {intersect_random_10_vs_10k,    random(10, 10_000)}
-set_intersection_bench! {intersect_random_10k_vs_10,    random(10_000, 10)}
-set_intersection_bench! {intersect_staggered_100,       staggered(100, 100)}
-set_intersection_bench! {intersect_staggered_10k,       staggered(10_000, 10_000)}
-set_intersection_bench! {intersect_staggered_10_vs_10k, staggered(10, 10_000)}
-set_intersection_bench! {intersect_staggered_10k_vs_10, staggered(10_000, 10)}
-set_intersection_bench! {intersect_neg_vs_pos_100,      neg_vs_pos(100, 100)}
-set_intersection_bench! {intersect_neg_vs_pos_10k,      neg_vs_pos(10_000, 10_000)}
-set_intersection_bench! {intersect_neg_vs_pos_10_vs_10k,neg_vs_pos(10, 10_000)}
-set_intersection_bench! {intersect_neg_vs_pos_10k_vs_10,neg_vs_pos(10_000, 10)}
-set_intersection_bench! {intersect_pos_vs_neg_100,      pos_vs_neg(100, 100)}
-set_intersection_bench! {intersect_pos_vs_neg_10k,      pos_vs_neg(10_000, 10_000)}
-set_intersection_bench! {intersect_pos_vs_neg_10_vs_10k,pos_vs_neg(10, 10_000)}
-set_intersection_bench! {intersect_pos_vs_neg_10k_vs_10,pos_vs_neg(10_000, 10)}
+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)]}