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