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(unboxed_closures)]
  12
  13 use std::collections::{BTreeMap, HashMap, HashSet};
  14 use std::os;
  15 use std::rand::{Rng, IsaacRng, SeedableRng};
  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: uint, v: uint);
  24     fn remove(&mut self, k: &uint) -> bool;
  25     fn find(&self, k: &uint) -> Option<&uint>;
  26 }
  27
  28 impl MutableMap for BTreeMap<uint, uint> {
  29     fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  30     fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  31     fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
  32 }
  33 impl MutableMap for HashMap<uint, uint> {
  34     fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  35     fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  36     fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
  37 }
  38
  39 fn ascending<M: MutableMap>(map: &mut M, n_keys: uint) {
  40     println!(" Ascending integers:");
  41
  42     timed("insert", || {
  43         for i in 0u..n_keys {
  44             map.insert(i, i + 1);
  45         }
  46     });
  47
  48     timed("search", || {
  49         for i in 0u..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: uint) {
  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: uint, dist: &[uint]) {
  84     timed("insert", || {
  85         for i in 0u..n_keys {
  86             map.insert(dist[i], i + 1);
  87         }
  88     });
  89
  90     timed("search", || {
  91         for i in 0u..n_keys {
  92             assert_eq!(map.find(&dist[i]).unwrap(), &(i + 1));
  93         }
  94     });
  95
  96     timed("remove", || {
  97         for i in 0u..n_keys {
  98             assert!(map.remove(&dist[i]));
  99         }
 100     });
 101 }
 102
 103 fn main() {
 104     let args = os::args();
 105     let args = args.as_slice();
 106     let n_keys = {
 107         if args.len() == 2 {
 108             args[1].parse::<uint>().unwrap()
 109         } else {
 110             1000000
 111         }
 112     };
 113
 114     let mut rand = Vec::with_capacity(n_keys);
 115
 116     {
 117         let seed: &[_] = &[1, 1, 1, 1, 1, 1, 1];
 118         let mut rng: IsaacRng = SeedableRng::from_seed(seed);
 119         let mut set = HashSet::new();
 120         while set.len() != n_keys {
 121             let next = rng.gen();
 122             if set.insert(next) {
 123                 rand.push(next);
 124             }
 125         }
 126     }
 127
 128     println!("{} keys", n_keys);
 129
 130     // FIXME: #9970
 131     println!("{}", "\nBTreeMap:");
 132
 133     {
 134         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 135         ascending(&mut map, n_keys);
 136     }
 137
 138     {
 139         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 140         descending(&mut map, n_keys);
 141     }
 142
 143     {
 144         println!(" Random integers:");
 145         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 146         vector(&mut map, n_keys, rand.as_slice());
 147     }
 148
 149     // FIXME: #9970
 150     println!("{}", "\nHashMap:");
 151
 152     {
 153         let mut map: HashMap<uint,uint> = HashMap::new();
 154         ascending(&mut map, n_keys);
 155     }
 156
 157     {
 158         let mut map: HashMap<uint,uint> = HashMap::new();
 159         descending(&mut map, n_keys);
 160     }
 161
 162     {
 163         println!(" Random integers:");
 164         let mut map: HashMap<uint,uint> = HashMap::new();
 165         vector(&mut map, n_keys, rand.as_slice());
 166     }
 167 }