From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/benches/binary_heap.rs | 91 ++++ library/alloc/benches/btree/map.rs | 585 ++++++++++++++++++++++ library/alloc/benches/btree/mod.rs | 2 + library/alloc/benches/btree/set.rs | 224 +++++++++ library/alloc/benches/lib.rs | 28 ++ library/alloc/benches/linked_list.rs | 77 +++ library/alloc/benches/slice.rs | 379 +++++++++++++++ library/alloc/benches/str.rs | 299 ++++++++++++ library/alloc/benches/string.rs | 164 +++++++ library/alloc/benches/vec.rs | 784 ++++++++++++++++++++++++++++++ library/alloc/benches/vec_deque.rs | 125 +++++ library/alloc/benches/vec_deque_append.rs | 34 ++ 12 files changed, 2792 insertions(+) create mode 100644 library/alloc/benches/binary_heap.rs create mode 100644 library/alloc/benches/btree/map.rs create mode 100644 library/alloc/benches/btree/mod.rs create mode 100644 library/alloc/benches/btree/set.rs create mode 100644 library/alloc/benches/lib.rs create mode 100644 library/alloc/benches/linked_list.rs create mode 100644 library/alloc/benches/slice.rs create mode 100644 library/alloc/benches/str.rs create mode 100644 library/alloc/benches/string.rs create mode 100644 library/alloc/benches/vec.rs create mode 100644 library/alloc/benches/vec_deque.rs create mode 100644 library/alloc/benches/vec_deque_append.rs (limited to 'library/alloc/benches') 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 = (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 = (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 = (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 = (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 = (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::() % n; + map.insert(i, i); + } + + // measure + b.iter(|| { + let k = rng.gen::() % 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::() % 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::() % 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::::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::::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(b: &mut Bencher, f: F) +where + F: Fn(i32, i32) -> R, + R: RangeBounds, +{ + 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 { + (0..n).map(|i| (i, i)).collect::>() +} + +// The returned map has small keys and large values. +fn fat_val_map(n: usize) -> BTreeMap { + (0..n).map(|i| (i, [i; FAT])).collect::>() +} + +#[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 { + 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 { + let set: BTreeSet = (-(n as i32)..=-1).collect(); + assert_eq!(set.len(), n); + set +} + +fn pos(n: usize) -> BTreeSet { + let set: BTreeSet = (1..=(n as i32)).collect(); + assert_eq!(set.len(), n); + set +} + +fn stagger(n1: usize, factor: usize) -> [BTreeSet; 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 { + (0..n).collect::>() +} + +#[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> = (0..100).map(|i| (0..i).collect()).collect(); + b.iter(|| { + xss.concat(); + }); +} + +#[bench] +fn join(b: &mut Bencher) { + let xss: Vec> = (0..100).map(|i| (0..i).collect()).collect(); + b.iter(|| xss.join(&0)); +} + +#[bench] +fn push(b: &mut Bencher) { + let mut vec = Vec::::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::::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::::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::::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::() % (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::() % l); + } + }) +} + +fn gen_ascending(len: usize) -> Vec { + (0..len as u64).collect() +} + +fn gen_descending(len: usize) -> Vec { + (0..len as u64).rev().collect() +} + +fn gen_random(len: usize) -> Vec { + let mut rng = crate::bench_rng(); + (&mut rng).sample_iter(&Standard).take(len).collect() +} + +fn gen_random_bytes(len: usize) -> Vec { + let mut rng = crate::bench_rng(); + (&mut rng).sample_iter(&Standard).take(len).collect() +} + +fn gen_mostly_ascending(len: usize) -> Vec { + 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::() % len; + let y = rng.gen::() % len; + v.swap(x, y); + } + v +} + +fn gen_mostly_descending(len: usize) -> Vec { + 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::() % len; + let y = rng.gen::() % len; + v.swap(x, y); + } + v +} + +fn gen_strings(len: usize) -> Vec { + let mut rng = crate::bench_rng(); + let mut v = vec![]; + for _ in 0..len { + let n = rng.gen::() % 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::>(); + 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::>(); + 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::::new()) +} + +fn do_bench_with_capacity(b: &mut Bencher, src_len: usize) { + b.bytes = src_len as u64; + + b.iter(|| Vec::::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::>()) +} + +#[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::>()) +} + +#[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 = 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::>() + }); + } + )+ + }; +} + +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::>(), + ); + }); +} + +#[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::>(); + 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(input: Vec) -> Vec { + 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::(v)); + let v = black_box(vec_cast::(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 = 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::>() + }) +} + +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::>()); +} + +#[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::>()); +} + +#[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::>() + }); +} + +#[bench] +fn bench_range_map_collect(b: &mut Bencher) { + b.iter(|| (0..LEN).map(|_| u32::default()).collect::>()); +} + +#[bench] +fn bench_chain_extend_ref(b: &mut Bencher) { + let data = black_box([0; LEN]); + b.iter(|| { + let mut v = Vec::::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::::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::::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::::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::::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 = 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::>()); +} + +/// 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::() { + 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 = 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 = 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 = 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 = 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 = 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 = 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 = (0..VECDEQUE_LEN).collect(); + let b: VecDeque = (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()); +} -- cgit v1.2.3