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     // FIXME: #9970
 130     println!("{}", "\nBTreeMap:");
 131
 132     {
 133         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 134         ascending(&mut map, n_keys);
 135     }
 136
 137     {
 138         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 139         descending(&mut map, n_keys);
 140     }
 141
 142     {
 143         println!(" Random integers:");
 144         let mut map: BTreeMap<usize,usize> = BTreeMap::new();
 145         vector(&mut map, n_keys, &rand);
 146     }
 147
 148     // FIXME: #9970
 149     println!("{}", "\nHashMap:");
 150
 151     {
 152         let mut map: HashMap<usize,usize> = HashMap::new();
 153         ascending(&mut map, n_keys);
 154     }
 155
 156     {
 157         let mut map: HashMap<usize,usize> = HashMap::new();
 158         descending(&mut map, n_keys);
 159     }
 160
 161     {
 162         println!(" Random integers:");
 163         let mut map: HashMap<usize,usize> = HashMap::new();
 164         vector(&mut map, n_keys, &rand);
 165     }
 166 }