From f66bcc5459d4a720b31eaeac3149f19799118d72 Mon Sep 17 00:00:00 2001 From: Ivan Tham Date: Sat, 20 Jun 2020 11:07:22 +0800 Subject: Add liballoc impl SpecFromElem for i8 Speedup vec![1_i8; N] for non-zero element. Before test do_bench_from_elem_i8 ... bench: 130 ns/iter (+/- 7) = 61 MB/s test do_bench_from_elem_u8 ... bench: 121 ns/iter (+/- 4) = 66 MB/s After test do_bench_from_elem_i8 ... bench: 123 ns/iter (+/- 7) = 65 MB/s test do_bench_from_elem_u8 ... bench: 121 ns/iter (+/- 5) = 66 MB/s No speed difference if element is already zero. #[bench] fn do_bench_from_elem_i8(b: &mut Bencher) { b.bytes = 8 as u64; b.iter(|| { let dst = ve::vec![10_i8; 100]; assert_eq!(dst.len(), 100); assert!(dst.iter().all(|x| *x == 10)); }) } As suggested by @cuviper https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/SpecForElem.20for.20other.20integers --- src/liballoc/vec.rs | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'src/liballoc') diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs index f16cac05ea0..b4a8597656e 100644 --- a/src/liballoc/vec.rs +++ b/src/liballoc/vec.rs @@ -1803,6 +1803,21 @@ impl SpecFromElem for T { } } +impl SpecFromElem for i8 { + #[inline] + fn from_elem(elem: i8, n: usize) -> Vec { + if elem == 0 { + return Vec { buf: RawVec::with_capacity_zeroed(n), len: n }; + } + unsafe { + let mut v = Vec::with_capacity(n); + ptr::write_bytes(v.as_mut_ptr(), elem as u8, n); + v.set_len(n); + v + } + } +} + impl SpecFromElem for u8 { #[inline] fn from_elem(elem: u8, n: usize) -> Vec { @@ -1847,7 +1862,6 @@ macro_rules! impl_is_zero { }; } -impl_is_zero!(i8, |x| x == 0); impl_is_zero!(i16, |x| x == 0); impl_is_zero!(i32, |x| x == 0); impl_is_zero!(i64, |x| x == 0); -- cgit 1.4.1-3-g733a5 From 42062a58026cdb245e3eb365af726f2d9f4946af Mon Sep 17 00:00:00 2001 From: Stein Somers Date: Mon, 22 Jun 2020 20:12:11 +0200 Subject: Shortcuts for min/max on ordinary BTreeMap/BTreeSet iterators --- src/liballoc/collections/btree/map.rs | 40 +++++++++++++++++++++++++++++++++++ src/liballoc/collections/btree/set.rs | 35 ++++++++++++++++++++++++++++++ src/liballoc/tests/btree/map.rs | 35 ++++++++++++++++++++++++++++++ src/liballoc/tests/btree/set.rs | 31 +++++++++++++++++++++++++++ 4 files changed, 141 insertions(+) (limited to 'src/liballoc') diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs index 34cacebe796..bb9091a6659 100644 --- a/src/liballoc/collections/btree/map.rs +++ b/src/liballoc/collections/btree/map.rs @@ -1396,6 +1396,14 @@ impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { fn last(mut self) -> Option<(&'a K, &'a V)> { self.next_back() } + + fn min(mut self) -> Option<(&'a K, &'a V)> { + self.next() + } + + fn max(mut self) -> Option<(&'a K, &'a V)> { + self.next_back() + } } #[stable(feature = "fused", since = "1.26.0")] @@ -1458,6 +1466,14 @@ impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> { fn last(mut self) -> Option<(&'a K, &'a mut V)> { self.next_back() } + + fn min(mut self) -> Option<(&'a K, &'a mut V)> { + self.next() + } + + fn max(mut self) -> Option<(&'a K, &'a mut V)> { + self.next_back() + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1595,6 +1611,14 @@ impl<'a, K, V> Iterator for Keys<'a, K, V> { fn last(mut self) -> Option<&'a K> { self.next_back() } + + fn min(mut self) -> Option<&'a K> { + self.next() + } + + fn max(mut self) -> Option<&'a K> { + self.next_back() + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1768,6 +1792,14 @@ impl<'a, K, V> Iterator for Range<'a, K, V> { fn last(mut self) -> Option<(&'a K, &'a V)> { self.next_back() } + + fn min(mut self) -> Option<(&'a K, &'a V)> { + self.next() + } + + fn max(mut self) -> Option<(&'a K, &'a V)> { + self.next_back() + } } #[stable(feature = "map_values_mut", since = "1.10.0")] @@ -1853,6 +1885,14 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> { fn last(mut self) -> Option<(&'a K, &'a mut V)> { self.next_back() } + + fn min(mut self) -> Option<(&'a K, &'a mut V)> { + self.next() + } + + fn max(mut self) -> Option<(&'a K, &'a mut V)> { + self.next_back() + } } impl<'a, K, V> RangeMut<'a, K, V> { diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs index 525ef38c32f..d8959966fe5 100644 --- a/src/liballoc/collections/btree/set.rs +++ b/src/liballoc/collections/btree/set.rs @@ -1291,12 +1291,22 @@ impl<'a, T> Iterator for Iter<'a, T> { fn next(&mut self) -> Option<&'a T> { self.iter.next() } + fn size_hint(&self) -> (usize, Option) { self.iter.size_hint() } + fn last(mut self) -> Option<&'a T> { self.next_back() } + + fn min(mut self) -> Option<&'a T> { + self.next() + } + + fn max(mut self) -> Option<&'a T> { + self.next_back() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T> DoubleEndedIterator for Iter<'a, T> { @@ -1321,6 +1331,7 @@ impl Iterator for IntoIter { fn next(&mut self) -> Option { self.iter.next().map(|(k, _)| k) } + fn size_hint(&self) -> (usize, Option) { self.iter.size_hint() } @@ -1359,6 +1370,14 @@ impl<'a, T> Iterator for Range<'a, T> { fn last(mut self) -> Option<&'a T> { self.next_back() } + + fn min(mut self) -> Option<&'a T> { + self.next() + } + + fn max(mut self) -> Option<&'a T> { + self.next_back() + } } #[stable(feature = "btree_range", since = "1.17.0")] @@ -1429,6 +1448,10 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> { }; (self_len.saturating_sub(other_len), Some(self_len)) } + + fn min(mut self) -> Option<&'a T> { + self.next() + } } #[stable(feature = "fused", since = "1.26.0")] @@ -1460,6 +1483,10 @@ impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> { // the number of elements to less than half the range of usize. (0, Some(a_len + b_len)) } + + fn min(mut self) -> Option<&'a T> { + self.next() + } } #[stable(feature = "fused", since = "1.26.0")] @@ -1516,6 +1543,10 @@ impl<'a, T: Ord> Iterator for Intersection<'a, T> { IntersectionInner::Answer(Some(_)) => (1, Some(1)), } } + + fn min(mut self) -> Option<&'a T> { + self.next() + } } #[stable(feature = "fused", since = "1.26.0")] @@ -1541,6 +1572,10 @@ impl<'a, T: Ord> Iterator for Union<'a, T> { // No checked_add - see SymmetricDifference::size_hint. (max(a_len, b_len), Some(a_len + b_len)) } + + fn min(mut self) -> Option<&'a T> { + self.next() + } } #[stable(feature = "fused", since = "1.26.0")] diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs index 731a1b5f875..682d829d219 100644 --- a/src/liballoc/tests/btree/map.rs +++ b/src/liballoc/tests/btree/map.rs @@ -309,6 +309,41 @@ fn test_iter_mixed() { test(size, map.into_iter()); } +#[test] +fn test_iter_min_max() { + let mut a = BTreeMap::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.iter_mut().min(), None); + assert_eq!(a.iter_mut().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.range_mut(..).min(), None); + assert_eq!(a.range_mut(..).max(), None); + assert_eq!(a.keys().min(), None); + assert_eq!(a.keys().max(), None); + assert_eq!(a.values().min(), None); + assert_eq!(a.values().max(), None); + assert_eq!(a.values_mut().min(), None); + assert_eq!(a.values_mut().max(), None); + a.insert(1, 42); + a.insert(2, 24); + assert_eq!(a.iter().min(), Some((&1, &42))); + assert_eq!(a.iter().max(), Some((&2, &24))); + assert_eq!(a.iter_mut().min(), Some((&1, &mut 42))); + assert_eq!(a.iter_mut().max(), Some((&2, &mut 24))); + assert_eq!(a.range(..).min(), Some((&1, &42))); + assert_eq!(a.range(..).max(), Some((&2, &24))); + assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42))); + assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24))); + assert_eq!(a.keys().min(), Some(&1)); + assert_eq!(a.keys().max(), Some(&2)); + assert_eq!(a.values().min(), Some(&24)); + assert_eq!(a.values().max(), Some(&42)); + assert_eq!(a.values_mut().min(), Some(&mut 24)); + assert_eq!(a.values_mut().max(), Some(&mut 42)); +} + fn range_keys(map: &BTreeMap, range: impl RangeBounds) -> Vec { map.range(range) .map(|(&k, &v)| { diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs index 75251ca0d51..b6c34b7c6c3 100644 --- a/src/liballoc/tests/btree/set.rs +++ b/src/liballoc/tests/btree/set.rs @@ -33,6 +33,37 @@ fn test_hash() { assert_eq!(hash(&x), hash(&y)); } +#[test] +fn test_iter_min_max() { + let mut a = BTreeSet::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.difference(&BTreeSet::new()).min(), None); + assert_eq!(a.difference(&BTreeSet::new()).max(), None); + assert_eq!(a.intersection(&a).min(), None); + assert_eq!(a.intersection(&a).max(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None); + assert_eq!(a.union(&a).min(), None); + assert_eq!(a.union(&a).max(), None); + a.insert(1); + a.insert(2); + assert_eq!(a.iter().min(), Some(&1)); + assert_eq!(a.iter().max(), Some(&2)); + assert_eq!(a.range(..).min(), Some(&1)); + assert_eq!(a.range(..).max(), Some(&2)); + assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.intersection(&a).min(), Some(&1)); + assert_eq!(a.intersection(&a).max(), Some(&2)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.union(&a).min(), Some(&1)); + assert_eq!(a.union(&a).max(), Some(&2)); +} + fn check(a: &[i32], b: &[i32], expected: &[i32], f: F) where F: FnOnce(&BTreeSet, &BTreeSet, &mut dyn FnMut(&i32) -> bool) -> bool, -- cgit 1.4.1-3-g733a5 From cb152eae2f63cc07e23142452d7e80b24392c284 Mon Sep 17 00:00:00 2001 From: "KRAAI, MATTHEW [VISUS]" Date: Fri, 26 Jun 2020 06:22:35 -0700 Subject: Remove blank line --- src/liballoc/raw_vec/tests.rs | 1 - 1 file changed, 1 deletion(-) (limited to 'src/liballoc') diff --git a/src/liballoc/raw_vec/tests.rs b/src/liballoc/raw_vec/tests.rs index 6418c4a9823..5408faa079c 100644 --- a/src/liballoc/raw_vec/tests.rs +++ b/src/liballoc/raw_vec/tests.rs @@ -12,7 +12,6 @@ fn allocator_param() { // // Instead, this just checks that the `RawVec` methods do at // least go through the Allocator API when it reserves - // storage. // A dumb allocator that consumes a fixed amount of fuel -- cgit 1.4.1-3-g733a5