summaryrefslogtreecommitdiffstats
path: root/library/alloc/benches
diff options
context:
space:
mode:
Diffstat (limited to 'library/alloc/benches')
-rw-r--r--library/alloc/benches/binary_heap.rs91
-rw-r--r--library/alloc/benches/btree/map.rs585
-rw-r--r--library/alloc/benches/btree/mod.rs2
-rw-r--r--library/alloc/benches/btree/set.rs224
-rw-r--r--library/alloc/benches/lib.rs28
-rw-r--r--library/alloc/benches/linked_list.rs77
-rw-r--r--library/alloc/benches/slice.rs379
-rw-r--r--library/alloc/benches/str.rs299
-rw-r--r--library/alloc/benches/string.rs164
-rw-r--r--library/alloc/benches/vec.rs784
-rw-r--r--library/alloc/benches/vec_deque.rs125
-rw-r--r--library/alloc/benches/vec_deque_append.rs34
12 files changed, 2792 insertions, 0 deletions
diff --git a/library/alloc/benches/binary_heap.rs b/library/alloc/benches/binary_heap.rs
new file mode 100644
index 000000000..917e71f25
--- /dev/null
+++ b/library/alloc/benches/binary_heap.rs
@@ -0,0 +1,91 @@
+use std::collections::BinaryHeap;
+
+use rand::seq::SliceRandom;
+use test::{black_box, Bencher};
+
+#[bench]
+fn bench_find_smallest_1000(b: &mut Bencher) {
+ let mut rng = crate::bench_rng();
+ let mut vec: Vec<u32> = (0..100_000).collect();
+ vec.shuffle(&mut rng);
+
+ b.iter(|| {
+ let mut iter = vec.iter().copied();
+ let mut heap: BinaryHeap<_> = iter.by_ref().take(1000).collect();
+
+ for x in iter {
+ let mut max = heap.peek_mut().unwrap();
+ // This comparison should be true only 1% of the time.
+ // Unnecessary `sift_down`s will degrade performance
+ if x < *max {
+ *max = x;
+ }
+ }
+
+ heap
+ })
+}
+
+#[bench]
+fn bench_peek_mut_deref_mut(b: &mut Bencher) {
+ let mut bheap = BinaryHeap::from(vec![42]);
+ let vec: Vec<u32> = (0..1_000_000).collect();
+
+ b.iter(|| {
+ let vec = black_box(&vec);
+ let mut peek_mut = bheap.peek_mut().unwrap();
+ // The compiler shouldn't be able to optimize away the `sift_down`
+ // assignment in `PeekMut`'s `DerefMut` implementation since
+ // the loop might not run.
+ for &i in vec.iter() {
+ *peek_mut = i;
+ }
+ // Remove the already minimal overhead of the sift_down
+ std::mem::forget(peek_mut);
+ })
+}
+
+#[bench]
+fn bench_from_vec(b: &mut Bencher) {
+ let mut rng = crate::bench_rng();
+ let mut vec: Vec<u32> = (0..100_000).collect();
+ vec.shuffle(&mut rng);
+
+ b.iter(|| BinaryHeap::from(vec.clone()))
+}
+
+#[bench]
+fn bench_into_sorted_vec(b: &mut Bencher) {
+ let bheap: BinaryHeap<i32> = (0..10_000).collect();
+
+ b.iter(|| bheap.clone().into_sorted_vec())
+}
+
+#[bench]
+fn bench_push(b: &mut Bencher) {
+ let mut bheap = BinaryHeap::with_capacity(50_000);
+ let mut rng = crate::bench_rng();
+ let mut vec: Vec<u32> = (0..50_000).collect();
+ vec.shuffle(&mut rng);
+
+ b.iter(|| {
+ for &i in vec.iter() {
+ bheap.push(i);
+ }
+ black_box(&mut bheap);
+ bheap.clear();
+ })
+}
+
+#[bench]
+fn bench_pop(b: &mut Bencher) {
+ let mut bheap = BinaryHeap::with_capacity(10_000);
+
+ b.iter(|| {
+ bheap.extend((0..10_000).rev());
+ black_box(&mut bheap);
+ while let Some(elem) = bheap.pop() {
+ black_box(elem);
+ }
+ })
+}
diff --git a/library/alloc/benches/btree/map.rs b/library/alloc/benches/btree/map.rs
new file mode 100644
index 000000000..1f6b87fb0
--- /dev/null
+++ b/library/alloc/benches/btree/map.rs
@@ -0,0 +1,585 @@
+use std::collections::BTreeMap;
+use std::iter::Iterator;
+use std::ops::RangeBounds;
+use std::vec::Vec;
+
+use rand::{seq::SliceRandom, Rng};
+use test::{black_box, Bencher};
+
+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 = crate::bench_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_from_iter_rand_bench {
+ ($name: ident, $n: expr, $map: ident) => {
+ #[bench]
+ pub fn $name(b: &mut Bencher) {
+ let n: usize = $n;
+ // setup
+ let mut rng = crate::bench_rng();
+ let mut vec = Vec::with_capacity(n);
+
+ for _ in 0..n {
+ let i = rng.gen::<usize>() % n;
+ vec.push((i, i));
+ }
+
+ // measure
+ b.iter(|| {
+ let map: $map<_, _> = vec.iter().copied().collect();
+ black_box(map);
+ });
+ }
+ };
+}
+
+macro_rules! map_from_iter_seq_bench {
+ ($name: ident, $n: expr, $map: ident) => {
+ #[bench]
+ pub fn $name(b: &mut Bencher) {
+ let n: usize = $n;
+ // setup
+ let mut vec = Vec::with_capacity(n);
+
+ for i in 0..n {
+ vec.push((i, i));
+ }
+
+ // measure
+ b.iter(|| {
+ let map: $map<_, _> = vec.iter().copied().collect();
+ 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 = crate::bench_rng();
+ let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
+
+ for &k in &keys {
+ map.insert(k, k);
+ }
+
+ keys.shuffle(&mut rng);
+
+ // 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_from_iter_rand_bench! {from_iter_rand_100, 100, BTreeMap}
+map_from_iter_rand_bench! {from_iter_rand_10_000, 10_000, BTreeMap}
+
+map_from_iter_seq_bench! {from_iter_seq_100, 100, BTreeMap}
+map_from_iter_seq_bench! {from_iter_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_iteration(b: &mut Bencher, size: i32) {
+ let mut map = BTreeMap::<i32, i32>::new();
+ let mut rng = crate::bench_rng();
+
+ for _ in 0..size {
+ map.insert(rng.gen(), rng.gen());
+ }
+
+ b.iter(|| {
+ for entry in &map {
+ black_box(entry);
+ }
+ });
+}
+
+#[bench]
+pub fn iteration_20(b: &mut Bencher) {
+ bench_iteration(b, 20);
+}
+
+#[bench]
+pub fn iteration_1000(b: &mut Bencher) {
+ bench_iteration(b, 1000);
+}
+
+#[bench]
+pub fn iteration_100000(b: &mut Bencher) {
+ bench_iteration(b, 100000);
+}
+
+fn bench_iteration_mut(b: &mut Bencher, size: i32) {
+ let mut map = BTreeMap::<i32, i32>::new();
+ let mut rng = crate::bench_rng();
+
+ for _ in 0..size {
+ map.insert(rng.gen(), rng.gen());
+ }
+
+ b.iter(|| {
+ for kv in map.iter_mut() {
+ black_box(kv);
+ }
+ });
+}
+
+#[bench]
+pub fn iteration_mut_20(b: &mut Bencher) {
+ bench_iteration_mut(b, 20);
+}
+
+#[bench]
+pub fn iteration_mut_1000(b: &mut Bencher) {
+ bench_iteration_mut(b, 1000);
+}
+
+#[bench]
+pub fn iteration_mut_100000(b: &mut Bencher) {
+ bench_iteration_mut(b, 100000);
+}
+
+fn bench_first_and_last_nightly(b: &mut Bencher, size: i32) {
+ let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+ b.iter(|| {
+ for _ in 0..10 {
+ black_box(map.first_key_value());
+ black_box(map.last_key_value());
+ }
+ });
+}
+
+fn bench_first_and_last_stable(b: &mut Bencher, size: i32) {
+ let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+ b.iter(|| {
+ for _ in 0..10 {
+ black_box(map.iter().next());
+ black_box(map.iter().next_back());
+ }
+ });
+}
+
+#[bench]
+pub fn first_and_last_0_nightly(b: &mut Bencher) {
+ bench_first_and_last_nightly(b, 0);
+}
+
+#[bench]
+pub fn first_and_last_0_stable(b: &mut Bencher) {
+ bench_first_and_last_stable(b, 0);
+}
+
+#[bench]
+pub fn first_and_last_100_nightly(b: &mut Bencher) {
+ bench_first_and_last_nightly(b, 100);
+}
+
+#[bench]
+pub fn first_and_last_100_stable(b: &mut Bencher) {
+ bench_first_and_last_stable(b, 100);
+}
+
+#[bench]
+pub fn first_and_last_10k_nightly(b: &mut Bencher) {
+ bench_first_and_last_nightly(b, 10_000);
+}
+
+#[bench]
+pub fn first_and_last_10k_stable(b: &mut Bencher) {
+ bench_first_and_last_stable(b, 10_000);
+}
+
+const BENCH_RANGE_SIZE: i32 = 145;
+const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2;
+
+fn bench_range<F, R>(b: &mut Bencher, f: F)
+where
+ F: Fn(i32, i32) -> R,
+ R: RangeBounds<i32>,
+{
+ let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
+ b.iter(|| {
+ let mut c = 0;
+ for i in 0..BENCH_RANGE_SIZE {
+ for j in i + 1..BENCH_RANGE_SIZE {
+ let _ = black_box(map.range(f(i, j)));
+ c += 1;
+ }
+ }
+ debug_assert_eq!(c, BENCH_RANGE_COUNT);
+ });
+}
+
+#[bench]
+pub fn range_included_excluded(b: &mut Bencher) {
+ bench_range(b, |i, j| i..j);
+}
+
+#[bench]
+pub fn range_included_included(b: &mut Bencher) {
+ bench_range(b, |i, j| i..=j);
+}
+
+#[bench]
+pub fn range_included_unbounded(b: &mut Bencher) {
+ bench_range(b, |i, _| i..);
+}
+
+#[bench]
+pub fn range_unbounded_unbounded(b: &mut Bencher) {
+ bench_range(b, |_, _| ..);
+}
+
+fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) {
+ let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+ b.iter(|| {
+ for _ in 0..repeats {
+ let _ = black_box(map.iter());
+ }
+ });
+}
+
+/// Contrast range_unbounded_unbounded with `iter()`.
+#[bench]
+pub fn range_unbounded_vs_iter(b: &mut Bencher) {
+ bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE);
+}
+
+#[bench]
+pub fn iter_0(b: &mut Bencher) {
+ bench_iter(b, 1_000, 0);
+}
+
+#[bench]
+pub fn iter_1(b: &mut Bencher) {
+ bench_iter(b, 1_000, 1);
+}
+
+#[bench]
+pub fn iter_100(b: &mut Bencher) {
+ bench_iter(b, 1_000, 100);
+}
+
+#[bench]
+pub fn iter_10k(b: &mut Bencher) {
+ bench_iter(b, 1_000, 10_000);
+}
+
+#[bench]
+pub fn iter_1m(b: &mut Bencher) {
+ bench_iter(b, 1_000, 1_000_000);
+}
+
+const FAT: usize = 256;
+
+// The returned map has small keys and values.
+// Benchmarks on it have a counterpart in set.rs with the same keys and no values at all.
+fn slim_map(n: usize) -> BTreeMap<usize, usize> {
+ (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
+}
+
+// The returned map has small keys and large values.
+fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> {
+ (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
+}
+
+#[bench]
+pub fn clone_slim_100(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_100_and_clear(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+ assert_eq!(map.len(), 100 / 2);
+ })
+}
+
+#[bench]
+pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ while map.pop_first().is_some() {}
+ map
+ });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+ let v = map.remove(&elt);
+ debug_assert!(v.is_some());
+ }
+ map
+ });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
+ let src = slim_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ for i in (0..100).step_by(2) {
+ let v = map.remove(&i);
+ debug_assert!(v.is_some());
+ }
+ assert_eq!(map.len(), 100 / 2);
+ map
+ })
+}
+
+#[bench]
+pub fn clone_slim_10k(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| {
+ let mut map = src.clone();
+ assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
+ assert_eq!(map.len(), 10_000 / 2);
+ })
+}
+
+#[bench]
+pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| {
+ let mut map = src.clone();
+ while map.pop_first().is_some() {}
+ map
+ });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| {
+ let mut map = src.clone();
+ while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+ let v = map.remove(&elt);
+ debug_assert!(v.is_some());
+ }
+ map
+ });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
+ let src = slim_map(10_000);
+ b.iter(|| {
+ let mut map = src.clone();
+ for i in (0..10_000).step_by(2) {
+ let v = map.remove(&i);
+ debug_assert!(v.is_some());
+ }
+ assert_eq!(map.len(), 10_000 / 2);
+ map
+ })
+}
+
+#[bench]
+pub fn clone_fat_val_100(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+ assert_eq!(map.len(), 100 / 2);
+ })
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ while map.pop_first().is_some() {}
+ map
+ });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+ let v = map.remove(&elt);
+ debug_assert!(v.is_some());
+ }
+ map
+ });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
+ let src = fat_val_map(100);
+ b.iter(|| {
+ let mut map = src.clone();
+ for i in (0..100).step_by(2) {
+ let v = map.remove(&i);
+ debug_assert!(v.is_some());
+ }
+ assert_eq!(map.len(), 100 / 2);
+ map
+ })
+}
diff --git a/library/alloc/benches/btree/mod.rs b/library/alloc/benches/btree/mod.rs
new file mode 100644
index 000000000..095ca5dd2
--- /dev/null
+++ b/library/alloc/benches/btree/mod.rs
@@ -0,0 +1,2 @@
+mod map;
+mod set;
diff --git a/library/alloc/benches/btree/set.rs b/library/alloc/benches/btree/set.rs
new file mode 100644
index 000000000..3f4b0e0f1
--- /dev/null
+++ b/library/alloc/benches/btree/set.rs
@@ -0,0 +1,224 @@
+use std::collections::BTreeSet;
+
+use rand::Rng;
+use test::Bencher;
+
+fn random(n: usize) -> BTreeSet<usize> {
+ let mut rng = crate::bench_rng();
+ let mut set = BTreeSet::new();
+ while set.len() < n {
+ set.insert(rng.gen());
+ }
+ assert_eq!(set.len(), n);
+ set
+}
+
+fn neg(n: usize) -> BTreeSet<i32> {
+ let set: BTreeSet<i32> = (-(n as i32)..=-1).collect();
+ assert_eq!(set.len(), n);
+ set
+}
+
+fn pos(n: usize) -> BTreeSet<i32> {
+ let set: BTreeSet<i32> = (1..=(n as i32)).collect();
+ assert_eq!(set.len(), n);
+ set
+}
+
+fn stagger(n1: usize, factor: usize) -> [BTreeSet<u32>; 2] {
+ let n2 = n1 * factor;
+ let mut sets = [BTreeSet::new(), BTreeSet::new()];
+ for i in 0..(n1 + n2) {
+ let b = i % (factor + 1) != 0;
+ sets[b as usize].insert(i as u32);
+ }
+ assert_eq!(sets[0].len(), n1);
+ assert_eq!(sets[1].len(), n2);
+ sets
+}
+
+macro_rules! set_bench {
+ ($name: ident, $set_func: ident, $result_func: ident, $sets: expr) => {
+ #[bench]
+ pub fn $name(b: &mut Bencher) {
+ // setup
+ let sets = $sets;
+
+ // measure
+ b.iter(|| sets[0].$set_func(&sets[1]).$result_func())
+ }
+ };
+}
+
+fn slim_set(n: usize) -> BTreeSet<usize> {
+ (0..n).collect::<BTreeSet<_>>()
+}
+
+#[bench]
+pub fn clone_100(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_100_and_clear(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_100_and_drain_all(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| src.clone().drain_filter(|_| true).count())
+}
+
+#[bench]
+pub fn clone_100_and_drain_half(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| {
+ let mut set = src.clone();
+ assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 100 / 2);
+ assert_eq!(set.len(), 100 / 2);
+ })
+}
+
+#[bench]
+pub fn clone_100_and_into_iter(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_100_and_pop_all(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| {
+ let mut set = src.clone();
+ while set.pop_first().is_some() {}
+ set
+ });
+}
+
+#[bench]
+pub fn clone_100_and_remove_all(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| {
+ let mut set = src.clone();
+ while let Some(elt) = set.iter().copied().next() {
+ let ok = set.remove(&elt);
+ debug_assert!(ok);
+ }
+ set
+ });
+}
+
+#[bench]
+pub fn clone_100_and_remove_half(b: &mut Bencher) {
+ let src = slim_set(100);
+ b.iter(|| {
+ let mut set = src.clone();
+ for i in (0..100).step_by(2) {
+ let ok = set.remove(&i);
+ debug_assert!(ok);
+ }
+ assert_eq!(set.len(), 100 / 2);
+ set
+ })
+}
+
+#[bench]
+pub fn clone_10k(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_10k_and_clear(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_10k_and_drain_all(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| src.clone().drain_filter(|_| true).count())
+}
+
+#[bench]
+pub fn clone_10k_and_drain_half(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| {
+ let mut set = src.clone();
+ assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 10_000 / 2);
+ assert_eq!(set.len(), 10_000 / 2);
+ })
+}
+
+#[bench]
+pub fn clone_10k_and_into_iter(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_10k_and_pop_all(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| {
+ let mut set = src.clone();
+ while set.pop_first().is_some() {}
+ set
+ });
+}
+
+#[bench]
+pub fn clone_10k_and_remove_all(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| {
+ let mut set = src.clone();
+ while let Some(elt) = set.iter().copied().next() {
+ let ok = set.remove(&elt);
+ debug_assert!(ok);
+ }
+ set
+ });
+}
+
+#[bench]
+pub fn clone_10k_and_remove_half(b: &mut Bencher) {
+ let src = slim_set(10_000);
+ b.iter(|| {
+ let mut set = src.clone();
+ for i in (0..10_000).step_by(2) {
+ let ok = set.remove(&i);
+ debug_assert!(ok);
+ }
+ assert_eq!(set.len(), 10_000 / 2);
+ set
+ })
+}
+
+set_bench! {intersection_100_neg_vs_100_pos, intersection, count, [neg(100), pos(100)]}
+set_bench! {intersection_100_neg_vs_10k_pos, intersection, count, [neg(100), pos(10_000)]}
+set_bench! {intersection_100_pos_vs_100_neg, intersection, count, [pos(100), neg(100)]}
+set_bench! {intersection_100_pos_vs_10k_neg, intersection, count, [pos(100), neg(10_000)]}
+set_bench! {intersection_10k_neg_vs_100_pos, intersection, count, [neg(10_000), pos(100)]}
+set_bench! {intersection_10k_neg_vs_10k_pos, intersection, count, [neg(10_000), pos(10_000)]}
+set_bench! {intersection_10k_pos_vs_100_neg, intersection, count, [pos(10_000), neg(100)]}
+set_bench! {intersection_10k_pos_vs_10k_neg, intersection, count, [pos(10_000), neg(10_000)]}
+set_bench! {intersection_random_100_vs_100, intersection, count, [random(100), random(100)]}
+set_bench! {intersection_random_100_vs_10k, intersection, count, [random(100), random(10_000)]}
+set_bench! {intersection_random_10k_vs_100, intersection, count, [random(10_000), random(100)]}
+set_bench! {intersection_random_10k_vs_10k, intersection, count, [random(10_000), random(10_000)]}
+set_bench! {intersection_staggered_100_vs_100, intersection, count, stagger(100, 1)}
+set_bench! {intersection_staggered_10k_vs_10k, intersection, count, stagger(10_000, 1)}
+set_bench! {intersection_staggered_100_vs_10k, intersection, count, stagger(100, 100)}
+set_bench! {difference_random_100_vs_100, difference, count, [random(100), random(100)]}
+set_bench! {difference_random_100_vs_10k, difference, count, [random(100), random(10_000)]}
+set_bench! {difference_random_10k_vs_100, difference, count, [random(10_000), random(100)]}
+set_bench! {difference_random_10k_vs_10k, difference, count, [random(10_000), random(10_000)]}
+set_bench! {difference_staggered_100_vs_100, difference, count, stagger(100, 1)}
+set_bench! {difference_staggered_10k_vs_10k, difference, count, stagger(10_000, 1)}
+set_bench! {difference_staggered_100_vs_10k, difference, count, stagger(100, 100)}
+set_bench! {is_subset_100_vs_100, is_subset, clone, [pos(100), pos(100)]}
+set_bench! {is_subset_100_vs_10k, is_subset, clone, [pos(100), pos(10_000)]}
+set_bench! {is_subset_10k_vs_100, is_subset, clone, [pos(10_000), pos(100)]}
+set_bench! {is_subset_10k_vs_10k, is_subset, clone, [pos(10_000), pos(10_000)]}
diff --git a/library/alloc/benches/lib.rs b/library/alloc/benches/lib.rs
new file mode 100644
index 000000000..72ac897d4
--- /dev/null
+++ b/library/alloc/benches/lib.rs
@@ -0,0 +1,28 @@
+// Disabling on android for the time being
+// See https://github.com/rust-lang/rust/issues/73535#event-3477699747
+#![cfg(not(target_os = "android"))]
+#![feature(btree_drain_filter)]
+#![feature(iter_next_chunk)]
+#![feature(map_first_last)]
+#![feature(repr_simd)]
+#![feature(slice_partition_dedup)]
+#![feature(test)]
+
+extern crate test;
+
+mod binary_heap;
+mod btree;
+mod linked_list;
+mod slice;
+mod str;
+mod string;
+mod vec;
+mod vec_deque;
+
+/// Returns a `rand::Rng` seeded with a consistent seed.
+///
+/// This is done to avoid introducing nondeterminism in benchmark results.
+fn bench_rng() -> rand_xorshift::XorShiftRng {
+ const SEED: [u8; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
+ rand::SeedableRng::from_seed(SEED)
+}
diff --git a/library/alloc/benches/linked_list.rs b/library/alloc/benches/linked_list.rs
new file mode 100644
index 000000000..29c5ad2bc
--- /dev/null
+++ b/library/alloc/benches/linked_list.rs
@@ -0,0 +1,77 @@
+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/library/alloc/benches/slice.rs b/library/alloc/benches/slice.rs
new file mode 100644
index 000000000..bd6f38f2f
--- /dev/null
+++ b/library/alloc/benches/slice.rs
@@ -0,0 +1,379 @@
+use std::{mem, ptr};
+
+use rand::distributions::{Alphanumeric, Standard};
+use rand::Rng;
+use test::{black_box, Bencher};
+
+#[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 = crate::bench_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 = crate::bench_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 = crate::bench_rng();
+ (&mut rng).sample_iter(&Standard).take(len).collect()
+}
+
+fn gen_random_bytes(len: usize) -> Vec<u8> {
+ let mut rng = crate::bench_rng();
+ (&mut rng).sample_iter(&Standard).take(len).collect()
+}
+
+fn gen_mostly_ascending(len: usize) -> Vec<u64> {
+ let mut rng = crate::bench_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 = crate::bench_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 = crate::bench_rng();
+ let mut v = vec![];
+ for _ in 0..len {
+ let n = rng.gen::<usize>() % 20 + 1;
+ v.push((&mut rng).sample_iter(&Alphanumeric).take(n).collect());
+ }
+ v
+}
+
+fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
+ let mut rng = crate::bench_rng();
+ (&mut rng).sample_iter(&Standard).map(|x| [x; 16]).take(len).collect()
+}
+
+macro_rules! sort {
+ ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let v = $gen($len);
+ b.iter(|| v.clone().$f());
+ b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
+ }
+ };
+}
+
+macro_rules! sort_strings {
+ ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let v = $gen($len);
+ let v = v.iter().map(|s| &**s).collect::<Vec<&str>>();
+ b.iter(|| v.clone().$f());
+ b.bytes = $len * mem::size_of::<&str>() as u64;
+ }
+ };
+}
+
+macro_rules! sort_expensive {
+ ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let v = $gen($len);
+ b.iter(|| {
+ let mut v = v.clone();
+ 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 * mem::size_of_val(&$gen(1)[0]) as u64;
+ }
+ };
+}
+
+macro_rules! sort_lexicographic {
+ ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let v = $gen($len);
+ b.iter(|| v.clone().$f(|x| x.to_string()));
+ b.bytes = $len * mem::size_of_val(&$gen(1)[0]) 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, 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, gen_big_random, 10000);
+sort_strings!(sort, sort_large_strings, gen_strings, 10000);
+sort_expensive!(sort_by, sort_large_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, 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, gen_big_random, 10000);
+sort_strings!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
+sort_expensive!(sort_unstable_by, sort_unstable_large_expensive, gen_random, 10000);
+
+sort_lexicographic!(sort_by_key, sort_by_key_lexicographic, gen_random, 10000);
+sort_lexicographic!(sort_unstable_by_key, sort_unstable_by_key_lexicographic, gen_random, 10000);
+sort_lexicographic!(sort_by_cached_key, sort_by_cached_key_lexicographic, 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_left(($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/library/alloc/benches/str.rs b/library/alloc/benches/str.rs
new file mode 100644
index 000000000..391475bc0
--- /dev/null
+++ b/library/alloc/benches/str.rs
@@ -0,0 +1,299 @@
+use test::{black_box, Bencher};
+
+#[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, { s.trim_matches(|c: char| c.is_ascii()) });
+make_test!(trim_start_ascii_char, s, { s.trim_start_matches(|c: char| c.is_ascii()) });
+make_test!(trim_end_ascii_char, s, { s.trim_end_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/library/alloc/benches/string.rs b/library/alloc/benches/string.rs
new file mode 100644
index 000000000..5c95160ba
--- /dev/null
+++ b/library/alloc/benches/string.rs
@@ -0,0 +1,164 @@
+use std::iter::repeat;
+use test::{black_box, 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())
+}
+
+#[bench]
+fn bench_insert_char_short(b: &mut Bencher) {
+ let s = "Hello, World!";
+ b.iter(|| {
+ let mut x = String::from(s);
+ black_box(&mut x).insert(6, black_box(' '));
+ x
+ })
+}
+
+#[bench]
+fn bench_insert_char_long(b: &mut Bencher) {
+ let s = "Hello, World!";
+ b.iter(|| {
+ let mut x = String::from(s);
+ black_box(&mut x).insert(6, black_box('❤'));
+ x
+ })
+}
+
+#[bench]
+fn bench_insert_str_short(b: &mut Bencher) {
+ let s = "Hello, World!";
+ b.iter(|| {
+ let mut x = String::from(s);
+ black_box(&mut x).insert_str(6, black_box(" "));
+ x
+ })
+}
+
+#[bench]
+fn bench_insert_str_long(b: &mut Bencher) {
+ let s = "Hello, World!";
+ b.iter(|| {
+ let mut x = String::from(s);
+ black_box(&mut x).insert_str(6, black_box(" rustic "));
+ x
+ })
+}
diff --git a/library/alloc/benches/vec.rs b/library/alloc/benches/vec.rs
new file mode 100644
index 000000000..663f6b9dd
--- /dev/null
+++ b/library/alloc/benches/vec.rs
@@ -0,0 +1,784 @@
+use rand::RngCore;
+use std::iter::{repeat, FromIterator};
+use test::{black_box, Bencher};
+
+#[bench]
+fn bench_new(b: &mut Bencher) {
+ b.iter(|| Vec::<u32>::new())
+}
+
+fn do_bench_with_capacity(b: &mut Bencher, src_len: usize) {
+ b.bytes = src_len as u64;
+
+ b.iter(|| Vec::<u32>::with_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(|| (0..src_len).collect::<Vec<_>>())
+}
+
+#[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(|| repeat(5).take(src_len).collect::<Vec<usize>>())
+}
+
+#[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(|| src.as_slice().to_vec());
+}
+
+#[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.iter().cloned());
+ dst
+ });
+}
+
+#[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());
+ dst
+ });
+}
+
+#[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_extend_from_slice(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);
+ dst
+ });
+}
+
+#[bench]
+fn bench_extend_recycle(b: &mut Bencher) {
+ let mut data = vec![0; 1000];
+
+ b.iter(|| {
+ let tmp = std::mem::take(&mut data);
+ let mut to_extend = black_box(Vec::new());
+ to_extend.extend(tmp.into_iter());
+ data = black_box(to_extend);
+ });
+
+ black_box(data);
+}
+
+#[bench]
+fn bench_extend_from_slice_0000_0000(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 0, 0)
+}
+
+#[bench]
+fn bench_extend_from_slice_0000_0010(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 0, 10)
+}
+
+#[bench]
+fn bench_extend_from_slice_0000_0100(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 0, 100)
+}
+
+#[bench]
+fn bench_extend_from_slice_0000_1000(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 0, 1000)
+}
+
+#[bench]
+fn bench_extend_from_slice_0010_0010(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 10, 10)
+}
+
+#[bench]
+fn bench_extend_from_slice_0100_0100(b: &mut Bencher) {
+ do_bench_extend_from_slice(b, 100, 100)
+}
+
+#[bench]
+fn bench_extend_from_slice_1000_1000(b: &mut Bencher) {
+ do_bench_extend_from_slice(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(|| src.clone());
+}
+
+#[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);
+ dst = black_box(dst);
+ }
+ dst
+ });
+}
+
+#[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)
+}
+
+macro_rules! bench_in_place {
+ ($($fname:ident, $type:ty, $count:expr, $init:expr);*) => {
+ $(
+ #[bench]
+ fn $fname(b: &mut Bencher) {
+ b.iter(|| {
+ let src: Vec<$type> = black_box(vec![$init; $count]);
+ src.into_iter()
+ .enumerate()
+ .map(|(idx, e)| idx as $type ^ e)
+ .collect::<Vec<$type>>()
+ });
+ }
+ )+
+ };
+}
+
+bench_in_place![
+ bench_in_place_xxu8_0010_i0, u8, 10, 0;
+ bench_in_place_xxu8_0100_i0, u8, 100, 0;
+ bench_in_place_xxu8_1000_i0, u8, 1000, 0;
+ bench_in_place_xxu8_0010_i1, u8, 10, 1;
+ bench_in_place_xxu8_0100_i1, u8, 100, 1;
+ bench_in_place_xxu8_1000_i1, u8, 1000, 1;
+ bench_in_place_xu32_0010_i0, u32, 10, 0;
+ bench_in_place_xu32_0100_i0, u32, 100, 0;
+ bench_in_place_xu32_1000_i0, u32, 1000, 0;
+ bench_in_place_xu32_0010_i1, u32, 10, 1;
+ bench_in_place_xu32_0100_i1, u32, 100, 1;
+ bench_in_place_xu32_1000_i1, u32, 1000, 1;
+ bench_in_place_u128_0010_i0, u128, 10, 0;
+ bench_in_place_u128_0100_i0, u128, 100, 0;
+ bench_in_place_u128_1000_i0, u128, 1000, 0;
+ bench_in_place_u128_0010_i1, u128, 10, 1;
+ bench_in_place_u128_0100_i1, u128, 100, 1;
+ bench_in_place_u128_1000_i1, u128, 1000, 1
+];
+
+#[bench]
+fn bench_in_place_recycle(b: &mut Bencher) {
+ let mut data = vec![0; 1000];
+
+ b.iter(|| {
+ let tmp = std::mem::take(&mut data);
+ data = black_box(
+ tmp.into_iter()
+ .enumerate()
+ .map(|(idx, e)| idx.wrapping_add(e))
+ .fuse()
+ .collect::<Vec<usize>>(),
+ );
+ });
+}
+
+#[bench]
+fn bench_in_place_zip_recycle(b: &mut Bencher) {
+ let mut data = vec![0u8; 1000];
+ let mut rng = crate::bench_rng();
+ let mut subst = vec![0u8; 1000];
+ rng.fill_bytes(&mut subst[..]);
+
+ b.iter(|| {
+ let tmp = std::mem::take(&mut data);
+ let mangled = tmp
+ .into_iter()
+ .zip(subst.iter().copied())
+ .enumerate()
+ .map(|(i, (d, s))| d.wrapping_add(i as u8) ^ s)
+ .collect::<Vec<_>>();
+ data = black_box(mangled);
+ });
+}
+
+#[bench]
+fn bench_in_place_zip_iter_mut(b: &mut Bencher) {
+ let mut data = vec![0u8; 256];
+ let mut rng = crate::bench_rng();
+ let mut subst = vec![0u8; 1000];
+ rng.fill_bytes(&mut subst[..]);
+
+ b.iter(|| {
+ data.iter_mut().enumerate().for_each(|(i, d)| {
+ *d = d.wrapping_add(i as u8) ^ subst[i];
+ });
+ });
+
+ black_box(data);
+}
+
+pub fn vec_cast<T, U>(input: Vec<T>) -> Vec<U> {
+ input.into_iter().map(|e| unsafe { std::mem::transmute_copy(&e) }).collect()
+}
+
+#[bench]
+fn bench_transmute(b: &mut Bencher) {
+ let mut vec = vec![10u32; 100];
+ b.bytes = 800; // 2 casts x 4 bytes x 100
+ b.iter(|| {
+ let v = std::mem::take(&mut vec);
+ let v = black_box(vec_cast::<u32, i32>(v));
+ let v = black_box(vec_cast::<i32, u32>(v));
+ vec = v;
+ });
+}
+
+#[derive(Clone)]
+struct Droppable(usize);
+
+impl Drop for Droppable {
+ fn drop(&mut self) {
+ black_box(self);
+ }
+}
+
+#[bench]
+fn bench_in_place_collect_droppable(b: &mut Bencher) {
+ let v: Vec<Droppable> = std::iter::repeat_with(|| Droppable(0)).take(1000).collect();
+ b.iter(|| {
+ v.clone()
+ .into_iter()
+ .skip(100)
+ .enumerate()
+ .map(|(i, e)| Droppable(i ^ e.0))
+ .collect::<Vec<_>>()
+ })
+}
+
+const LEN: usize = 16384;
+
+#[bench]
+fn bench_chain_collect(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| data.iter().cloned().chain([1]).collect::<Vec<_>>());
+}
+
+#[bench]
+fn bench_chain_chain_collect(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| data.iter().cloned().chain([1]).chain([2]).collect::<Vec<_>>());
+}
+
+#[bench]
+fn bench_nest_chain_chain_collect(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| {
+ data.iter().cloned().chain([1].iter().chain([2].iter()).cloned()).collect::<Vec<_>>()
+ });
+}
+
+#[bench]
+fn bench_range_map_collect(b: &mut Bencher) {
+ b.iter(|| (0..LEN).map(|_| u32::default()).collect::<Vec<_>>());
+}
+
+#[bench]
+fn bench_chain_extend_ref(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| {
+ let mut v = Vec::<u32>::with_capacity(data.len() + 1);
+ v.extend(data.iter().chain([1].iter()));
+ v
+ });
+}
+
+#[bench]
+fn bench_chain_extend_value(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| {
+ let mut v = Vec::<u32>::with_capacity(data.len() + 1);
+ v.extend(data.iter().cloned().chain(Some(1)));
+ v
+ });
+}
+
+#[bench]
+fn bench_rev_1(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| {
+ let mut v = Vec::<u32>::new();
+ v.extend(data.iter().rev());
+ v
+ });
+}
+
+#[bench]
+fn bench_rev_2(b: &mut Bencher) {
+ let data = black_box([0; LEN]);
+ b.iter(|| {
+ let mut v = Vec::<u32>::with_capacity(data.len());
+ v.extend(data.iter().rev());
+ v
+ });
+}
+
+#[bench]
+fn bench_map_regular(b: &mut Bencher) {
+ let data = black_box([(0, 0); LEN]);
+ b.iter(|| {
+ let mut v = Vec::<u32>::new();
+ v.extend(data.iter().map(|t| t.1));
+ v
+ });
+}
+
+#[bench]
+fn bench_map_fast(b: &mut Bencher) {
+ let data = black_box([(0, 0); LEN]);
+ b.iter(|| {
+ let mut result: Vec<u32> = Vec::with_capacity(data.len());
+ for i in 0..data.len() {
+ unsafe {
+ *result.as_mut_ptr().add(i) = data[i].0;
+ result.set_len(i);
+ }
+ }
+ result
+ });
+}
+
+fn random_sorted_fill(mut seed: u32, buf: &mut [u32]) {
+ let mask = if buf.len() < 8192 {
+ 0xFF
+ } else if buf.len() < 200_000 {
+ 0xFFFF
+ } else {
+ 0xFFFF_FFFF
+ };
+
+ for item in buf.iter_mut() {
+ seed ^= seed << 13;
+ seed ^= seed >> 17;
+ seed ^= seed << 5;
+
+ *item = seed & mask;
+ }
+
+ buf.sort();
+}
+
+fn bench_vec_dedup_old(b: &mut Bencher, sz: usize) {
+ let mut template = vec![0u32; sz];
+ b.bytes = std::mem::size_of_val(template.as_slice()) as u64;
+ random_sorted_fill(0x43, &mut template);
+
+ let mut vec = template.clone();
+ b.iter(|| {
+ let len = {
+ let (dedup, _) = vec.partition_dedup();
+ dedup.len()
+ };
+ vec.truncate(len);
+
+ black_box(vec.first());
+ vec.clear();
+ vec.extend_from_slice(&template);
+ });
+}
+
+fn bench_vec_dedup_new(b: &mut Bencher, sz: usize) {
+ let mut template = vec![0u32; sz];
+ b.bytes = std::mem::size_of_val(template.as_slice()) as u64;
+ random_sorted_fill(0x43, &mut template);
+
+ let mut vec = template.clone();
+ b.iter(|| {
+ vec.dedup();
+ black_box(vec.first());
+ vec.clear();
+ vec.extend_from_slice(&template);
+ });
+}
+
+#[bench]
+fn bench_dedup_old_100(b: &mut Bencher) {
+ bench_vec_dedup_old(b, 100);
+}
+#[bench]
+fn bench_dedup_new_100(b: &mut Bencher) {
+ bench_vec_dedup_new(b, 100);
+}
+
+#[bench]
+fn bench_dedup_old_1000(b: &mut Bencher) {
+ bench_vec_dedup_old(b, 1000);
+}
+#[bench]
+fn bench_dedup_new_1000(b: &mut Bencher) {
+ bench_vec_dedup_new(b, 1000);
+}
+
+#[bench]
+fn bench_dedup_old_10000(b: &mut Bencher) {
+ bench_vec_dedup_old(b, 10000);
+}
+#[bench]
+fn bench_dedup_new_10000(b: &mut Bencher) {
+ bench_vec_dedup_new(b, 10000);
+}
+
+#[bench]
+fn bench_dedup_old_100000(b: &mut Bencher) {
+ bench_vec_dedup_old(b, 100000);
+}
+#[bench]
+fn bench_dedup_new_100000(b: &mut Bencher) {
+ bench_vec_dedup_new(b, 100000);
+}
+
+#[bench]
+fn bench_flat_map_collect(b: &mut Bencher) {
+ let v = vec![777u32; 500000];
+ b.iter(|| v.iter().flat_map(|color| color.rotate_left(8).to_be_bytes()).collect::<Vec<_>>());
+}
+
+/// Reference benchmark that `retain` has to compete with.
+#[bench]
+fn bench_retain_iter_100000(b: &mut Bencher) {
+ let mut v = Vec::with_capacity(100000);
+
+ b.iter(|| {
+ let mut tmp = std::mem::take(&mut v);
+ tmp.clear();
+ tmp.extend(black_box(1..=100000));
+ v = tmp.into_iter().filter(|x| x & 1 == 0).collect();
+ });
+}
+
+#[bench]
+fn bench_retain_100000(b: &mut Bencher) {
+ let mut v = Vec::with_capacity(100000);
+
+ b.iter(|| {
+ v.clear();
+ v.extend(black_box(1..=100000));
+ v.retain(|x| x & 1 == 0)
+ });
+}
+
+#[bench]
+fn bench_retain_whole_100000(b: &mut Bencher) {
+ let mut v = black_box(vec![826u32; 100000]);
+ b.iter(|| v.retain(|x| *x == 826u32));
+}
+
+#[bench]
+fn bench_next_chunk(b: &mut Bencher) {
+ let v = vec![13u8; 2048];
+
+ b.iter(|| {
+ const CHUNK: usize = 8;
+
+ let mut sum = [0u32; CHUNK];
+ let mut iter = black_box(v.clone()).into_iter();
+
+ while let Ok(chunk) = iter.next_chunk::<CHUNK>() {
+ for i in 0..CHUNK {
+ sum[i] += chunk[i] as u32;
+ }
+ }
+
+ sum
+ })
+}
diff --git a/library/alloc/benches/vec_deque.rs b/library/alloc/benches/vec_deque.rs
new file mode 100644
index 000000000..7c78561eb
--- /dev/null
+++ b/library/alloc/benches/vec_deque.rs
@@ -0,0 +1,125 @@
+use std::collections::VecDeque;
+use test::{black_box, Bencher};
+
+#[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);
+ })
+}
+
+#[bench]
+fn bench_try_fold(b: &mut Bencher) {
+ let ring: VecDeque<_> = (0..1000).collect();
+
+ b.iter(|| black_box(ring.iter().try_fold(0, |a, b| Some(a + b))))
+}
+
+#[bench]
+fn bench_from_array_1000(b: &mut Bencher) {
+ const N: usize = 1000;
+ let mut array: [usize; N] = [0; N];
+
+ for i in 0..N {
+ array[i] = i;
+ }
+
+ b.iter(|| {
+ let deq: VecDeque<_> = array.into();
+ black_box(deq);
+ })
+}
+
+#[bench]
+fn bench_extend_bytes(b: &mut Bencher) {
+ let mut ring: VecDeque<u8> = VecDeque::with_capacity(1000);
+ let input: &[u8] = &[128; 512];
+
+ b.iter(|| {
+ ring.clear();
+ ring.extend(black_box(input));
+ });
+}
+
+#[bench]
+fn bench_extend_vec(b: &mut Bencher) {
+ let mut ring: VecDeque<u8> = VecDeque::with_capacity(1000);
+ let input = vec![128; 512];
+
+ b.iter(|| {
+ ring.clear();
+
+ let input = input.clone();
+ ring.extend(black_box(input));
+ });
+}
+
+#[bench]
+fn bench_extend_trustedlen(b: &mut Bencher) {
+ let mut ring: VecDeque<u16> = VecDeque::with_capacity(1000);
+
+ b.iter(|| {
+ ring.clear();
+ ring.extend(black_box(0..512));
+ });
+}
+
+#[bench]
+fn bench_extend_chained_trustedlen(b: &mut Bencher) {
+ let mut ring: VecDeque<u16> = VecDeque::with_capacity(1000);
+
+ b.iter(|| {
+ ring.clear();
+ ring.extend(black_box((0..256).chain(768..1024)));
+ });
+}
+
+#[bench]
+fn bench_extend_chained_bytes(b: &mut Bencher) {
+ let mut ring: VecDeque<u16> = VecDeque::with_capacity(1000);
+ let input1: &[u16] = &[128; 256];
+ let input2: &[u16] = &[255; 256];
+
+ b.iter(|| {
+ ring.clear();
+ ring.extend(black_box(input1.iter().chain(input2.iter())));
+ });
+}
diff --git a/library/alloc/benches/vec_deque_append.rs b/library/alloc/benches/vec_deque_append.rs
new file mode 100644
index 000000000..5825bdc35
--- /dev/null
+++ b/library/alloc/benches/vec_deque_append.rs
@@ -0,0 +1,34 @@
+use std::{collections::VecDeque, time::Instant};
+
+const VECDEQUE_LEN: i32 = 100000;
+const WARMUP_N: usize = 100;
+const BENCH_N: usize = 1000;
+
+fn main() {
+ let a: VecDeque<i32> = (0..VECDEQUE_LEN).collect();
+ let b: VecDeque<i32> = (0..VECDEQUE_LEN).collect();
+
+ for _ in 0..WARMUP_N {
+ let mut c = a.clone();
+ let mut d = b.clone();
+ c.append(&mut d);
+ }
+
+ let mut durations = Vec::with_capacity(BENCH_N);
+
+ for _ in 0..BENCH_N {
+ let mut c = a.clone();
+ let mut d = b.clone();
+ let before = Instant::now();
+ c.append(&mut d);
+ let after = Instant::now();
+ durations.push(after.duration_since(before));
+ }
+
+ let l = durations.len();
+ durations.sort();
+
+ assert!(BENCH_N % 2 == 0);
+ let median = (durations[(l / 2) - 1] + durations[l / 2]) / 2;
+ println!("\ncustom-bench vec_deque_append {:?} ns/iter\n", median.as_nanos());
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-01 02:48:12 +0000