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::str::from_str;
  24 use std::time::Duration;
  25 use std::uint;
  26
  27 struct Results {
  28     sequential_ints: Duration,
  29     random_ints: Duration,
  30     delete_ints: Duration,
  31
  32     sequential_strings: Duration,
  33     random_strings: Duration,
  34     delete_strings: Duration,
  35 }
  36
  37 fn timed<F>(result: &mut Duration, op: F) where F: FnOnce() {
  38     *result = Duration::span(op);
  39 }
  40
  41 trait MutableSet<T> {
  42     fn insert(&mut self, k: T);
  43     fn remove(&mut self, k: &T) -> bool;
  44     fn contains(&self, k: &T) -> bool;
  45 }
  46
  47 impl<T: Hash + Eq> MutableSet<T> for HashSet<T> {
  48     fn insert(&mut self, k: T) { self.insert(k); }
  49     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  50     fn contains(&self, k: &T) -> bool { self.contains(k) }
  51 }
  52 impl<T: Ord> MutableSet<T> for BTreeSet<T> {
  53     fn insert(&mut self, k: T) { self.insert(k); }
  54     fn remove(&mut self, k: &T) -> bool { self.remove(k) }
  55     fn contains(&self, k: &T) -> bool { self.contains(k) }
  56 }
  57 impl MutableSet<uint> for BitvSet {
  58     fn insert(&mut self, k: uint) { self.insert(k); }
  59     fn remove(&mut self, k: &uint) -> bool { self.remove(k) }
  60     fn contains(&self, k: &uint) -> bool { self.contains(k) }
  61 }
  62
  63 impl Results {
  64     pub fn bench_int<T:MutableSet<uint>,
  65                      R: rand::Rng>(
  66                      &mut self,
  67                      rng: &mut R,
  68                      num_keys: uint,
  69                      rand_cap: uint,
  70                      f: || -> T) { {
  71             let mut set = f();
  72             timed(&mut self.sequential_ints, || {
  73                 for i in range(0u, num_keys) {
  74                     set.insert(i);
  75                 }
  76
  77                 for i in range(0u, 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 range(0, num_keys) {
  87                     set.insert(rng.gen::<uint>() % rand_cap);
  88                 }
  89             })
  90         }
  91
  92         {
  93             let mut set = f();
  94             for i in range(0u, num_keys) {
  95                 set.insert(i);
  96             }
  97
  98             timed(&mut self.delete_ints, || {
  99                 for i in range(0u, 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                      &mut self,
 109                      rng: &mut R,
 110                      num_keys: uint,
 111                      f: || -> T) {
 112         {
 113             let mut set = f();
 114             timed(&mut self.sequential_strings, || {
 115                 for i in range(0u, num_keys) {
 116                     set.insert(i.to_string());
 117                 }
 118
 119                 for i in range(0u, num_keys) {
 120                     assert!(set.contains(&i.to_string()));
 121                 }
 122             })
 123         }
 124
 125         {
 126             let mut set = f();
 127             timed(&mut self.random_strings, || {
 128                 for _ in range(0, num_keys) {
 129                     let s = rng.gen::<uint>().to_string();
 130                     set.insert(s);
 131                 }
 132             })
 133         }
 134
 135         {
 136             let mut set = f();
 137             for i in range(0u, num_keys) {
 138                 set.insert(i.to_string());
 139             }
 140             timed(&mut self.delete_strings, || {
 141                 for i in range(0u, num_keys) {
 142                     assert!(set.remove(&i.to_string()));
 143                 }
 144             })
 145         }
 146     }
 147 }
 148
 149 fn write_header(header: &str) {
 150     println!("{}", header);
 151 }
 152
 153 fn write_row(label: &str, value: Duration) {
 154     println!("{:30} {} s\n", label, value);
 155 }
 156
 157 fn write_results(label: &str, results: &Results) {
 158     write_header(label);
 159     write_row("sequential_ints", results.sequential_ints);
 160     write_row("random_ints", results.random_ints);
 161     write_row("delete_ints", results.delete_ints);
 162     write_row("sequential_strings", results.sequential_strings);
 163     write_row("random_strings", results.random_strings);
 164     write_row("delete_strings", results.delete_strings);
 165 }
 166
 167 fn empty_results() -> Results {
 168     Results {
 169         sequential_ints: Duration::seconds(0),
 170         random_ints: Duration::seconds(0),
 171         delete_ints: Duration::seconds(0),
 172
 173         sequential_strings: Duration::seconds(0),
 174         random_strings: Duration::seconds(0),
 175         delete_strings: Duration::seconds(0),
 176     }
 177 }
 178
 179 fn main() {
 180     let args = os::args();
 181     let args = args.as_slice();
 182     let num_keys = {
 183         if args.len() == 2 {
 184             from_str::<uint>(args[1].as_slice()).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<uint> = 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<uint> = 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, || BitvSet::new());
 225         write_results("collections::bitv::BitvSet", &results);
 226     }
 227 }