Rust performance for maps with uint keys

0 Results.md

Benchmarks on different Map implementations for uint keys

Environment:

$ rustc --version
rustc 0.13.0-nightly (770378a31 2014-11-20 23:02:01 +0000)
$ uname -sm
Linux x86_64

No optimizations. No debug info

$ rustc --test maps.rs  && ./maps --bench

running 5 tests
test btree_map ... bench:      2766 ns/iter (+/- 64)
test hash_map  ... bench:      1666 ns/iter (+/- 208)
test tree_map  ... bench:      1877 ns/iter (+/- 53)
test trie_map  ... bench:       439 ns/iter (+/- 9)
test vec_map   ... bench:       100 ns/iter (+/- 4)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured

No optimizations. Debug info

$ rustc -g --test maps.rs  && ./maps --bench

running 5 tests
test btree_map ... bench:      2543 ns/iter (+/- 151)
test hash_map  ... bench:      2107 ns/iter (+/- 313)
test tree_map  ... bench:      1927 ns/iter (+/- 58)
test trie_map  ... bench:       473 ns/iter (+/- 44)
test vec_map   ... bench:       121 ns/iter (+/- 12)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured

Optimizations. Debug info

$ rustc -O -g --test maps.rs  && ./maps --bench

running 5 tests
test btree_map ... bench:       249 ns/iter (+/- 25)
test hash_map  ... bench:       169 ns/iter (+/- 26)
test tree_map  ... bench:       521 ns/iter (+/- 15)
test trie_map  ... bench:       138 ns/iter (+/- 11)
test vec_map   ... bench:        21 ns/iter (+/- 2)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured

Optimizations. No debug info

$ rustc -O --test maps.rs  && ./maps --bench

running 5 tests
test btree_map ... bench:       297 ns/iter (+/- 15)
test hash_map  ... bench:       173 ns/iter (+/- 30)
test tree_map  ... bench:       478 ns/iter (+/- 16)
test trie_map  ... bench:       130 ns/iter (+/- 3)
test vec_map   ... bench:        20 ns/iter (+/- 2)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured

maps.rs

extern crate test;
extern crate core;

use std::collections::{TrieMap, BTreeMap, TreeMap, HashMap, VecMap};
use core::fmt::Show;

trait MutableMap {
  fn insert(&mut self, k: uint, v: uint);
  fn remove(&mut self, k: &uint) -> bool;
  fn find(&self, k: &uint) -> Option<&uint>;
}

impl MutableMap for TreeMap<uint, uint> {
  fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
}
impl MutableMap for HashMap<uint, uint> {
  fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
}
impl MutableMap for TrieMap<uint> {
  fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
}
impl MutableMap for BTreeMap<uint, uint> {
  fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
}
impl MutableMap for VecMap<uint> {
  fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
}

fn map_bench<M: MutableMap + Show>(map: &mut M, b: &mut test::Bencher) {
  let mut key = 0u;

  b.iter(|| {
    key = key + 1;
    map.insert(key, 0u);
    if key > 100 && key % 10 == 0 {
      let r = key - 17;
      map.remove(&r);
      map.insert(key + 13, 1);
      map.insert(key + 11, 1);
    }
  });

  // println!("map = {}", map);
  // println!("key = {}", key);
}

#[bench]
fn btree_map(b: &mut test::Bencher) {
  map_bench(&mut BTreeMap::new(), b);
}

#[bench]
fn trie_map(b: &mut test::Bencher) {
  map_bench(&mut TrieMap::new(), b);
}

#[bench]
fn tree_map(b: &mut test::Bencher) {
  map_bench(&mut TreeMap::new(), b);
}

#[bench]
fn hash_map(b: &mut test::Bencher) {
  map_bench(&mut HashMap::new(), b);
}

#[bench]
fn vec_map(b: &mut test::Bencher) {
  map_bench(&mut VecMap::new(), b);
}