auto merge of #5476 : thestinger/rust/bench, r=graydon

The old string benchmarks weren't very useful because the strings weren't long enough, so I just threw those out for now. I left out benchmarks of `oldmap` because it's clear that it's 30-40% slower and it doesn't implement the `Map` trait.

This also cleanly divides up `insert`, `search` and `remove`.

2 files changed, 87 insertions, 250 deletions

diff --git a/src/libcore/trie.rs b/src/libcore/trie.rs
index 6b2f2bb6a7d..3b9d3ad4b73 100644
--- a/src/libcore/trie.rs
+++ b/src/libcore/trie.rs
@@ -136,15 +136,13 @@ impl<T> Map<uint, T> for TrieMap<T> {
     }
 }
 
-impl<T> TrieMap<T> {
+pub impl<T> TrieMap<T> {
     /// Create an empty TrieMap
     #[inline(always)]
     static pure fn new() -> TrieMap<T> {
         TrieMap{root: TrieNode::new(), length: 0}
     }
-}
 
-impl<T> TrieMap<T> {
     /// Visit all keys in reverse order
     #[inline(always)]
     pure fn each_key_reverse(&self, f: &fn(&uint) -> bool) {
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index c86d2fe4d93..67281594a39 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -1,4 +1,4 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -9,322 +9,161 @@
 // except according to those terms.
 
 extern mod std;
-use std::oldmap;
-use std::treemap::TreeMap;
-use core::hashmap::linear::*;
-use core::io::WriterUtil;
-
-struct Results {
-    sequential_ints: float,
-    random_ints: float,
-    delete_ints: float,
-
-    sequential_strings: float,
-    random_strings: float,
-    delete_strings: float
-}
 
-fn timed(result: &mut float,
-         op: &fn()) {
-    let start = std::time::precise_time_s();
-    op();
-    let end = std::time::precise_time_s();
-    *result = (end - start);
+use core::io;
+use std::time;
+use std::treemap::TreeMap;
+use core::hashmap::linear::{LinearMap, LinearSet};
+use core::trie::TrieMap;
+
+fn timed(label: &str, f: &fn()) {
+    let start = time::precise_time_s();
+    f();
+    let end = time::precise_time_s();
+    io::println(fmt!("  %s: %f", label, end - start));
 }
 
-fn old_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
-
-    {
-        let map = oldmap::HashMap();
-        do timed(&mut results.sequential_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(i, i+1);
-            }
+fn ascending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
+    io::println(" Ascending integers:");
 
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.get(&i) == i+1);
-            }
+    do timed("insert") {
+        for uint::range(0, n_keys) |i| {
+            map.insert(i, i + 1);
         }
     }
 
-    {
-        let map = oldmap::HashMap();
-        do timed(&mut results.random_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(rng.next() as uint, i);
-            }
+    do timed("search") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.find(&i).unwrap() == &(i + 1));
         }
     }
 
-    {
-        let map = oldmap::HashMap();
-        for uint::range(0, num_keys) |i| {
-            map.insert(i, i);;
-        }
-
-        do timed(&mut results.delete_ints) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&i));
-            }
+    do timed("remove") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.remove(&i));
         }
     }
 }
 
-fn old_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
-    {
-        let map = oldmap::HashMap();
-        do timed(&mut results.sequential_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                map.insert(s, i);
-            }
+fn descending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
+    io::println(" Descending integers:");
 
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                fail_unless!(map.get(&s) == i);
-            }
+    do timed("insert") {
+        for uint::range(0, n_keys) |i| {
+            map.insert(i, i + 1);
         }
     }
 
-    {
-        let map = oldmap::HashMap();
-        do timed(&mut results.random_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(rng.next() as uint);
-                map.insert(s, i);
-            }
+    do timed("search") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.find(&i).unwrap() == &(i + 1));
         }
     }
 
-    {
-        let map = oldmap::HashMap();
-        for uint::range(0, num_keys) |i| {
-            map.insert(uint::to_str(i), i);
-        }
-        do timed(&mut results.delete_strings) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&uint::to_str(i)));
-            }
+    do timed("remove") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.remove(&i));
         }
     }
 }
 
-fn linear_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
-    {
-        let mut map = LinearMap::new();
-        do timed(&mut results.sequential_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(i, i+1);
-            }
+fn vector<M: Map<uint, uint>>(map: &mut M, n_keys: uint, dist: &[uint]) {
 
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.find(&i).unwrap() == &(i+1));
-            }
+    do timed("insert") {
+        for uint::range(0, n_keys) |i| {
+            map.insert(dist[i], i + 1);
         }
     }
 
-    {
-        let mut map = LinearMap::new();
-        do timed(&mut results.random_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(rng.next() as uint, i);
-            }
+    do timed("search") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.find(&dist[i]).unwrap() == &(i + 1));
         }
     }
 
-    {
-        let mut map = LinearMap::new();
-        for uint::range(0, num_keys) |i| {
-            map.insert(i, i);;
-        }
-
-        do timed(&mut results.delete_ints) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&i));
-            }
+    do timed("remove") {
+        for uint::range(0, n_keys) |i| {
+            fail_unless!(map.remove(&dist[i]));
         }
     }
 }
 
-fn linear_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
-    {
-        let mut map = LinearMap::new();
-        do timed(&mut results.sequential_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                map.insert(s, i);
-            }
-
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                fail_unless!(map.find(&s).unwrap() == &i);
-            }
+fn main() {
+    let args = os::args();
+    let n_keys = {
+        if args.len() == 2 {
+            uint::from_str(args[1]).get()
+        } else {
+            1000000
         }
-    }
+    };
 
-    {
-        let mut map = LinearMap::new();
-        do timed(&mut results.random_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(rng.next() as uint);
-                map.insert(s, i);
-            }
-        }
-    }
+    let mut rand = vec::with_capacity(n_keys);
 
     {
-        let mut map = LinearMap::new();
-        for uint::range(0, num_keys) |i| {
-            map.insert(uint::to_str(i), i);
-        }
-        do timed(&mut results.delete_strings) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&uint::to_str(i)));
+        let rng = core::rand::seeded_rng([1, 1, 1, 1, 1, 1, 1]);
+        let mut set = LinearSet::new();
+        while set.len() != n_keys {
+            let next = rng.next() as uint;
+            if set.insert(next) {
+                rand.push(next);
             }
         }
     }
-}
 
-fn tree_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
-    {
-        let mut map = TreeMap::new();
-        do timed(&mut results.sequential_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(i, i+1);
-            }
+    io::println(fmt!("%? keys", n_keys));
 
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.find(&i).unwrap() == &(i+1));
-            }
-        }
-    }
+    io::println("\nTreeMap:");
 
     {
-        let mut map = TreeMap::new();
-        do timed(&mut results.random_ints) {
-            for uint::range(0, num_keys) |i| {
-                map.insert(rng.next() as uint, i);
-            }
-        }
+        let mut map = TreeMap::new::<uint, uint>();
+        ascending(&mut map, n_keys);
     }
 
     {
-        let mut map = TreeMap::new();
-        for uint::range(0, num_keys) |i| {
-            map.insert(i, i);;
-        }
-
-        do timed(&mut results.delete_ints) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&i));
-            }
-        }
+        let mut map = TreeMap::new::<uint, uint>();
+        descending(&mut map, n_keys);
     }
-}
 
-fn tree_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
     {
-        let mut map = TreeMap::new();
-        do timed(&mut results.sequential_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                map.insert(s, i);
-            }
-
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(i);
-                fail_unless!(map.find(&s).unwrap() == &i);
-            }
-        }
+        io::println(" Random integers:");
+        let mut map = TreeMap::new::<uint, uint>();
+        vector(&mut map, n_keys, rand);
     }
 
+    io::println("\nLinearMap:");
+
     {
-        let mut map = TreeMap::new();
-        do timed(&mut results.random_strings) {
-            for uint::range(0, num_keys) |i| {
-                let s = uint::to_str(rng.next() as uint);
-                map.insert(s, i);
-            }
-        }
+        let mut map = LinearMap::new::<uint, uint>();
+        ascending(&mut map, n_keys);
     }
 
     {
-        let mut map = TreeMap::new();
-        for uint::range(0, num_keys) |i| {
-            map.insert(uint::to_str(i), i);
-        }
-        do timed(&mut results.delete_strings) {
-            for uint::range(0, num_keys) |i| {
-                fail_unless!(map.remove(&uint::to_str(i)));
-            }
-        }
+        let mut map = LinearMap::new::<uint, uint>();
+        descending(&mut map, n_keys);
     }
-}
-
-fn write_header(header: &str) {
-    io::stdout().write_str(header);
-    io::stdout().write_str("\n");
-}
-
-fn write_row(label: &str, value: float) {
-    io::stdout().write_str(fmt!("%30s %f s\n", label, value));
-}
-
-fn write_results(label: &str, results: &Results) {
-    write_header(label);
-    write_row("sequential_ints", results.sequential_ints);
-    write_row("random_ints", results.random_ints);
-    write_row("delete_ints", results.delete_ints);
-    write_row("sequential_strings", results.sequential_strings);
-    write_row("random_strings", results.random_strings);
-    write_row("delete_strings", results.delete_strings);
-}
 
-fn empty_results() -> Results {
-    Results {
-        sequential_ints: 0f,
-        random_ints: 0f,
-        delete_ints: 0f,
-
-        sequential_strings: 0f,
-        random_strings: 0f,
-        delete_strings: 0f,
+    {
+        io::println(" Random integers:");
+        let mut map = LinearMap::new::<uint, uint>();
+        vector(&mut map, n_keys, rand);
     }
-}
-
-fn main() {
-    let args = os::args();
-    let num_keys = {
-        if args.len() == 2 {
-            uint::from_str(args[1]).get()
-        } else {
-            100 // woefully inadequate for any real measurement
-        }
-    };
 
-    let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
+    io::println("\nTrieMap:");
 
     {
-        let rng = rand::seeded_rng(seed);
-        let mut results = empty_results();
-        old_int_benchmarks(rng, num_keys, &mut results);
-        old_str_benchmarks(rng, num_keys, &mut results);
-        write_results("std::oldmap::HashMap", &results);
+        let mut map = TrieMap::new::<uint>();
+        ascending(&mut map, n_keys);
     }
 
     {
-        let rng = rand::seeded_rng(seed);
-        let mut results = empty_results();
-        linear_int_benchmarks(rng, num_keys, &mut results);
-        linear_str_benchmarks(rng, num_keys, &mut results);
-        write_results("core::hashmap::linear::LinearMap", &results);
+        let mut map = TrieMap::new::<uint>();
+        descending(&mut map, n_keys);
     }
 
     {
-        let rng = rand::seeded_rng(seed);
-        let mut results = empty_results();
-        tree_int_benchmarks(rng, num_keys, &mut results);
-        tree_str_benchmarks(rng, num_keys, &mut results);
-        write_results("std::treemap::TreeMap", &results);
+        io::println(" Random integers:");
+        let mut map = TrieMap::new::<uint>();
+        vector(&mut map, n_keys, rand);
     }
 }