auto merge of #7912 : graydon/rust/extra-new-benchmarks-1, r=catamorphism

This adds new #[bench] benchmarks for extra::smallintmap, treemap, sha1, sha256 and 512, and base64. Also fixes a bunch of warnings in bitv.

6 files changed, 409 insertions, 68 deletions

diff --git a/src/libextra/base64.rs b/src/libextra/base64.rs
index 449a9aba4a7..3c549d42917 100644
--- a/src/libextra/base64.rs
+++ b/src/libextra/base64.rs
@@ -284,81 +284,109 @@ impl<'self> FromBase64 for &'self str {
     }
 }
 
-#[test]
-fn test_to_base64_basic() {
-    assert_eq!("".to_base64(STANDARD), ~"");
-    assert_eq!("f".to_base64(STANDARD), ~"Zg==");
-    assert_eq!("fo".to_base64(STANDARD), ~"Zm8=");
-    assert_eq!("foo".to_base64(STANDARD), ~"Zm9v");
-    assert_eq!("foob".to_base64(STANDARD), ~"Zm9vYg==");
-    assert_eq!("fooba".to_base64(STANDARD), ~"Zm9vYmE=");
-    assert_eq!("foobar".to_base64(STANDARD), ~"Zm9vYmFy");
-}
+#[cfg(test)]
+mod test {
+    use test::BenchHarness;
+    use base64::*;
+
+    #[test]
+    fn test_to_base64_basic() {
+        assert_eq!("".to_base64(STANDARD), ~"");
+        assert_eq!("f".to_base64(STANDARD), ~"Zg==");
+        assert_eq!("fo".to_base64(STANDARD), ~"Zm8=");
+        assert_eq!("foo".to_base64(STANDARD), ~"Zm9v");
+        assert_eq!("foob".to_base64(STANDARD), ~"Zm9vYg==");
+        assert_eq!("fooba".to_base64(STANDARD), ~"Zm9vYmE=");
+        assert_eq!("foobar".to_base64(STANDARD), ~"Zm9vYmFy");
+    }
 
-#[test]
-fn test_to_base64_line_break() {
-    assert!(![0u8, 1000].to_base64(Config {line_length: None, ..STANDARD})
-        .contains("\r\n"));
-    assert_eq!("foobar".to_base64(Config {line_length: Some(4), ..STANDARD}),
-        ~"Zm9v\r\nYmFy");
-}
+    #[test]
+    fn test_to_base64_line_break() {
+        assert!(![0u8, 1000].to_base64(Config {line_length: None, ..STANDARD})
+                .contains("\r\n"));
+        assert_eq!("foobar".to_base64(Config {line_length: Some(4), ..STANDARD}),
+                   ~"Zm9v\r\nYmFy");
+    }
 
-#[test]
-fn test_to_base64_padding() {
-    assert_eq!("f".to_base64(Config {pad: false, ..STANDARD}), ~"Zg");
-    assert_eq!("fo".to_base64(Config {pad: false, ..STANDARD}), ~"Zm8");
-}
+    #[test]
+    fn test_to_base64_padding() {
+        assert_eq!("f".to_base64(Config {pad: false, ..STANDARD}), ~"Zg");
+        assert_eq!("fo".to_base64(Config {pad: false, ..STANDARD}), ~"Zm8");
+    }
 
-#[test]
-fn test_to_base64_url_safe() {
-    assert_eq!([251, 255].to_base64(URL_SAFE), ~"-_8");
-    assert_eq!([251, 255].to_base64(STANDARD), ~"+/8=");
-}
+    #[test]
+    fn test_to_base64_url_safe() {
+        assert_eq!([251, 255].to_base64(URL_SAFE), ~"-_8");
+        assert_eq!([251, 255].to_base64(STANDARD), ~"+/8=");
+    }
 
-#[test]
-fn test_from_base64_basic() {
-    assert_eq!("".from_base64().get(), "".as_bytes().to_owned());
-    assert_eq!("Zg==".from_base64().get(), "f".as_bytes().to_owned());
-    assert_eq!("Zm8=".from_base64().get(), "fo".as_bytes().to_owned());
-    assert_eq!("Zm9v".from_base64().get(), "foo".as_bytes().to_owned());
-    assert_eq!("Zm9vYg==".from_base64().get(), "foob".as_bytes().to_owned());
-    assert_eq!("Zm9vYmE=".from_base64().get(), "fooba".as_bytes().to_owned());
-    assert_eq!("Zm9vYmFy".from_base64().get(), "foobar".as_bytes().to_owned());
-}
+    #[test]
+    fn test_from_base64_basic() {
+        assert_eq!("".from_base64().get(), "".as_bytes().to_owned());
+        assert_eq!("Zg==".from_base64().get(), "f".as_bytes().to_owned());
+        assert_eq!("Zm8=".from_base64().get(), "fo".as_bytes().to_owned());
+        assert_eq!("Zm9v".from_base64().get(), "foo".as_bytes().to_owned());
+        assert_eq!("Zm9vYg==".from_base64().get(), "foob".as_bytes().to_owned());
+        assert_eq!("Zm9vYmE=".from_base64().get(), "fooba".as_bytes().to_owned());
+        assert_eq!("Zm9vYmFy".from_base64().get(), "foobar".as_bytes().to_owned());
+    }
 
-#[test]
-fn test_from_base64_newlines() {
-    assert_eq!("Zm9v\r\nYmFy".from_base64().get(),
-        "foobar".as_bytes().to_owned());
-}
+    #[test]
+    fn test_from_base64_newlines() {
+        assert_eq!("Zm9v\r\nYmFy".from_base64().get(),
+                   "foobar".as_bytes().to_owned());
+    }
 
-#[test]
-fn test_from_base64_urlsafe() {
-    assert_eq!("-_8".from_base64().get(), "+/8=".from_base64().get());
-}
+    #[test]
+    fn test_from_base64_urlsafe() {
+        assert_eq!("-_8".from_base64().get(), "+/8=".from_base64().get());
+    }
 
-#[test]
-fn test_from_base64_invalid_char() {
-    assert!("Zm$=".from_base64().is_err())
-    assert!("Zg==$".from_base64().is_err());
-}
+    #[test]
+    fn test_from_base64_invalid_char() {
+        assert!("Zm$=".from_base64().is_err())
+            assert!("Zg==$".from_base64().is_err());
+    }
 
-#[test]
-fn test_from_base64_invalid_padding() {
-    assert!("Z===".from_base64().is_err());
-}
+    #[test]
+    fn test_from_base64_invalid_padding() {
+        assert!("Z===".from_base64().is_err());
+    }
 
-#[test]
-fn test_base64_random() {
-    use std::rand::{task_rng, random, RngUtil};
-    use std::vec;
+    #[test]
+    fn test_base64_random() {
+        use std::rand::{task_rng, random, RngUtil};
+        use std::vec;
 
-    for 1000.times {
-        let v: ~[u8] = do vec::build |push| {
-            for task_rng().gen_uint_range(1, 100).times {
-                push(random());
-            }
-        };
-        assert_eq!(v.to_base64(STANDARD).from_base64().get(), v);
+        for 1000.times {
+            let v: ~[u8] = do vec::build |push| {
+                for task_rng().gen_uint_range(1, 100).times {
+                    push(random());
+                }
+            };
+            assert_eq!(v.to_base64(STANDARD).from_base64().get(), v);
+        }
     }
-}
+
+    #[bench]
+    pub fn to_base64(bh: & mut BenchHarness) {
+        let s = "イロハニホヘト チリヌルヲ ワカヨタレソ ツネナラム \
+                 ウヰノオクヤマ ケフコエテ アサキユメミシ ヱヒモセスン";
+        do bh.iter {
+            s.to_base64(STANDARD);
+        }
+        bh.bytes = s.len() as u64;
+    }
+
+    #[bench]
+    pub fn from_base64(bh: & mut BenchHarness) {
+        let s = "イロハニホヘト チリヌルヲ ワカヨタレソ ツネナラム \
+                 ウヰノオクヤマ ケフコエテ アサキユメミシ ヱヒモセスン";
+        let b = s.to_base64(STANDARD);
+        do bh.iter {
+            b.from_base64();
+        }
+        bh.bytes = b.len() as u64;
+    }
+
+}
\ No newline at end of file
diff --git a/src/libextra/container.rs b/src/libextra/container.rs
index fe622289b29..7b072b7cd46 100644
--- a/src/libextra/container.rs
+++ b/src/libextra/container.rs
@@ -38,3 +38,86 @@ pub trait Deque<T> : Mutable {
     /// Remove the first element and return it, or None if the sequence is empty
     fn pop_front(&mut self) -> Option<T>;
 }
+
+#[cfg(test)]
+mod bench {
+
+    use std::container::MutableMap;
+    use std::{vec,rand,uint};
+    use std::rand::RngUtil;
+    use test::BenchHarness;
+
+    pub fn insert_rand_n<M:MutableMap<uint,uint>>(n: uint,
+                                                  map: &mut M,
+                                                  bh: &mut BenchHarness) {
+        // setup
+        let mut rng = rand::XorShiftRng::new();
+
+        map.clear();
+        for uint::range(0,n) |_i| {
+            map.insert(rng.gen::<uint>() % n, 1);
+        }
+
+        // measure
+        do bh.iter {
+            let k = rng.gen::<uint>() % n;
+            map.insert(k, 1);
+            map.remove(&k);
+        }
+    }
+
+    pub fn insert_seq_n<M:MutableMap<uint,uint>>(n: uint,
+                                                 map: &mut M,
+                                                 bh: &mut BenchHarness) {
+        // setup
+        map.clear();
+        for uint::range(0, n) |i| {
+            map.insert(i*2, 1);
+        }
+
+        // measure
+        let mut i = 1;
+        do bh.iter {
+            map.insert(i, 1);
+            map.remove(&i);
+            i = (i + 2) % n;
+        }
+    }
+
+    pub fn find_rand_n<M:MutableMap<uint,uint>>(n: uint,
+                                                map: &mut M,
+                                                bh: &mut BenchHarness) {
+        // setup
+        let mut rng = rand::XorShiftRng::new();
+        let mut keys = vec::from_fn(n, |_| rng.gen::<uint>() % n);
+
+        for keys.iter().advance() |k| {
+            map.insert(*k, 1);
+        }
+
+        rng.shuffle_mut(keys);
+
+        // measure
+        let mut i = 0;
+        do bh.iter {
+            map.find(&(keys[i]));
+            i = (i + 1) % n;
+        }
+    }
+
+    pub fn find_seq_n<M:MutableMap<uint,uint>>(n: uint,
+                                               map: &mut M,
+                                               bh: &mut BenchHarness) {
+        // setup
+        for uint::range(0, n) |i| {
+            map.insert(i, 1);
+        }
+
+        // measure
+        let mut i = 0;
+        do bh.iter {
+            map.find(&i);
+            i = (i + 1) % n;
+        }
+     }
+}
\ No newline at end of file
diff --git a/src/libextra/crypto/sha1.rs b/src/libextra/crypto/sha1.rs
index 83cef9972d7..dbc65754266 100644
--- a/src/libextra/crypto/sha1.rs
+++ b/src/libextra/crypto/sha1.rs
@@ -367,3 +367,41 @@ mod tests {
         }
     }
 }
+
+#[cfg(test)]
+mod bench {
+
+    use sha1::Sha1;
+    use test::BenchHarness;
+
+    #[bench]
+    pub fn sha1_10(bh: & mut BenchHarness) {
+        let mut sh = Sha1::new();
+        let bytes = [1u8, ..10];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha1_1k(bh: & mut BenchHarness) {
+        let mut sh = Sha1::new();
+        let bytes = [1u8, ..1024];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha1_64k(bh: & mut BenchHarness) {
+        let mut sh = Sha1::new();
+        let bytes = [1u8, ..65536];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+}
diff --git a/src/libextra/crypto/sha2.rs b/src/libextra/crypto/sha2.rs
index 4b120c7b118..f21722e8d7a 100644
--- a/src/libextra/crypto/sha2.rs
+++ b/src/libextra/crypto/sha2.rs
@@ -1121,3 +1121,75 @@ mod tests {
         test_hash(sh, tests);
     }
 }
+
+
+
+#[cfg(test)]
+mod bench {
+
+    use sha2::{Sha256,Sha512};
+    use test::BenchHarness;
+
+    #[bench]
+    pub fn sha256_10(bh: & mut BenchHarness) {
+        let mut sh = Sha256::new();
+        let bytes = [1u8, ..10];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha256_1k(bh: & mut BenchHarness) {
+        let mut sh = Sha256::new();
+        let bytes = [1u8, ..1024];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha256_64k(bh: & mut BenchHarness) {
+        let mut sh = Sha256::new();
+        let bytes = [1u8, ..65536];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+
+
+    #[bench]
+    pub fn sha512_10(bh: & mut BenchHarness) {
+        let mut sh = Sha512::new();
+        let bytes = [1u8, ..10];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha512_1k(bh: & mut BenchHarness) {
+        let mut sh = Sha512::new();
+        let bytes = [1u8, ..1024];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+    #[bench]
+    pub fn sha512_64k(bh: & mut BenchHarness) {
+        let mut sh = Sha512::new();
+        let bytes = [1u8, ..65536];
+        do bh.iter {
+            sh.input(bytes);
+        }
+        bh.bytes = bytes.len() as u64;
+    }
+
+}
diff --git a/src/libextra/smallintmap.rs b/src/libextra/smallintmap.rs
index 6ff219a4f8f..23b3364eb7c 100644
--- a/src/libextra/smallintmap.rs
+++ b/src/libextra/smallintmap.rs
@@ -658,6 +658,66 @@ mod tests {
 }
 
 #[cfg(test)]
+mod bench {
+
+    use super::*;
+    use test::BenchHarness;
+    use container::bench::*;
+
+    // Find seq
+    #[bench]
+    pub fn insert_rand_100(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        insert_rand_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn insert_rand_10_000(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        insert_rand_n(10_000, &mut m, bh);
+    }
+
+    // Insert seq
+    #[bench]
+    pub fn insert_seq_100(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        insert_seq_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn insert_seq_10_000(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        insert_seq_n(10_000, &mut m, bh);
+    }
+
+    // Find rand
+    #[bench]
+    pub fn find_rand_100(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        find_rand_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn find_rand_10_000(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        find_rand_n(10_000, &mut m, bh);
+    }
+
+    // Find seq
+    #[bench]
+    pub fn find_seq_100(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        find_seq_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn find_seq_10_000(bh: &mut BenchHarness) {
+        let mut m : SmallIntMap<uint> = SmallIntMap::new();
+        find_seq_n(10_000, &mut m, bh);
+    }
+}
+
+#[cfg(test)]
 mod test_set {
 
     use super::SmallIntSet;
@@ -851,5 +911,4 @@ mod test_set {
             i + v2 == 4
         });
     }
-
 }
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
index 7e0cb76b515..f9b2c8429cf 100644
--- a/src/libextra/treemap.rs
+++ b/src/libextra/treemap.rs
@@ -1055,6 +1055,67 @@ mod test_treemap {
             assert_eq!(map.find(&k), Some(&v));
         }
     }
+
+}
+
+#[cfg(test)]
+mod bench {
+
+    use super::*;
+    use test::BenchHarness;
+    use container::bench::*;
+
+    // Find seq
+    #[bench]
+    pub fn insert_rand_100(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        insert_rand_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn insert_rand_10_000(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        insert_rand_n(10_000, &mut m, bh);
+    }
+
+    // Insert seq
+    #[bench]
+    pub fn insert_seq_100(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        insert_seq_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn insert_seq_10_000(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        insert_seq_n(10_000, &mut m, bh);
+    }
+
+    // Find rand
+    #[bench]
+    pub fn find_rand_100(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        find_rand_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn find_rand_10_000(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        find_rand_n(10_000, &mut m, bh);
+    }
+
+    // Find seq
+    #[bench]
+    pub fn find_seq_100(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        find_seq_n(100, &mut m, bh);
+    }
+
+    #[bench]
+    pub fn find_seq_10_000(bh: &mut BenchHarness) {
+        let mut m : TreeMap<uint,uint> = TreeMap::new();
+        find_seq_n(10_000, &mut m, bh);
+    }
 }
 
 #[cfg(test)]