Merge crate `collections` into `alloc`

9 files changed, 1633 insertions, 0 deletions

diff --git a/src/liballoc/benches/btree/map.rs b/src/liballoc/benches/btree/map.rs
new file mode 100644
index 00000000000..744afb991b0
--- /dev/null
+++ b/src/liballoc/benches/btree/map.rs
@@ -0,0 +1,157 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+
+use std::iter::Iterator;
+use std::vec::Vec;
+use std::collections::BTreeMap;
+use std::__rand::{Rng, thread_rng};
+use test::{Bencher, black_box};
+
+macro_rules! map_insert_rand_bench {
+    ($name: ident, $n: expr, $map: ident) => (
+        #[bench]
+        pub fn $name(b: &mut Bencher) {
+            let n: usize = $n;
+            let mut map = $map::new();
+            // setup
+            let mut rng = thread_rng();
+
+            for _ in 0..n {
+                let i = rng.gen::<usize>() % n;
+                map.insert(i, i);
+            }
+
+            // measure
+            b.iter(|| {
+                let k = rng.gen::<usize>() % n;
+                map.insert(k, k);
+                map.remove(&k);
+            });
+            black_box(map);
+        }
+    )
+}
+
+macro_rules! map_insert_seq_bench {
+    ($name: ident, $n: expr, $map: ident) => (
+        #[bench]
+        pub fn $name(b: &mut Bencher) {
+            let mut map = $map::new();
+            let n: usize = $n;
+            // setup
+            for i in 0..n {
+                map.insert(i * 2, i * 2);
+            }
+
+            // measure
+            let mut i = 1;
+            b.iter(|| {
+                map.insert(i, i);
+                map.remove(&i);
+                i = (i + 2) % n;
+            });
+            black_box(map);
+        }
+    )
+}
+
+macro_rules! map_find_rand_bench {
+    ($name: ident, $n: expr, $map: ident) => (
+        #[bench]
+        pub fn $name(b: &mut Bencher) {
+            let mut map = $map::new();
+            let n: usize = $n;
+
+            // setup
+            let mut rng = thread_rng();
+            let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
+
+            for &k in &keys {
+                map.insert(k, k);
+            }
+
+            rng.shuffle(&mut keys);
+
+            // measure
+            let mut i = 0;
+            b.iter(|| {
+                let t = map.get(&keys[i]);
+                i = (i + 1) % n;
+                black_box(t);
+            })
+        }
+    )
+}
+
+macro_rules! map_find_seq_bench {
+    ($name: ident, $n: expr, $map: ident) => (
+        #[bench]
+        pub fn $name(b: &mut Bencher) {
+            let mut map = $map::new();
+            let n: usize = $n;
+
+            // setup
+            for i in 0..n {
+                map.insert(i, i);
+            }
+
+            // measure
+            let mut i = 0;
+            b.iter(|| {
+                let x = map.get(&i);
+                i = (i + 1) % n;
+                black_box(x);
+            })
+        }
+    )
+}
+
+map_insert_rand_bench!{insert_rand_100,    100,    BTreeMap}
+map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
+
+map_insert_seq_bench!{insert_seq_100,    100,    BTreeMap}
+map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
+
+map_find_rand_bench!{find_rand_100,    100,    BTreeMap}
+map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
+
+map_find_seq_bench!{find_seq_100,    100,    BTreeMap}
+map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
+
+fn bench_iter(b: &mut Bencher, size: i32) {
+    let mut map = BTreeMap::<i32, i32>::new();
+    let mut rng = thread_rng();
+
+    for _ in 0..size {
+        map.insert(rng.gen(), rng.gen());
+    }
+
+    b.iter(|| {
+        for entry in &map {
+            black_box(entry);
+        }
+    });
+}
+
+#[bench]
+pub fn iter_20(b: &mut Bencher) {
+    bench_iter(b, 20);
+}
+
+#[bench]
+pub fn iter_1000(b: &mut Bencher) {
+    bench_iter(b, 1000);
+}
+
+#[bench]
+pub fn iter_100000(b: &mut Bencher) {
+    bench_iter(b, 100000);
+}
diff --git a/src/liballoc/benches/btree/mod.rs b/src/liballoc/benches/btree/mod.rs
new file mode 100644
index 00000000000..f436b0ac0c0
--- /dev/null
+++ b/src/liballoc/benches/btree/mod.rs
@@ -0,0 +1,11 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+mod map;
diff --git a/src/liballoc/benches/lib.rs b/src/liballoc/benches/lib.rs
new file mode 100644
index 00000000000..958020d0b0e
--- /dev/null
+++ b/src/liballoc/benches/lib.rs
@@ -0,0 +1,28 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![deny(warnings)]
+
+#![feature(i128_type)]
+#![feature(rand)]
+#![feature(repr_simd)]
+#![feature(slice_rotate)]
+#![feature(sort_unstable)]
+#![feature(test)]
+
+extern crate test;
+
+mod btree;
+mod linked_list;
+mod string;
+mod str;
+mod slice;
+mod vec;
+mod vec_deque;
diff --git a/src/liballoc/benches/linked_list.rs b/src/liballoc/benches/linked_list.rs
new file mode 100644
index 00000000000..bbac44553f1
--- /dev/null
+++ b/src/liballoc/benches/linked_list.rs
@@ -0,0 +1,87 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::LinkedList;
+use test::Bencher;
+
+#[bench]
+fn bench_collect_into(b: &mut Bencher) {
+    let v = &[0; 64];
+    b.iter(|| {
+        let _: LinkedList<_> = v.iter().cloned().collect();
+    })
+}
+
+#[bench]
+fn bench_push_front(b: &mut Bencher) {
+    let mut m: LinkedList<_> = LinkedList::new();
+    b.iter(|| {
+        m.push_front(0);
+    })
+}
+
+#[bench]
+fn bench_push_back(b: &mut Bencher) {
+    let mut m: LinkedList<_> = LinkedList::new();
+    b.iter(|| {
+        m.push_back(0);
+    })
+}
+
+#[bench]
+fn bench_push_back_pop_back(b: &mut Bencher) {
+    let mut m: LinkedList<_> = LinkedList::new();
+    b.iter(|| {
+        m.push_back(0);
+        m.pop_back();
+    })
+}
+
+#[bench]
+fn bench_push_front_pop_front(b: &mut Bencher) {
+    let mut m: LinkedList<_> = LinkedList::new();
+    b.iter(|| {
+        m.push_front(0);
+        m.pop_front();
+    })
+}
+
+#[bench]
+fn bench_iter(b: &mut Bencher) {
+    let v = &[0; 128];
+    let m: LinkedList<_> = v.iter().cloned().collect();
+    b.iter(|| {
+        assert!(m.iter().count() == 128);
+    })
+}
+#[bench]
+fn bench_iter_mut(b: &mut Bencher) {
+    let v = &[0; 128];
+    let mut m: LinkedList<_> = v.iter().cloned().collect();
+    b.iter(|| {
+        assert!(m.iter_mut().count() == 128);
+    })
+}
+#[bench]
+fn bench_iter_rev(b: &mut Bencher) {
+    let v = &[0; 128];
+    let m: LinkedList<_> = v.iter().cloned().collect();
+    b.iter(|| {
+        assert!(m.iter().rev().count() == 128);
+    })
+}
+#[bench]
+fn bench_iter_mut_rev(b: &mut Bencher) {
+    let v = &[0; 128];
+    let mut m: LinkedList<_> = v.iter().cloned().collect();
+    b.iter(|| {
+        assert!(m.iter_mut().rev().count() == 128);
+    })
+}
diff --git a/src/liballoc/benches/slice.rs b/src/liballoc/benches/slice.rs
new file mode 100644
index 00000000000..aa5a438b35e
--- /dev/null
+++ b/src/liballoc/benches/slice.rs
@@ -0,0 +1,358 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::{mem, ptr};
+use std::__rand::{Rng, thread_rng};
+
+use test::{Bencher, black_box};
+
+#[bench]
+fn iterator(b: &mut Bencher) {
+    // peculiar numbers to stop LLVM from optimising the summation
+    // out.
+    let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
+
+    b.iter(|| {
+        let mut sum = 0;
+        for x in &v {
+            sum += *x;
+        }
+        // sum == 11806, to stop dead code elimination.
+        if sum == 0 {
+            panic!()
+        }
+    })
+}
+
+#[bench]
+fn mut_iterator(b: &mut Bencher) {
+    let mut v = vec![0; 100];
+
+    b.iter(|| {
+        let mut i = 0;
+        for x in &mut v {
+            *x = i;
+            i += 1;
+        }
+    })
+}
+
+#[bench]
+fn concat(b: &mut Bencher) {
+    let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
+    b.iter(|| {
+        xss.concat();
+    });
+}
+
+#[bench]
+fn join(b: &mut Bencher) {
+    let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
+    b.iter(|| xss.join(&0));
+}
+
+#[bench]
+fn push(b: &mut Bencher) {
+    let mut vec = Vec::<i32>::new();
+    b.iter(|| {
+        vec.push(0);
+        black_box(&vec);
+    });
+}
+
+#[bench]
+fn starts_with_same_vector(b: &mut Bencher) {
+    let vec: Vec<_> = (0..100).collect();
+    b.iter(|| vec.starts_with(&vec))
+}
+
+#[bench]
+fn starts_with_single_element(b: &mut Bencher) {
+    let vec: Vec<_> = vec![0];
+    b.iter(|| vec.starts_with(&vec))
+}
+
+#[bench]
+fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
+    let vec: Vec<_> = (0..100).collect();
+    let mut match_vec: Vec<_> = (0..99).collect();
+    match_vec.push(0);
+    b.iter(|| vec.starts_with(&match_vec))
+}
+
+#[bench]
+fn ends_with_same_vector(b: &mut Bencher) {
+    let vec: Vec<_> = (0..100).collect();
+    b.iter(|| vec.ends_with(&vec))
+}
+
+#[bench]
+fn ends_with_single_element(b: &mut Bencher) {
+    let vec: Vec<_> = vec![0];
+    b.iter(|| vec.ends_with(&vec))
+}
+
+#[bench]
+fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
+    let vec: Vec<_> = (0..100).collect();
+    let mut match_vec: Vec<_> = (0..100).collect();
+    match_vec[0] = 200;
+    b.iter(|| vec.starts_with(&match_vec))
+}
+
+#[bench]
+fn contains_last_element(b: &mut Bencher) {
+    let vec: Vec<_> = (0..100).collect();
+    b.iter(|| vec.contains(&99))
+}
+
+#[bench]
+fn zero_1kb_from_elem(b: &mut Bencher) {
+    b.iter(|| vec![0u8; 1024]);
+}
+
+#[bench]
+fn zero_1kb_set_memory(b: &mut Bencher) {
+    b.iter(|| {
+        let mut v = Vec::<u8>::with_capacity(1024);
+        unsafe {
+            let vp = v.as_mut_ptr();
+            ptr::write_bytes(vp, 0, 1024);
+            v.set_len(1024);
+        }
+        v
+    });
+}
+
+#[bench]
+fn zero_1kb_loop_set(b: &mut Bencher) {
+    b.iter(|| {
+        let mut v = Vec::<u8>::with_capacity(1024);
+        unsafe {
+            v.set_len(1024);
+        }
+        for i in 0..1024 {
+            v[i] = 0;
+        }
+    });
+}
+
+#[bench]
+fn zero_1kb_mut_iter(b: &mut Bencher) {
+    b.iter(|| {
+        let mut v = Vec::<u8>::with_capacity(1024);
+        unsafe {
+            v.set_len(1024);
+        }
+        for x in &mut v {
+            *x = 0;
+        }
+        v
+    });
+}
+
+#[bench]
+fn random_inserts(b: &mut Bencher) {
+    let mut rng = thread_rng();
+    b.iter(|| {
+        let mut v = vec![(0, 0); 30];
+        for _ in 0..100 {
+            let l = v.len();
+            v.insert(rng.gen::<usize>() % (l + 1), (1, 1));
+        }
+    })
+}
+
+#[bench]
+fn random_removes(b: &mut Bencher) {
+    let mut rng = thread_rng();
+    b.iter(|| {
+        let mut v = vec![(0, 0); 130];
+        for _ in 0..100 {
+            let l = v.len();
+            v.remove(rng.gen::<usize>() % l);
+        }
+    })
+}
+
+fn gen_ascending(len: usize) -> Vec<u64> {
+    (0..len as u64).collect()
+}
+
+fn gen_descending(len: usize) -> Vec<u64> {
+    (0..len as u64).rev().collect()
+}
+
+fn gen_random(len: usize) -> Vec<u64> {
+    let mut rng = thread_rng();
+    rng.gen_iter::<u64>().take(len).collect()
+}
+
+fn gen_random_bytes(len: usize) -> Vec<u8> {
+    let mut rng = thread_rng();
+    rng.gen_iter::<u8>().take(len).collect()
+}
+
+fn gen_mostly_ascending(len: usize) -> Vec<u64> {
+    let mut rng = thread_rng();
+    let mut v = gen_ascending(len);
+    for _ in (0usize..).take_while(|x| x * x <= len) {
+        let x = rng.gen::<usize>() % len;
+        let y = rng.gen::<usize>() % len;
+        v.swap(x, y);
+    }
+    v
+}
+
+fn gen_mostly_descending(len: usize) -> Vec<u64> {
+    let mut rng = thread_rng();
+    let mut v = gen_descending(len);
+    for _ in (0usize..).take_while(|x| x * x <= len) {
+        let x = rng.gen::<usize>() % len;
+        let y = rng.gen::<usize>() % len;
+        v.swap(x, y);
+    }
+    v
+}
+
+fn gen_strings(len: usize) -> Vec<String> {
+    let mut rng = thread_rng();
+    let mut v = vec![];
+    for _ in 0..len {
+        let n = rng.gen::<usize>() % 20 + 1;
+        v.push(rng.gen_ascii_chars().take(n).collect());
+    }
+    v
+}
+
+fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
+    let mut rng = thread_rng();
+    rng.gen_iter().map(|x| [x; 16]).take(len).collect()
+}
+
+macro_rules! sort {
+    ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            b.iter(|| $gen($len).$f());
+            b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
+        }
+    }
+}
+
+macro_rules! sort_expensive {
+    ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            b.iter(|| {
+                let mut v = $gen($len);
+                let mut count = 0;
+                v.$f(|a: &u64, b: &u64| {
+                    count += 1;
+                    if count % 1_000_000_000 == 0 {
+                        panic!("should not happen");
+                    }
+                    (*a as f64).cos().partial_cmp(&(*b as f64).cos()).unwrap()
+                });
+                black_box(count);
+            });
+            b.bytes = $len as u64 * mem::size_of::<u64>() as u64;
+        }
+    }
+}
+
+sort!(sort, sort_small_ascending, gen_ascending, 10);
+sort!(sort, sort_small_descending, gen_descending, 10);
+sort!(sort, sort_small_random, gen_random, 10);
+sort!(sort, sort_small_big_random, gen_big_random, 10);
+sort!(sort, sort_medium_random, gen_random, 100);
+sort!(sort, sort_large_ascending, gen_ascending, 10000);
+sort!(sort, sort_large_descending, gen_descending, 10000);
+sort!(sort, sort_large_mostly_ascending, gen_mostly_ascending, 10000);
+sort!(sort, sort_large_mostly_descending, gen_mostly_descending, 10000);
+sort!(sort, sort_large_random, gen_random, 10000);
+sort!(sort, sort_large_big_random, gen_big_random, 10000);
+sort!(sort, sort_large_strings, gen_strings, 10000);
+sort_expensive!(sort_by, sort_large_random_expensive, gen_random, 10000);
+
+sort!(sort_unstable, sort_unstable_small_ascending, gen_ascending, 10);
+sort!(sort_unstable, sort_unstable_small_descending, gen_descending, 10);
+sort!(sort_unstable, sort_unstable_small_random, gen_random, 10);
+sort!(sort_unstable, sort_unstable_small_big_random, gen_big_random, 10);
+sort!(sort_unstable, sort_unstable_medium_random, gen_random, 100);
+sort!(sort_unstable, sort_unstable_large_ascending, gen_ascending, 10000);
+sort!(sort_unstable, sort_unstable_large_descending, gen_descending, 10000);
+sort!(sort_unstable, sort_unstable_large_mostly_ascending, gen_mostly_ascending, 10000);
+sort!(sort_unstable, sort_unstable_large_mostly_descending, gen_mostly_descending, 10000);
+sort!(sort_unstable, sort_unstable_large_random, gen_random, 10000);
+sort!(sort_unstable, sort_unstable_large_big_random, gen_big_random, 10000);
+sort!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
+sort_expensive!(sort_unstable_by, sort_unstable_large_random_expensive, gen_random, 10000);
+
+macro_rules! reverse {
+    ($name:ident, $ty:ty, $f:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            // odd length and offset by 1 to be as unaligned as possible
+            let n = 0xFFFFF;
+            let mut v: Vec<_> =
+                (0..1+(n / mem::size_of::<$ty>() as u64))
+                .map($f)
+                .collect();
+            b.iter(|| black_box(&mut v[1..]).reverse());
+            b.bytes = n;
+        }
+    }
+}
+
+reverse!(reverse_u8, u8, |x| x as u8);
+reverse!(reverse_u16, u16, |x| x as u16);
+reverse!(reverse_u8x3, [u8;3], |x| [x as u8, (x>>8) as u8, (x>>16) as u8]);
+reverse!(reverse_u32, u32, |x| x as u32);
+reverse!(reverse_u64, u64, |x| x as u64);
+reverse!(reverse_u128, u128, |x| x as u128);
+#[repr(simd)] struct F64x4(f64, f64, f64, f64);
+reverse!(reverse_simd_f64x4, F64x4, |x| { let x = x as f64; F64x4(x,x,x,x) });
+
+macro_rules! rotate {
+    ($name:ident, $gen:expr, $len:expr, $mid:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            let size = mem::size_of_val(&$gen(1)[0]);
+            let mut v = $gen($len * 8 / size);
+            b.iter(|| black_box(&mut v).rotate(($mid*8+size-1)/size));
+            b.bytes = (v.len() * size) as u64;
+        }
+    }
+}
+
+rotate!(rotate_tiny_by1, gen_random, 16, 1);
+rotate!(rotate_tiny_half, gen_random, 16, 16/2);
+rotate!(rotate_tiny_half_plus_one, gen_random, 16, 16/2+1);
+
+rotate!(rotate_medium_by1, gen_random, 9158, 1);
+rotate!(rotate_medium_by727_u64, gen_random, 9158, 727);
+rotate!(rotate_medium_by727_bytes, gen_random_bytes, 9158, 727);
+rotate!(rotate_medium_by727_strings, gen_strings, 9158, 727);
+rotate!(rotate_medium_half, gen_random, 9158, 9158/2);
+rotate!(rotate_medium_half_plus_one, gen_random, 9158, 9158/2+1);
+
+// Intended to use more RAM than the machine has cache
+rotate!(rotate_huge_by1, gen_random, 5*1024*1024, 1);
+rotate!(rotate_huge_by9199_u64, gen_random, 5*1024*1024, 9199);
+rotate!(rotate_huge_by9199_bytes, gen_random_bytes, 5*1024*1024, 9199);
+rotate!(rotate_huge_by9199_strings, gen_strings, 5*1024*1024, 9199);
+rotate!(rotate_huge_by9199_big, gen_big_random, 5*1024*1024, 9199);
+rotate!(rotate_huge_by1234577_u64, gen_random, 5*1024*1024, 1234577);
+rotate!(rotate_huge_by1234577_bytes, gen_random_bytes, 5*1024*1024, 1234577);
+rotate!(rotate_huge_by1234577_strings, gen_strings, 5*1024*1024, 1234577);
+rotate!(rotate_huge_by1234577_big, gen_big_random, 5*1024*1024, 1234577);
+rotate!(rotate_huge_half, gen_random, 5*1024*1024, 5*1024*1024/2);
+rotate!(rotate_huge_half_plus_one, gen_random, 5*1024*1024, 5*1024*1024/2+1);
diff --git a/src/liballoc/benches/str.rs b/src/liballoc/benches/str.rs
new file mode 100644
index 00000000000..fc4063fae92
--- /dev/null
+++ b/src/liballoc/benches/str.rs
@@ -0,0 +1,309 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use test::{Bencher, black_box};
+
+#[bench]
+fn char_iterator(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+
+    b.iter(|| s.chars().count());
+}
+
+#[bench]
+fn char_iterator_for(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+
+    b.iter(|| {
+        for ch in s.chars() { black_box(ch); }
+    });
+}
+
+#[bench]
+fn char_iterator_ascii(b: &mut Bencher) {
+    let s = "Mary had a little lamb, Little lamb
+    Mary had a little lamb, Little lamb
+    Mary had a little lamb, Little lamb
+    Mary had a little lamb, Little lamb
+    Mary had a little lamb, Little lamb
+    Mary had a little lamb, Little lamb";
+
+    b.iter(|| s.chars().count());
+}
+
+#[bench]
+fn char_iterator_rev(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+
+    b.iter(|| s.chars().rev().count());
+}
+
+#[bench]
+fn char_iterator_rev_for(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+
+    b.iter(|| {
+        for ch in s.chars().rev() { black_box(ch); }
+    });
+}
+
+#[bench]
+fn char_indicesator(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+    let len = s.chars().count();
+
+    b.iter(|| assert_eq!(s.char_indices().count(), len));
+}
+
+#[bench]
+fn char_indicesator_rev(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+    let len = s.chars().count();
+
+    b.iter(|| assert_eq!(s.char_indices().rev().count(), len));
+}
+
+#[bench]
+fn split_unicode_ascii(b: &mut Bencher) {
+    let s = "ประเทศไทย中华Việt Namประเทศไทย中华Việt Nam";
+
+    b.iter(|| assert_eq!(s.split('V').count(), 3));
+}
+
+#[bench]
+fn split_ascii(b: &mut Bencher) {
+    let s = "Mary had a little lamb, Little lamb, little-lamb.";
+    let len = s.split(' ').count();
+
+    b.iter(|| assert_eq!(s.split(' ').count(), len));
+}
+
+#[bench]
+fn split_extern_fn(b: &mut Bencher) {
+    let s = "Mary had a little lamb, Little lamb, little-lamb.";
+    let len = s.split(' ').count();
+    fn pred(c: char) -> bool { c == ' ' }
+
+    b.iter(|| assert_eq!(s.split(pred).count(), len));
+}
+
+#[bench]
+fn split_closure(b: &mut Bencher) {
+    let s = "Mary had a little lamb, Little lamb, little-lamb.";
+    let len = s.split(' ').count();
+
+    b.iter(|| assert_eq!(s.split(|c: char| c == ' ').count(), len));
+}
+
+#[bench]
+fn split_slice(b: &mut Bencher) {
+    let s = "Mary had a little lamb, Little lamb, little-lamb.";
+    let len = s.split(' ').count();
+
+    let c: &[char] = &[' '];
+    b.iter(|| assert_eq!(s.split(c).count(), len));
+}
+
+#[bench]
+fn bench_join(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+    let sep = "→";
+    let v = vec![s, s, s, s, s, s, s, s, s, s];
+    b.iter(|| {
+        assert_eq!(v.join(sep).len(), s.len() * 10 + sep.len() * 9);
+    })
+}
+
+#[bench]
+fn bench_contains_short_short(b: &mut Bencher) {
+    let haystack = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
+    let needle = "sit";
+
+    b.iter(|| {
+        assert!(haystack.contains(needle));
+    })
+}
+
+#[bench]
+fn bench_contains_short_long(b: &mut Bencher) {
+    let haystack = "\
+Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse quis lorem sit amet dolor \
+ultricies condimentum. Praesent iaculis purus elit, ac malesuada quam malesuada in. Duis sed orci \
+eros. Suspendisse sit amet magna mollis, mollis nunc luctus, imperdiet mi. Integer fringilla non \
+sem ut lacinia. Fusce varius tortor a risus porttitor hendrerit. Morbi mauris dui, ultricies nec \
+tempus vel, gravida nec quam.
+
+In est dui, tincidunt sed tempus interdum, adipiscing laoreet ante. Etiam tempor, tellus quis \
+sagittis interdum, nulla purus mattis sem, quis auctor erat odio ac tellus. In nec nunc sit amet \
+diam volutpat molestie at sed ipsum. Vestibulum laoreet consequat vulputate. Integer accumsan \
+lorem ac dignissim placerat. Suspendisse convallis faucibus lorem. Aliquam erat volutpat. In vel \
+eleifend felis. Sed suscipit nulla lorem, sed mollis est sollicitudin et. Nam fermentum egestas \
+interdum. Curabitur ut nisi justo.
+
+Sed sollicitudin ipsum tellus, ut condimentum leo eleifend nec. Cras ut velit ante. Phasellus nec \
+mollis odio. Mauris molestie erat in arcu mattis, at aliquet dolor vehicula. Quisque malesuada \
+lectus sit amet nisi pretium, a condimentum ipsum porta. Morbi at dapibus diam. Praesent egestas \
+est sed risus elementum, eu rutrum metus ultrices. Etiam fermentum consectetur magna, id rutrum \
+felis accumsan a. Aliquam ut pellentesque libero. Sed mi nulla, lobortis eu tortor id, suscipit \
+ultricies neque. Morbi iaculis sit amet risus at iaculis. Praesent eget ligula quis turpis \
+feugiat suscipit vel non arcu. Interdum et malesuada fames ac ante ipsum primis in faucibus. \
+Aliquam sit amet placerat lorem.
+
+Cras a lacus vel ante posuere elementum. Nunc est leo, bibendum ut facilisis vel, bibendum at \
+mauris. Nullam adipiscing diam vel odio ornare, luctus adipiscing mi luctus. Nulla facilisi. \
+Mauris adipiscing bibendum neque, quis adipiscing lectus tempus et. Sed feugiat erat et nisl \
+lobortis pharetra. Donec vitae erat enim. Nullam sit amet felis et quam lacinia tincidunt. Aliquam \
+suscipit dapibus urna. Sed volutpat urna in magna pulvinar volutpat. Phasellus nec tellus ac diam \
+cursus accumsan.
+
+Nam lectus enim, dapibus non nisi tempor, consectetur convallis massa. Maecenas eleifend dictum \
+feugiat. Etiam quis mauris vel risus luctus mattis a a nunc. Nullam orci quam, imperdiet id \
+vehicula in, porttitor ut nibh. Duis sagittis adipiscing nisl vitae congue. Donec mollis risus eu \
+leo suscipit, varius porttitor nulla porta. Pellentesque ut sem nec nisi euismod vehicula. Nulla \
+malesuada sollicitudin quam eu fermentum.";
+    let needle = "english";
+
+    b.iter(|| {
+        assert!(!haystack.contains(needle));
+    })
+}
+
+#[bench]
+fn bench_contains_bad_naive(b: &mut Bencher) {
+    let haystack = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
+    let needle = "aaaaaaaab";
+
+    b.iter(|| {
+        assert!(!haystack.contains(needle));
+    })
+}
+
+#[bench]
+fn bench_contains_equal(b: &mut Bencher) {
+    let haystack = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
+    let needle = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
+
+    b.iter(|| {
+        assert!(haystack.contains(needle));
+    })
+}
+
+
+macro_rules! make_test_inner {
+    ($s:ident, $code:expr, $name:ident, $str:expr, $iters:expr) => {
+        #[bench]
+        fn $name(bencher: &mut Bencher) {
+            let mut $s = $str;
+            black_box(&mut $s);
+            bencher.iter(|| for _ in 0..$iters { black_box($code); });
+        }
+    }
+}
+
+macro_rules! make_test {
+    ($name:ident, $s:ident, $code:expr) => {
+        make_test!($name, $s, $code, 1);
+    };
+    ($name:ident, $s:ident, $code:expr, $iters:expr) => {
+        mod $name {
+            use test::Bencher;
+            use test::black_box;
+
+            // Short strings: 65 bytes each
+            make_test_inner!($s, $code, short_ascii,
+                "Mary had a little lamb, Little lamb Mary had a littl lamb, lamb!", $iters);
+            make_test_inner!($s, $code, short_mixed,
+                "ศไทย中华Việt Nam; Mary had a little lamb, Little lam!", $iters);
+            make_test_inner!($s, $code, short_pile_of_poo,
+                "💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩!", $iters);
+            make_test_inner!($s, $code, long_lorem_ipsum,"\
+Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse quis lorem sit amet dolor \
+ultricies condimentum. Praesent iaculis purus elit, ac malesuada quam malesuada in. Duis sed orci \
+eros. Suspendisse sit amet magna mollis, mollis nunc luctus, imperdiet mi. Integer fringilla non \
+sem ut lacinia. Fusce varius tortor a risus porttitor hendrerit. Morbi mauris dui, ultricies nec \
+tempus vel, gravida nec quam.
+
+In est dui, tincidunt sed tempus interdum, adipiscing laoreet ante. Etiam tempor, tellus quis \
+sagittis interdum, nulla purus mattis sem, quis auctor erat odio ac tellus. In nec nunc sit amet \
+diam volutpat molestie at sed ipsum. Vestibulum laoreet consequat vulputate. Integer accumsan \
+lorem ac dignissim placerat. Suspendisse convallis faucibus lorem. Aliquam erat volutpat. In vel \
+eleifend felis. Sed suscipit nulla lorem, sed mollis est sollicitudin et. Nam fermentum egestas \
+interdum. Curabitur ut nisi justo.
+
+Sed sollicitudin ipsum tellus, ut condimentum leo eleifend nec. Cras ut velit ante. Phasellus nec \
+mollis odio. Mauris molestie erat in arcu mattis, at aliquet dolor vehicula. Quisque malesuada \
+lectus sit amet nisi pretium, a condimentum ipsum porta. Morbi at dapibus diam. Praesent egestas \
+est sed risus elementum, eu rutrum metus ultrices. Etiam fermentum consectetur magna, id rutrum \
+felis accumsan a. Aliquam ut pellentesque libero. Sed mi nulla, lobortis eu tortor id, suscipit \
+ultricies neque. Morbi iaculis sit amet risus at iaculis. Praesent eget ligula quis turpis \
+feugiat suscipit vel non arcu. Interdum et malesuada fames ac ante ipsum primis in faucibus. \
+Aliquam sit amet placerat lorem.
+
+Cras a lacus vel ante posuere elementum. Nunc est leo, bibendum ut facilisis vel, bibendum at \
+mauris. Nullam adipiscing diam vel odio ornare, luctus adipiscing mi luctus. Nulla facilisi. \
+Mauris adipiscing bibendum neque, quis adipiscing lectus tempus et. Sed feugiat erat et nisl \
+lobortis pharetra. Donec vitae erat enim. Nullam sit amet felis et quam lacinia tincidunt. Aliquam \
+suscipit dapibus urna. Sed volutpat urna in magna pulvinar volutpat. Phasellus nec tellus ac diam \
+cursus accumsan.
+
+Nam lectus enim, dapibus non nisi tempor, consectetur convallis massa. Maecenas eleifend dictum \
+feugiat. Etiam quis mauris vel risus luctus mattis a a nunc. Nullam orci quam, imperdiet id \
+vehicula in, porttitor ut nibh. Duis sagittis adipiscing nisl vitae congue. Donec mollis risus eu \
+leo suscipit, varius porttitor nulla porta. Pellentesque ut sem nec nisi euismod vehicula. Nulla \
+malesuada sollicitudin quam eu fermentum!", $iters);
+        }
+    }
+}
+
+make_test!(chars_count, s, s.chars().count());
+
+make_test!(contains_bang_str, s, s.contains("!"));
+make_test!(contains_bang_char, s, s.contains('!'));
+
+make_test!(match_indices_a_str, s, s.match_indices("a").count());
+
+make_test!(split_a_str, s, s.split("a").count());
+
+make_test!(trim_ascii_char, s, {
+    use std::ascii::AsciiExt;
+    s.trim_matches(|c: char| c.is_ascii())
+});
+make_test!(trim_left_ascii_char, s, {
+    use std::ascii::AsciiExt;
+    s.trim_left_matches(|c: char| c.is_ascii())
+});
+make_test!(trim_right_ascii_char, s, {
+    use std::ascii::AsciiExt;
+    s.trim_right_matches(|c: char| c.is_ascii())
+});
+
+make_test!(find_underscore_char, s, s.find('_'));
+make_test!(rfind_underscore_char, s, s.rfind('_'));
+make_test!(find_underscore_str, s, s.find("_"));
+
+make_test!(find_zzz_char, s, s.find('\u{1F4A4}'));
+make_test!(rfind_zzz_char, s, s.rfind('\u{1F4A4}'));
+make_test!(find_zzz_str, s, s.find("\u{1F4A4}"));
+
+make_test!(starts_with_ascii_char, s, s.starts_with('/'), 1024);
+make_test!(ends_with_ascii_char, s, s.ends_with('/'), 1024);
+make_test!(starts_with_unichar, s, s.starts_with('\u{1F4A4}'), 1024);
+make_test!(ends_with_unichar, s, s.ends_with('\u{1F4A4}'), 1024);
+make_test!(starts_with_str, s, s.starts_with("💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩"), 1024);
+make_test!(ends_with_str, s, s.ends_with("💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩"), 1024);
+
+make_test!(split_space_char, s, s.split(' ').count());
+make_test!(split_terminator_space_char, s, s.split_terminator(' ').count());
+
+make_test!(splitn_space_char, s, s.splitn(10, ' ').count());
+make_test!(rsplitn_space_char, s, s.rsplitn(10, ' ').count());
+
+make_test!(split_space_str, s, s.split(" ").count());
+make_test!(split_ad_str, s, s.split("ad").count());
diff --git a/src/liballoc/benches/string.rs b/src/liballoc/benches/string.rs
new file mode 100644
index 00000000000..36be21d978e
--- /dev/null
+++ b/src/liballoc/benches/string.rs
@@ -0,0 +1,134 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::iter::repeat;
+use test::Bencher;
+
+#[bench]
+fn bench_with_capacity(b: &mut Bencher) {
+    b.iter(|| String::with_capacity(100));
+}
+
+#[bench]
+fn bench_push_str(b: &mut Bencher) {
+    let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+    b.iter(|| {
+        let mut r = String::new();
+        r.push_str(s);
+    });
+}
+
+const REPETITIONS: u64 = 10_000;
+
+#[bench]
+fn bench_push_str_one_byte(b: &mut Bencher) {
+    b.bytes = REPETITIONS;
+    b.iter(|| {
+        let mut r = String::new();
+        for _ in 0..REPETITIONS {
+            r.push_str("a")
+        }
+    });
+}
+
+#[bench]
+fn bench_push_char_one_byte(b: &mut Bencher) {
+    b.bytes = REPETITIONS;
+    b.iter(|| {
+        let mut r = String::new();
+        for _ in 0..REPETITIONS {
+            r.push('a')
+        }
+    });
+}
+
+#[bench]
+fn bench_push_char_two_bytes(b: &mut Bencher) {
+    b.bytes = REPETITIONS * 2;
+    b.iter(|| {
+        let mut r = String::new();
+        for _ in 0..REPETITIONS {
+            r.push('â')
+        }
+    });
+}
+
+#[bench]
+fn from_utf8_lossy_100_ascii(b: &mut Bencher) {
+    let s = b"Hello there, the quick brown fox jumped over the lazy dog! \
+              Lorem ipsum dolor sit amet, consectetur. ";
+
+    assert_eq!(100, s.len());
+    b.iter(|| {
+        let _ = String::from_utf8_lossy(s);
+    });
+}
+
+#[bench]
+fn from_utf8_lossy_100_multibyte(b: &mut Bencher) {
+    let s = "𐌀𐌖𐌋𐌄𐌑𐌉ปรدولة الكويتทศไทย中华𐍅𐌿𐌻𐍆𐌹𐌻𐌰".as_bytes();
+    assert_eq!(100, s.len());
+    b.iter(|| {
+        let _ = String::from_utf8_lossy(s);
+    });
+}
+
+#[bench]
+fn from_utf8_lossy_invalid(b: &mut Bencher) {
+    let s = b"Hello\xC0\x80 There\xE6\x83 Goodbye";
+    b.iter(|| {
+        let _ = String::from_utf8_lossy(s);
+    });
+}
+
+#[bench]
+fn from_utf8_lossy_100_invalid(b: &mut Bencher) {
+    let s = repeat(0xf5).take(100).collect::<Vec<_>>();
+    b.iter(|| {
+        let _ = String::from_utf8_lossy(&s);
+    });
+}
+
+#[bench]
+fn bench_exact_size_shrink_to_fit(b: &mut Bencher) {
+    let s = "Hello there, the quick brown fox jumped over the lazy dog! \
+             Lorem ipsum dolor sit amet, consectetur. ";
+    // ensure our operation produces an exact-size string before we benchmark it
+    let mut r = String::with_capacity(s.len());
+    r.push_str(s);
+    assert_eq!(r.len(), r.capacity());
+    b.iter(|| {
+        let mut r = String::with_capacity(s.len());
+        r.push_str(s);
+        r.shrink_to_fit();
+        r
+    });
+}
+
+#[bench]
+fn bench_from_str(b: &mut Bencher) {
+    let s = "Hello there, the quick brown fox jumped over the lazy dog! \
+             Lorem ipsum dolor sit amet, consectetur. ";
+    b.iter(|| String::from(s))
+}
+
+#[bench]
+fn bench_from(b: &mut Bencher) {
+    let s = "Hello there, the quick brown fox jumped over the lazy dog! \
+             Lorem ipsum dolor sit amet, consectetur. ";
+    b.iter(|| String::from(s))
+}
+
+#[bench]
+fn bench_to_string(b: &mut Bencher) {
+    let s = "Hello there, the quick brown fox jumped over the lazy dog! \
+             Lorem ipsum dolor sit amet, consectetur. ";
+    b.iter(|| s.to_string())
+}
diff --git a/src/liballoc/benches/vec.rs b/src/liballoc/benches/vec.rs
new file mode 100644
index 00000000000..41490117068
--- /dev/null
+++ b/src/liballoc/benches/vec.rs
@@ -0,0 +1,492 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use test::Bencher;
+use std::iter::{FromIterator, repeat};
+
+#[bench]
+fn bench_new(b: &mut Bencher) {
+    b.iter(|| {
+        let v: Vec<u32> = Vec::new();
+        assert_eq!(v.len(), 0);
+        assert_eq!(v.capacity(), 0);
+    })
+}
+
+fn do_bench_with_capacity(b: &mut Bencher, src_len: usize) {
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let v: Vec<u32> = Vec::with_capacity(src_len);
+        assert_eq!(v.len(), 0);
+        assert_eq!(v.capacity(), src_len);
+    })
+}
+
+#[bench]
+fn bench_with_capacity_0000(b: &mut Bencher) {
+    do_bench_with_capacity(b, 0)
+}
+
+#[bench]
+fn bench_with_capacity_0010(b: &mut Bencher) {
+    do_bench_with_capacity(b, 10)
+}
+
+#[bench]
+fn bench_with_capacity_0100(b: &mut Bencher) {
+    do_bench_with_capacity(b, 100)
+}
+
+#[bench]
+fn bench_with_capacity_1000(b: &mut Bencher) {
+    do_bench_with_capacity(b, 1000)
+}
+
+fn do_bench_from_fn(b: &mut Bencher, src_len: usize) {
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let dst = (0..src_len).collect::<Vec<_>>();
+        assert_eq!(dst.len(), src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    })
+}
+
+#[bench]
+fn bench_from_fn_0000(b: &mut Bencher) {
+    do_bench_from_fn(b, 0)
+}
+
+#[bench]
+fn bench_from_fn_0010(b: &mut Bencher) {
+    do_bench_from_fn(b, 10)
+}
+
+#[bench]
+fn bench_from_fn_0100(b: &mut Bencher) {
+    do_bench_from_fn(b, 100)
+}
+
+#[bench]
+fn bench_from_fn_1000(b: &mut Bencher) {
+    do_bench_from_fn(b, 1000)
+}
+
+fn do_bench_from_elem(b: &mut Bencher, src_len: usize) {
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let dst: Vec<usize> = repeat(5).take(src_len).collect();
+        assert_eq!(dst.len(), src_len);
+        assert!(dst.iter().all(|x| *x == 5));
+    })
+}
+
+#[bench]
+fn bench_from_elem_0000(b: &mut Bencher) {
+    do_bench_from_elem(b, 0)
+}
+
+#[bench]
+fn bench_from_elem_0010(b: &mut Bencher) {
+    do_bench_from_elem(b, 10)
+}
+
+#[bench]
+fn bench_from_elem_0100(b: &mut Bencher) {
+    do_bench_from_elem(b, 100)
+}
+
+#[bench]
+fn bench_from_elem_1000(b: &mut Bencher) {
+    do_bench_from_elem(b, 1000)
+}
+
+fn do_bench_from_slice(b: &mut Bencher, src_len: usize) {
+    let src: Vec<_> = FromIterator::from_iter(0..src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let dst = src.clone()[..].to_vec();
+        assert_eq!(dst.len(), src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_from_slice_0000(b: &mut Bencher) {
+    do_bench_from_slice(b, 0)
+}
+
+#[bench]
+fn bench_from_slice_0010(b: &mut Bencher) {
+    do_bench_from_slice(b, 10)
+}
+
+#[bench]
+fn bench_from_slice_0100(b: &mut Bencher) {
+    do_bench_from_slice(b, 100)
+}
+
+#[bench]
+fn bench_from_slice_1000(b: &mut Bencher) {
+    do_bench_from_slice(b, 1000)
+}
+
+fn do_bench_from_iter(b: &mut Bencher, src_len: usize) {
+    let src: Vec<_> = FromIterator::from_iter(0..src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let dst: Vec<_> = FromIterator::from_iter(src.clone());
+        assert_eq!(dst.len(), src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_from_iter_0000(b: &mut Bencher) {
+    do_bench_from_iter(b, 0)
+}
+
+#[bench]
+fn bench_from_iter_0010(b: &mut Bencher) {
+    do_bench_from_iter(b, 10)
+}
+
+#[bench]
+fn bench_from_iter_0100(b: &mut Bencher) {
+    do_bench_from_iter(b, 100)
+}
+
+#[bench]
+fn bench_from_iter_1000(b: &mut Bencher) {
+    do_bench_from_iter(b, 1000)
+}
+
+fn do_bench_extend(b: &mut Bencher, dst_len: usize, src_len: usize) {
+    let dst: Vec<_> = FromIterator::from_iter(0..dst_len);
+    let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let mut dst = dst.clone();
+        dst.extend(src.clone());
+        assert_eq!(dst.len(), dst_len + src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_extend_0000_0000(b: &mut Bencher) {
+    do_bench_extend(b, 0, 0)
+}
+
+#[bench]
+fn bench_extend_0000_0010(b: &mut Bencher) {
+    do_bench_extend(b, 0, 10)
+}
+
+#[bench]
+fn bench_extend_0000_0100(b: &mut Bencher) {
+    do_bench_extend(b, 0, 100)
+}
+
+#[bench]
+fn bench_extend_0000_1000(b: &mut Bencher) {
+    do_bench_extend(b, 0, 1000)
+}
+
+#[bench]
+fn bench_extend_0010_0010(b: &mut Bencher) {
+    do_bench_extend(b, 10, 10)
+}
+
+#[bench]
+fn bench_extend_0100_0100(b: &mut Bencher) {
+    do_bench_extend(b, 100, 100)
+}
+
+#[bench]
+fn bench_extend_1000_1000(b: &mut Bencher) {
+    do_bench_extend(b, 1000, 1000)
+}
+
+fn do_bench_push_all(b: &mut Bencher, dst_len: usize, src_len: usize) {
+    let dst: Vec<_> = FromIterator::from_iter(0..dst_len);
+    let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let mut dst = dst.clone();
+        dst.extend_from_slice(&src);
+        assert_eq!(dst.len(), dst_len + src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_push_all_0000_0000(b: &mut Bencher) {
+    do_bench_push_all(b, 0, 0)
+}
+
+#[bench]
+fn bench_push_all_0000_0010(b: &mut Bencher) {
+    do_bench_push_all(b, 0, 10)
+}
+
+#[bench]
+fn bench_push_all_0000_0100(b: &mut Bencher) {
+    do_bench_push_all(b, 0, 100)
+}
+
+#[bench]
+fn bench_push_all_0000_1000(b: &mut Bencher) {
+    do_bench_push_all(b, 0, 1000)
+}
+
+#[bench]
+fn bench_push_all_0010_0010(b: &mut Bencher) {
+    do_bench_push_all(b, 10, 10)
+}
+
+#[bench]
+fn bench_push_all_0100_0100(b: &mut Bencher) {
+    do_bench_push_all(b, 100, 100)
+}
+
+#[bench]
+fn bench_push_all_1000_1000(b: &mut Bencher) {
+    do_bench_push_all(b, 1000, 1000)
+}
+
+fn do_bench_push_all_move(b: &mut Bencher, dst_len: usize, src_len: usize) {
+    let dst: Vec<_> = FromIterator::from_iter(0..dst_len);
+    let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let mut dst = dst.clone();
+        dst.extend(src.clone());
+        assert_eq!(dst.len(), dst_len + src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_push_all_move_0000_0000(b: &mut Bencher) {
+    do_bench_push_all_move(b, 0, 0)
+}
+
+#[bench]
+fn bench_push_all_move_0000_0010(b: &mut Bencher) {
+    do_bench_push_all_move(b, 0, 10)
+}
+
+#[bench]
+fn bench_push_all_move_0000_0100(b: &mut Bencher) {
+    do_bench_push_all_move(b, 0, 100)
+}
+
+#[bench]
+fn bench_push_all_move_0000_1000(b: &mut Bencher) {
+    do_bench_push_all_move(b, 0, 1000)
+}
+
+#[bench]
+fn bench_push_all_move_0010_0010(b: &mut Bencher) {
+    do_bench_push_all_move(b, 10, 10)
+}
+
+#[bench]
+fn bench_push_all_move_0100_0100(b: &mut Bencher) {
+    do_bench_push_all_move(b, 100, 100)
+}
+
+#[bench]
+fn bench_push_all_move_1000_1000(b: &mut Bencher) {
+    do_bench_push_all_move(b, 1000, 1000)
+}
+
+fn do_bench_clone(b: &mut Bencher, src_len: usize) {
+    let src: Vec<usize> = FromIterator::from_iter(0..src_len);
+
+    b.bytes = src_len as u64;
+
+    b.iter(|| {
+        let dst = src.clone();
+        assert_eq!(dst.len(), src_len);
+        assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
+    });
+}
+
+#[bench]
+fn bench_clone_0000(b: &mut Bencher) {
+    do_bench_clone(b, 0)
+}
+
+#[bench]
+fn bench_clone_0010(b: &mut Bencher) {
+    do_bench_clone(b, 10)
+}
+
+#[bench]
+fn bench_clone_0100(b: &mut Bencher) {
+    do_bench_clone(b, 100)
+}
+
+#[bench]
+fn bench_clone_1000(b: &mut Bencher) {
+    do_bench_clone(b, 1000)
+}
+
+fn do_bench_clone_from(b: &mut Bencher, times: usize, dst_len: usize, src_len: usize) {
+    let dst: Vec<_> = FromIterator::from_iter(0..src_len);
+    let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
+
+    b.bytes = (times * src_len) as u64;
+
+    b.iter(|| {
+        let mut dst = dst.clone();
+
+        for _ in 0..times {
+            dst.clone_from(&src);
+
+            assert_eq!(dst.len(), src_len);
+            assert!(dst.iter().enumerate().all(|(i, x)| dst_len + i == *x));
+        }
+    });
+}
+
+#[bench]
+fn bench_clone_from_01_0000_0000(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 0, 0)
+}
+
+#[bench]
+fn bench_clone_from_01_0000_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 0, 10)
+}
+
+#[bench]
+fn bench_clone_from_01_0000_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 0, 100)
+}
+
+#[bench]
+fn bench_clone_from_01_0000_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 0, 1000)
+}
+
+#[bench]
+fn bench_clone_from_01_0010_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 10, 10)
+}
+
+#[bench]
+fn bench_clone_from_01_0100_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 100, 100)
+}
+
+#[bench]
+fn bench_clone_from_01_1000_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 1000, 1000)
+}
+
+#[bench]
+fn bench_clone_from_01_0010_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 10, 100)
+}
+
+#[bench]
+fn bench_clone_from_01_0100_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 100, 1000)
+}
+
+#[bench]
+fn bench_clone_from_01_0010_0000(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 10, 0)
+}
+
+#[bench]
+fn bench_clone_from_01_0100_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 100, 10)
+}
+
+#[bench]
+fn bench_clone_from_01_1000_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 1, 1000, 100)
+}
+
+#[bench]
+fn bench_clone_from_10_0000_0000(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 0, 0)
+}
+
+#[bench]
+fn bench_clone_from_10_0000_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 0, 10)
+}
+
+#[bench]
+fn bench_clone_from_10_0000_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 0, 100)
+}
+
+#[bench]
+fn bench_clone_from_10_0000_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 0, 1000)
+}
+
+#[bench]
+fn bench_clone_from_10_0010_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 10, 10)
+}
+
+#[bench]
+fn bench_clone_from_10_0100_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 100, 100)
+}
+
+#[bench]
+fn bench_clone_from_10_1000_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 1000, 1000)
+}
+
+#[bench]
+fn bench_clone_from_10_0010_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 10, 100)
+}
+
+#[bench]
+fn bench_clone_from_10_0100_1000(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 100, 1000)
+}
+
+#[bench]
+fn bench_clone_from_10_0010_0000(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 10, 0)
+}
+
+#[bench]
+fn bench_clone_from_10_0100_0010(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 100, 10)
+}
+
+#[bench]
+fn bench_clone_from_10_1000_0100(b: &mut Bencher) {
+    do_bench_clone_from(b, 10, 1000, 100)
+}
diff --git a/src/liballoc/benches/vec_deque.rs b/src/liballoc/benches/vec_deque.rs
new file mode 100644
index 00000000000..380645e7cd0
--- /dev/null
+++ b/src/liballoc/benches/vec_deque.rs
@@ -0,0 +1,57 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::VecDeque;
+use test::{Bencher, black_box};
+
+#[bench]
+fn bench_new(b: &mut Bencher) {
+    b.iter(|| {
+        let ring: VecDeque<i32> = VecDeque::new();
+        black_box(ring);
+    })
+}
+
+#[bench]
+fn bench_grow_1025(b: &mut Bencher) {
+    b.iter(|| {
+        let mut deq = VecDeque::new();
+        for i in 0..1025 {
+            deq.push_front(i);
+        }
+        black_box(deq);
+    })
+}
+
+#[bench]
+fn bench_iter_1000(b: &mut Bencher) {
+    let ring: VecDeque<_> = (0..1000).collect();
+
+    b.iter(|| {
+        let mut sum = 0;
+        for &i in &ring {
+            sum += i;
+        }
+        black_box(sum);
+    })
+}
+
+#[bench]
+fn bench_mut_iter_1000(b: &mut Bencher) {
+    let mut ring: VecDeque<_> = (0..1000).collect();
+
+    b.iter(|| {
+        let mut sum = 0;
+        for i in &mut ring {
+            sum += *i;
+        }
+        black_box(sum);
+    })
+}