src/test/bench/core-set.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // ignore-pretty very bad with line comments
  12
  13 #![feature(unboxed_closures, rand, std_misc, collections, duration, duration_span)]
  14
  15 extern crate collections;
  16 extern crate rand;
  17
  18 use std::collections::BTreeSet;
  19 use std::collections::BitSet;
  20 use std::collections::HashSet;
  21 use std::hash::Hash;
  22 use std::env;
  23 use std::time::Duration;
  24
  25 struct Results {
  26     sequential_ints: Duration,
  27     random_ints: Duration,
  28     delete_ints: Duration,
  29
  30     sequential_strings: Duration,
  31     random_strings: Duration,
  32     delete_strings: Duration,
  33 }
  34
  35 fn timed<F>(result: &mut Duration, op: F) where F: FnOnce() {
  36     *result = Duration::span(op);
  37 }
  38
  39 trait MutableSet<T> {
  40     fn insert(&mut self, k: T);
  41     fn remove(&mut self, k: &T) -> bool;
  42     fn contains(&self, k: &T) -> bool;
  43 }
  44
  45 impl<T: Hash + Eq> MutableSet<T> for HashSet<T> {
  46     fn insert(&mut self, k: T) { self.insert(k); }
  47     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  48     fn contains(&self, k: &T) -> bool { self.contains(k) }
  49 }
  50 impl<T: Ord> MutableSet<T> for BTreeSet<T> {
  51     fn insert(&mut self, k: T) { self.insert(k); }
  52     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  53     fn contains(&self, k: &T) -> bool { self.contains(k) }
  54 }
  55 impl MutableSet<usize> for BitSet {
  56     fn insert(&mut self, k: usize) { self.insert(k); }
  57     fn remove(&mut self, k: &usize) -> bool { self.remove(k) }
  58     fn contains(&self, k: &usize) -> bool { self.contains(k) }
  59 }
  60
  61 impl Results {
  62     pub fn bench_int<T:MutableSet<usize>,
  63                      R:rand::Rng,
  64                      F:FnMut() -> T>(
  65                      &mut self,
  66                      rng: &mut R,
  67                      num_keys: usize,
  68                      rand_cap: usize,
  69                      mut f: F) {
  70         {
  71             let mut set = f();
  72             timed(&mut self.sequential_ints, || {
  73                 for i in 0..num_keys {
  74                     set.insert(i);
  75                 }
  76
  77                 for i in 0..num_keys {
  78                     assert!(set.contains(&i));
  79                 }
  80             })
  81         }
  82
  83         {
  84             let mut set = f();
  85             timed(&mut self.random_ints, || {
  86                 for _ in 0..num_keys {
  87                     set.insert(rng.gen::<usize>() % rand_cap);
  88                 }
  89             })
  90         }
  91
  92         {
  93             let mut set = f();
  94             for i in 0..num_keys {
  95                 set.insert(i);
  96             }
  97
  98             timed(&mut self.delete_ints, || {
  99                 for i in 0..num_keys {
 100                     assert!(set.remove(&i));
 101                 }
 102             })
 103         }
 104     }
 105
 106     pub fn bench_str<T:MutableSet<String>,
 107                      R:rand::Rng,
 108                      F:FnMut() -> T>(
 109                      &mut self,
 110                      rng: &mut R,
 111                      num_keys: usize,
 112                      mut f: F) {
 113         {
 114             let mut set = f();
 115             timed(&mut self.sequential_strings, || {
 116                 for i in 0..num_keys {
 117                     set.insert(i.to_string());
 118                 }
 119
 120                 for i in 0..num_keys {
 121                     assert!(set.contains(&i.to_string()));
 122                 }
 123             })
 124         }
 125
 126         {
 127             let mut set = f();
 128             timed(&mut self.random_strings, || {
 129                 for _ in 0..num_keys {
 130                     let s = rng.gen::<usize>().to_string();
 131                     set.insert(s);
 132                 }
 133             })
 134         }
 135
 136         {
 137             let mut set = f();
 138             for i in 0..num_keys {
 139                 set.insert(i.to_string());
 140             }
 141             timed(&mut self.delete_strings, || {
 142                 for i in 0..num_keys {
 143                     assert!(set.remove(&i.to_string()));
 144                 }
 145             })
 146         }
 147     }
 148 }
 149
 150 fn write_header(header: &str) {
 151     println!("{}", header);
 152 }
 153
 154 fn write_row(label: &str, value: Duration) {
 155     println!("{:30} {} s\n", label, value);
 156 }
 157
 158 fn write_results(label: &str, results: &Results) {
 159     write_header(label);
 160     write_row("sequential_ints", results.sequential_ints);
 161     write_row("random_ints", results.random_ints);
 162     write_row("delete_ints", results.delete_ints);
 163     write_row("sequential_strings", results.sequential_strings);
 164     write_row("random_strings", results.random_strings);
 165     write_row("delete_strings", results.delete_strings);
 166 }
 167
 168 fn empty_results() -> Results {
 169     Results {
 170         sequential_ints: Duration::new(0, 0),
 171         random_ints: Duration::new(0, 0),
 172         delete_ints: Duration::new(0, 0),
 173
 174         sequential_strings: Duration::new(0, 0),
 175         random_strings: Duration::new(0, 0),
 176         delete_strings: Duration::new(0, 0),
 177     }
 178 }
 179
 180 fn main() {
 181     let mut args = env::args();
 182     let num_keys = {
 183         if args.len() == 2 {
 184             args.nth(1).unwrap().parse::<usize>().unwrap()
 185         } else {
 186             100 // woefully inadequate for any real measurement
 187         }
 188     };
 189
 190     let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 191     let max = 200000;
 192
 193     {
 194         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 195         let mut results = empty_results();
 196         results.bench_int(&mut rng, num_keys, max, || {
 197             let s: HashSet<usize> = HashSet::new();
 198             s
 199         });
 200         results.bench_str(&mut rng, num_keys, || {
 201             let s: HashSet<String> = HashSet::new();
 202             s
 203         });
 204         write_results("collections::HashSet", &results);
 205     }
 206
 207     {
 208         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 209         let mut results = empty_results();
 210         results.bench_int(&mut rng, num_keys, max, || {
 211             let s: BTreeSet<usize> = BTreeSet::new();
 212             s
 213         });
 214         results.bench_str(&mut rng, num_keys, || {
 215             let s: BTreeSet<String> = BTreeSet::new();
 216             s
 217         });
 218         write_results("collections::BTreeSet", &results);
 219     }
 220
 221     {
 222         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 223         let mut results = empty_results();
 224         results.bench_int(&mut rng, num_keys, max, || BitSet::new());
 225         write_results("collections::bit_vec::BitSet", &results);
 226     }
 227 }