src/test/bench/core-map.rs

   1 // Copyright 2013 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 #![feature(std_misc, rand, duration, duration_span)]
  12
  13 use std::collections::{BTreeMap, HashMap, HashSet};
  14 use std::env;
  15 use std::__rand::{Rng, thread_rng};
  16 use std::time::Duration;
  17
  18 fn timed<F>(label: &str, f: F) where F: FnMut() {
  19     println!("  {}: {:?}", label, Duration::span(f));
  20 }
  21
  22 trait MutableMap {
  23     fn insert(&mut self, k: usize, v: usize);
  24     fn remove(&mut self, k: &usize) -> bool;
  25     fn find(&self, k: &usize) -> Option<&usize>;
  26 }
  27
  28 impl MutableMap for BTreeMap<usize, usize> {
  29     fn insert(&mut self, k: usize, v: usize) { self.insert(k, v); }
  30     fn remove(&mut self, k: &usize) -> bool { self.remove(k).is_some() }
  31     fn find(&self, k: &usize) -> Option<&usize> { self.get(k) }
  32 }
  33 impl MutableMap for HashMap<usize, usize> {
  34     fn insert(&mut self, k: usize, v: usize) { self.insert(k, v); }
  35     fn remove(&mut self, k: &usize) -> bool { self.remove(k).is_some() }
  36     fn find(&self, k: &usize) -> Option<&usize> { self.get(k) }
  37 }
  38
  39 fn ascending<M: MutableMap>(map: &mut M, n_keys: usize) {
  40     println!(" Ascending integers:");
  41
  42     timed("insert", || {
  43         for i in 0..n_keys {
  44             map.insert(i, i + 1);
  45         }
  46     });
  47
  48     timed("search", || {
  49         for i in 0..n_keys {
  50             assert_eq!(map.find(&i).unwrap(), &(i + 1));
  51         }
  52     });
  53
  54     timed("remove", || {
  55         for i in 0..n_keys {
  56             assert!(map.remove(&i));
  57         }
  58     });
  59 }
  60
  61 fn descending<M: MutableMap>(map: &mut M, n_keys: usize) {
  62     println!(" Descending integers:");
  63
  64     timed("insert", || {
  65         for i in (0..n_keys).rev() {
  66             map.insert(i, i + 1);
  67         }
  68     });
  69
  70     timed("search", || {
  71         for i in (0..n_keys).rev() {
  72             assert_eq!(map.find(&i).unwrap(), &(i + 1));
  73         }
  74     });
  75
  76     timed("remove", || {
  77         for i in 0..n_keys {
  78             assert!(map.remove(&i));
  79         }
  80     });
  81 }
  82
  83 fn vector<M: MutableMap>(map: &mut M, n_keys: usize, dist: &[usize]) {
  84     timed("insert", || {
  85         for i in 0..n_keys {
  86             map.insert(dist[i], i + 1);
  87         }
  88     });
  89
  90     timed("search", || {
  91         for i in 0..n_keys {
  92             assert_eq!(map.find(&dist[i]).unwrap(), &(i + 1));
  93         }
  94     });
  95
  96     timed("remove", || {
  97         for i in 0..n_keys {
  98             assert!(map.remove(&dist[i]));
  99         }
 100     });
 101 }
 102
 103 fn main() {
 104     let mut args = env::args();
 105     let n_keys = {
 106         if args.len() == 2 {
 107             args.nth(1).unwrap().parse::<usize>().unwrap()
 108         } else {
 109             1000000
 110         }
 111     };
 112
 113     let mut rand = Vec::with_capacity(n_keys);
 114
 115     {
 116         let seed: &[_] = &[1, 1, 1, 1, 1, 1, 1];
 117         let mut rng = thread_rng();
 118         let mut set = HashSet::new();
 119         while set.len() != n_keys {
 120             let next = rng.gen();
 121             if set.insert(next) {
 122                 rand.push(next);
 123             }
 124         }
 125     }
 126
 127     println!("{} keys", n_keys);
 128
 129     println!("\nBTreeMap:");
 130
 131     {
 132         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 133         ascending(&mut map, n_keys);
 134     }
 135
 136     {
 137         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 138         descending(&mut map, n_keys);
 139     }
 140
 141     {
 142         println!(" Random integers:");
 143         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 144         vector(&mut map, n_keys, &rand);
 145     }
 146
 147     println!("\nHashMap:");
 148
 149     {
 150         let mut map: HashMap<usize,usize> = HashMap::new();
 151         ascending(&mut map, n_keys);
 152     }
 153
 154     {
 155         let mut map: HashMap<usize,usize> = HashMap::new();
 156         descending(&mut map, n_keys);
 157     }
 158
 159     {
 160         println!(" Random integers:");
 161         let mut map: HashMap<usize,usize> = HashMap::new();
 162         vector(&mut map, n_keys, &rand);
 163     }
 164 }