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 #![feature(bitset)]
  15
  16 extern crate collections;
  17 extern crate rand;
  18
  19 use std::collections::BTreeSet;
  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
  56 impl Results {
  57     pub fn bench_int<T:MutableSet<usize>,
  58                      R:rand::Rng,
  59                      F:FnMut() -> T>(
  60                      &mut self,
  61                      rng: &mut R,
  62                      num_keys: usize,
  63                      rand_cap: usize,
  64                      mut f: F) {
  65         {
  66             let mut set = f();
  67             timed(&mut self.sequential_ints, || {
  68                 for i in 0..num_keys {
  69                     set.insert(i);
  70                 }
  71
  72                 for i in 0..num_keys {
  73                     assert!(set.contains(&i));
  74                 }
  75             })
  76         }
  77
  78         {
  79             let mut set = f();
  80             timed(&mut self.random_ints, || {
  81                 for _ in 0..num_keys {
  82                     set.insert(rng.gen::<usize>() % rand_cap);
  83                 }
  84             })
  85         }
  86
  87         {
  88             let mut set = f();
  89             for i in 0..num_keys {
  90                 set.insert(i);
  91             }
  92
  93             timed(&mut self.delete_ints, || {
  94                 for i in 0..num_keys {
  95                     assert!(set.remove(&i));
  96                 }
  97             })
  98         }
  99     }
 100
 101     pub fn bench_str<T:MutableSet<String>,
 102                      R:rand::Rng,
 103                      F:FnMut() -> T>(
 104                      &mut self,
 105                      rng: &mut R,
 106                      num_keys: usize,
 107                      mut f: F) {
 108         {
 109             let mut set = f();
 110             timed(&mut self.sequential_strings, || {
 111                 for i in 0..num_keys {
 112                     set.insert(i.to_string());
 113                 }
 114
 115                 for i in 0..num_keys {
 116                     assert!(set.contains(&i.to_string()));
 117                 }
 118             })
 119         }
 120
 121         {
 122             let mut set = f();
 123             timed(&mut self.random_strings, || {
 124                 for _ in 0..num_keys {
 125                     let s = rng.gen::<usize>().to_string();
 126                     set.insert(s);
 127                 }
 128             })
 129         }
 130
 131         {
 132             let mut set = f();
 133             for i in 0..num_keys {
 134                 set.insert(i.to_string());
 135             }
 136             timed(&mut self.delete_strings, || {
 137                 for i in 0..num_keys {
 138                     assert!(set.remove(&i.to_string()));
 139                 }
 140             })
 141         }
 142     }
 143 }
 144
 145 fn write_header(header: &str) {
 146     println!("{}", header);
 147 }
 148
 149 fn write_row(label: &str, value: Duration) {
 150     println!("{:30} {:?} s\n", label, value);
 151 }
 152
 153 fn write_results(label: &str, results: &Results) {
 154     write_header(label);
 155     write_row("sequential_ints", results.sequential_ints);
 156     write_row("random_ints", results.random_ints);
 157     write_row("delete_ints", results.delete_ints);
 158     write_row("sequential_strings", results.sequential_strings);
 159     write_row("random_strings", results.random_strings);
 160     write_row("delete_strings", results.delete_strings);
 161 }
 162
 163 fn empty_results() -> Results {
 164     Results {
 165         sequential_ints: Duration::new(0, 0),
 166         random_ints: Duration::new(0, 0),
 167         delete_ints: Duration::new(0, 0),
 168
 169         sequential_strings: Duration::new(0, 0),
 170         random_strings: Duration::new(0, 0),
 171         delete_strings: Duration::new(0, 0),
 172     }
 173 }
 174
 175 fn main() {
 176     let mut args = env::args();
 177     let num_keys = {
 178         if args.len() == 2 {
 179             args.nth(1).unwrap().parse::<usize>().unwrap()
 180         } else {
 181             100 // woefully inadequate for any real measurement
 182         }
 183     };
 184
 185     let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 186     let max = 200000;
 187
 188     {
 189         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 190         let mut results = empty_results();
 191         results.bench_int(&mut rng, num_keys, max, || {
 192             let s: HashSet<usize> = HashSet::new();
 193             s
 194         });
 195         results.bench_str(&mut rng, num_keys, || {
 196             let s: HashSet<String> = HashSet::new();
 197             s
 198         });
 199         write_results("collections::HashSet", &results);
 200     }
 201
 202     {
 203         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 204         let mut results = empty_results();
 205         results.bench_int(&mut rng, num_keys, max, || {
 206             let s: BTreeSet<usize> = BTreeSet::new();
 207             s
 208         });
 209         results.bench_str(&mut rng, num_keys, || {
 210             let s: BTreeSet<String> = BTreeSet::new();
 211             s
 212         });
 213         write_results("collections::BTreeSet", &results);
 214     }
 215 }