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)]
  14
  15 extern crate collections;
  16 extern crate rand;
  17
  18 use std::collections::BTreeSet;
  19 use std::collections::BitvSet;
  20 use std::collections::HashSet;
  21 use std::hash::Hash;
  22 use std::os;
  23 use std::time::Duration;
  24 use std::uint;
  25
  26 struct Results {
  27     sequential_ints: Duration,
  28     random_ints: Duration,
  29     delete_ints: Duration,
  30
  31     sequential_strings: Duration,
  32     random_strings: Duration,
  33     delete_strings: Duration,
  34 }
  35
  36 fn timed<F>(result: &mut Duration, op: F) where F: FnOnce() {
  37     *result = Duration::span(op);
  38 }
  39
  40 trait MutableSet<T> {
  41     fn insert(&mut self, k: T);
  42     fn remove(&mut self, k: &T) -> bool;
  43     fn contains(&self, k: &T) -> bool;
  44 }
  45
  46 impl<T: Hash + Eq> MutableSet<T> for HashSet<T> {
  47     fn insert(&mut self, k: T) { self.insert(k); }
  48     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  49     fn contains(&self, k: &T) -> bool { self.contains(k) }
  50 }
  51 impl<T: Ord> MutableSet<T> for BTreeSet<T> {
  52     fn insert(&mut self, k: T) { self.insert(k); }
  53     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  54     fn contains(&self, k: &T) -> bool { self.contains(k) }
  55 }
  56 impl MutableSet<uint> for BitvSet {
  57     fn insert(&mut self, k: uint) { self.insert(k); }
  58     fn remove(&mut self, k: &uint) -> bool { self.remove(k) }
  59     fn contains(&self, k: &uint) -> bool { self.contains(k) }
  60 }
  61
  62 impl Results {
  63     pub fn bench_int<T:MutableSet<uint>,
  64                      R: rand::Rng>(
  65                      &mut self,
  66                      rng: &mut R,
  67                      num_keys: uint,
  68                      rand_cap: uint,
  69                      f: || -> T) { {
  70             let mut set = f();
  71             timed(&mut self.sequential_ints, || {
  72                 for i in range(0u, num_keys) {
  73                     set.insert(i);
  74                 }
  75
  76                 for i in range(0u, num_keys) {
  77                     assert!(set.contains(&i));
  78                 }
  79             })
  80         }
  81
  82         {
  83             let mut set = f();
  84             timed(&mut self.random_ints, || {
  85                 for _ in range(0, num_keys) {
  86                     set.insert(rng.gen::<uint>() % rand_cap);
  87                 }
  88             })
  89         }
  90
  91         {
  92             let mut set = f();
  93             for i in range(0u, num_keys) {
  94                 set.insert(i);
  95             }
  96
  97             timed(&mut self.delete_ints, || {
  98                 for i in range(0u, num_keys) {
  99                     assert!(set.remove(&i));
 100                 }
 101             })
 102         }
 103     }
 104
 105     pub fn bench_str<T:MutableSet<String>,
 106                      R:rand::Rng>(
 107                      &mut self,
 108                      rng: &mut R,
 109                      num_keys: uint,
 110                      f: || -> T) {
 111         {
 112             let mut set = f();
 113             timed(&mut self.sequential_strings, || {
 114                 for i in range(0u, num_keys) {
 115                     set.insert(i.to_string());
 116                 }
 117
 118                 for i in range(0u, num_keys) {
 119                     assert!(set.contains(&i.to_string()));
 120                 }
 121             })
 122         }
 123
 124         {
 125             let mut set = f();
 126             timed(&mut self.random_strings, || {
 127                 for _ in range(0, num_keys) {
 128                     let s = rng.gen::<uint>().to_string();
 129                     set.insert(s);
 130                 }
 131             })
 132         }
 133
 134         {
 135             let mut set = f();
 136             for i in range(0u, num_keys) {
 137                 set.insert(i.to_string());
 138             }
 139             timed(&mut self.delete_strings, || {
 140                 for i in range(0u, num_keys) {
 141                     assert!(set.remove(&i.to_string()));
 142                 }
 143             })
 144         }
 145     }
 146 }
 147
 148 fn write_header(header: &str) {
 149     println!("{}", header);
 150 }
 151
 152 fn write_row(label: &str, value: Duration) {
 153     println!("{:30} {} s\n", label, value);
 154 }
 155
 156 fn write_results(label: &str, results: &Results) {
 157     write_header(label);
 158     write_row("sequential_ints", results.sequential_ints);
 159     write_row("random_ints", results.random_ints);
 160     write_row("delete_ints", results.delete_ints);
 161     write_row("sequential_strings", results.sequential_strings);
 162     write_row("random_strings", results.random_strings);
 163     write_row("delete_strings", results.delete_strings);
 164 }
 165
 166 fn empty_results() -> Results {
 167     Results {
 168         sequential_ints: Duration::seconds(0),
 169         random_ints: Duration::seconds(0),
 170         delete_ints: Duration::seconds(0),
 171
 172         sequential_strings: Duration::seconds(0),
 173         random_strings: Duration::seconds(0),
 174         delete_strings: Duration::seconds(0),
 175     }
 176 }
 177
 178 fn main() {
 179     let args = os::args();
 180     let args = args.as_slice();
 181     let num_keys = {
 182         if args.len() == 2 {
 183             args[1].parse::<uint>().unwrap()
 184         } else {
 185             100 // woefully inadequate for any real measurement
 186         }
 187     };
 188
 189     let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 190     let max = 200000;
 191
 192     {
 193         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 194         let mut results = empty_results();
 195         results.bench_int(&mut rng, num_keys, max, || {
 196             let s: HashSet<uint> = HashSet::new();
 197             s
 198         });
 199         results.bench_str(&mut rng, num_keys, || {
 200             let s: HashSet<String> = HashSet::new();
 201             s
 202         });
 203         write_results("collections::HashSet", &results);
 204     }
 205
 206     {
 207         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 208         let mut results = empty_results();
 209         results.bench_int(&mut rng, num_keys, max, || {
 210             let s: BTreeSet<uint> = BTreeSet::new();
 211             s
 212         });
 213         results.bench_str(&mut rng, num_keys, || {
 214             let s: BTreeSet<String> = BTreeSet::new();
 215             s
 216         });
 217         write_results("collections::BTreeSet", &results);
 218     }
 219
 220     {
 221         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
 222         let mut results = empty_results();
 223         results.bench_int(&mut rng, num_keys, max, || BitvSet::new());
 224         write_results("collections::bitv::BitvSet", &results);
 225     }
 226 }