src/liballoc/benches/btree/set.rs

   1 use std::collections::BTreeSet;
   2
   3 use rand::{thread_rng, Rng};
   4 use test::{black_box, Bencher};
   5
   6 fn random(n1: u32, n2: u32) -> [BTreeSet<usize>; 2] {
   7     let mut rng = thread_rng();
   8     let mut set1 = BTreeSet::new();
   9     let mut set2 = BTreeSet::new();
  10     for _ in 0..n1 {
  11         let i = rng.gen::<usize>();
  12         set1.insert(i);
  13     }
  14     for _ in 0..n2 {
  15         let i = rng.gen::<usize>();
  16         set2.insert(i);
  17     }
  18     [set1, set2]
  19 }
  20
  21 fn staggered(n1: u32, n2: u32) -> [BTreeSet<u32>; 2] {
  22     let mut even = BTreeSet::new();
  23     let mut odd = BTreeSet::new();
  24     for i in 0..n1 {
  25         even.insert(i * 2);
  26     }
  27     for i in 0..n2 {
  28         odd.insert(i * 2 + 1);
  29     }
  30     [even, odd]
  31 }
  32
  33 fn neg_vs_pos(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
  34     let mut neg = BTreeSet::new();
  35     let mut pos = BTreeSet::new();
  36     for i in -(n1 as i32)..=-1 {
  37         neg.insert(i);
  38     }
  39     for i in 1..=(n2 as i32) {
  40         pos.insert(i);
  41     }
  42     [neg, pos]
  43 }
  44
  45 fn pos_vs_neg(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
  46     let mut neg = BTreeSet::new();
  47     let mut pos = BTreeSet::new();
  48     for i in -(n1 as i32)..=-1 {
  49         neg.insert(i);
  50     }
  51     for i in 1..=(n2 as i32) {
  52         pos.insert(i);
  53     }
  54     [pos, neg]
  55 }
  56
  57 macro_rules! set_intersection_bench {
  58     ($name: ident, $sets: expr) => {
  59         #[bench]
  60         pub fn $name(b: &mut Bencher) {
  61             // setup
  62             let sets = $sets;
  63
  64             // measure
  65             b.iter(|| {
  66                 let x = sets[0].intersection(&sets[1]).count();
  67                 black_box(x);
  68             })
  69         }
  70     };
  71 }
  72
  73 set_intersection_bench! {intersect_random_100,          random(100, 100)}
  74 set_intersection_bench! {intersect_random_10k,          random(10_000, 10_000)}
  75 set_intersection_bench! {intersect_random_10_vs_10k,    random(10, 10_000)}
  76 set_intersection_bench! {intersect_random_10k_vs_10,    random(10_000, 10)}
  77 set_intersection_bench! {intersect_staggered_100,       staggered(100, 100)}
  78 set_intersection_bench! {intersect_staggered_10k,       staggered(10_000, 10_000)}
  79 set_intersection_bench! {intersect_staggered_10_vs_10k, staggered(10, 10_000)}
  80 set_intersection_bench! {intersect_staggered_10k_vs_10, staggered(10_000, 10)}
  81 set_intersection_bench! {intersect_neg_vs_pos_100,      neg_vs_pos(100, 100)}
  82 set_intersection_bench! {intersect_neg_vs_pos_10k,      neg_vs_pos(10_000, 10_000)}
  83 set_intersection_bench! {intersect_neg_vs_pos_10_vs_10k,neg_vs_pos(10, 10_000)}
  84 set_intersection_bench! {intersect_neg_vs_pos_10k_vs_10,neg_vs_pos(10_000, 10)}
  85 set_intersection_bench! {intersect_pos_vs_neg_100,      pos_vs_neg(100, 100)}
  86 set_intersection_bench! {intersect_pos_vs_neg_10k,      pos_vs_neg(10_000, 10_000)}
  87 set_intersection_bench! {intersect_pos_vs_neg_10_vs_10k,pos_vs_neg(10, 10_000)}
  88 set_intersection_bench! {intersect_pos_vs_neg_10k_vs_10,pos_vs_neg(10_000, 10)}