From 3ca6bb0b44c3e65dab07e12aec9efb277dc206f9 Mon Sep 17 00:00:00 2001 From: The 8472 Date: Sat, 15 Apr 2023 12:59:16 +0200 Subject: Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunks --- library/alloc/src/collections/binary_heap/mod.rs | 11 +++- library/alloc/src/lib.rs | 1 + library/alloc/src/vec/in_place_collect.rs | 83 +++++++++++++++++++----- library/alloc/src/vec/into_iter.rs | 12 +++- 4 files changed, 86 insertions(+), 21 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs index 66573b90db9..ad2c4e483a3 100644 --- a/library/alloc/src/collections/binary_heap/mod.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -145,7 +145,7 @@ use core::alloc::Allocator; use core::fmt; -use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; +use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; @@ -1540,6 +1540,10 @@ impl ExactSizeIterator for IntoIter { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IntoIter {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl TrustedFused for IntoIter {} + #[stable(feature = "default_iters", since = "1.70.0")] impl Default for IntoIter { /// Creates an empty `binary_heap::IntoIter`. @@ -1569,7 +1573,10 @@ unsafe impl SourceIter for IntoIter { #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl InPlaceIterable for IntoIter {} +unsafe impl InPlaceIterable for IntoIter { + const EXPAND_BY: Option = NonZeroUsize::new(1); + const MERGE_BY: Option = NonZeroUsize::new(1); +} unsafe impl AsVecIntoIter for IntoIter { type Item = I; diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index e43b6ac4039..c9fee435f1e 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -155,6 +155,7 @@ #![feature(std_internals)] #![feature(str_internals)] #![feature(strict_provenance)] +#![feature(trusted_fused)] #![feature(trusted_len)] #![feature(trusted_random_access)] #![feature(try_trait_v2)] diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 5ecd0479971..d174074902a 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -137,44 +137,73 @@ //! } //! vec.truncate(write_idx); //! ``` +use crate::alloc::{handle_alloc_error, Global}; +use core::alloc::Allocator; +use core::alloc::Layout; use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}; use core::mem::{self, ManuallyDrop, SizedTypeProperties}; -use core::ptr::{self}; +use core::num::NonZeroUsize; +use core::ptr::{self, NonNull}; use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec}; -/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the -/// source allocation, i.e. executing the pipeline in place. -#[rustc_unsafe_specialization_marker] -pub(super) trait InPlaceIterableMarker {} +const fn in_place_collectible( + step_merge: Option, + step_expand: Option, +) -> bool { + if DEST::IS_ZST || mem::align_of::() != mem::align_of::() { + return false; + } + + match (step_merge, step_expand) { + (Some(step_merge), Some(step_expand)) => { + // At least N merged source items -> at most M expanded destination items + // e.g. + // - 1 x [u8; 4] -> 4x u8, via flatten + // - 4 x u8 -> 1x [u8; 4], via array_chunks + mem::size_of::() * step_merge.get() == mem::size_of::() * step_expand.get() + } + // Fall back to other from_iter impls if an overflow occured in the step merge/expansion + // tracking. + _ => false, + } +} -impl InPlaceIterableMarker for T where T: InPlaceIterable {} +/// This provides a shorthand for the source type since local type aliases aren't a thing. +#[rustc_specialization_trait] +trait InPlaceCollect: SourceIter + InPlaceIterable { + type Src; +} + +impl InPlaceCollect for T +where + T: SourceIter + InPlaceIterable, +{ + type Src = <::Source as AsVecIntoIter>::Item; +} impl SpecFromIter for Vec where - I: Iterator + SourceIter + InPlaceIterableMarker, + I: Iterator + InPlaceCollect, + ::Source: AsVecIntoIter, { default fn from_iter(mut iterator: I) -> Self { // See "Layout constraints" section in the module documentation. We rely on const // optimization here since these conditions currently cannot be expressed as trait bounds - if T::IS_ZST - || mem::size_of::() - != mem::size_of::<<::Source as AsVecIntoIter>::Item>() - || mem::align_of::() - != mem::align_of::<<::Source as AsVecIntoIter>::Item>() - { + if const { !in_place_collectible::(I::MERGE_BY, I::EXPAND_BY) } { // fallback to more generic implementations return SpecFromIterNested::from_iter(iterator); } - let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { + let (src_buf, src_ptr, src_cap, mut dst_buf, dst_end, dst_cap) = unsafe { let inner = iterator.as_inner().as_into_iter(); ( inner.buf.as_ptr(), inner.ptr, + inner.cap, inner.buf.as_ptr() as *mut T, inner.end as *const T, - inner.cap, + inner.cap * mem::size_of::() / mem::size_of::(), ) }; @@ -203,11 +232,31 @@ where // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the // module documentation why this is ok anyway. - let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap }; + let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap: dst_cap }; src.forget_allocation_drop_remaining(); mem::forget(dst_guard); - let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; + // Adjust the allocation size if the source had a capacity in bytes that wasn't a multiple + // of the destination type size. + // Since the discrepancy should generally be small this should only result in some + // bookkeeping updates and no memmove. + if const { mem::size_of::() > mem::size_of::() } + && src_cap * mem::size_of::() != dst_cap * mem::size_of::() + { + let alloc = Global; + unsafe { + let new_layout = Layout::array::(dst_cap).unwrap(); + let result = alloc.shrink( + NonNull::new_unchecked(dst_buf as *mut u8), + Layout::array::(src_cap).unwrap(), + new_layout, + ); + let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; + dst_buf = reallocated.as_ptr() as *mut T; + } + } + + let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; vec } diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index b2db2fdfd18..40b93b34e18 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -7,7 +7,8 @@ use crate::raw_vec::RawVec; use core::array; use core::fmt; use core::iter::{ - FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce, + FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen, + TrustedRandomAccessNoCoerce, }; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; @@ -339,6 +340,10 @@ impl ExactSizeIterator for IntoIter { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IntoIter {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl TrustedFused for IntoIter {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl TrustedLen for IntoIter {} @@ -423,7 +428,10 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter { // also refer to the vec::in_place_collect module documentation to get an overview #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl InPlaceIterable for IntoIter {} +unsafe impl InPlaceIterable for IntoIter { + const EXPAND_BY: Option = NonZeroUsize::new(1); + const MERGE_BY: Option = NonZeroUsize::new(1); +} #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -- cgit 1.4.1-3-g733a5 From 6e4f98c987f196ed27a3eae9ebb019ec89759f6c Mon Sep 17 00:00:00 2001 From: The 8472 Date: Sat, 29 Apr 2023 12:34:28 +0200 Subject: don't leak items if alloc::shrink panics --- library/alloc/src/vec/in_place_collect.rs | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index d174074902a..20ecc50c4b6 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -225,16 +225,18 @@ where } // The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`. - // This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation + // This is safe because + // * `forget_allocation_drop_remaining` immediately forgets the allocation // before any panic can occur in order to avoid any double free, and then proceeds to drop // any remaining values at the tail of the source. + // * the shrink either panics without invalidating the allocation, aborts or + // succeeds. In the last case we disarm the guard. // // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the // module documentation why this is ok anyway. let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap: dst_cap }; src.forget_allocation_drop_remaining(); - mem::forget(dst_guard); // Adjust the allocation size if the source had a capacity in bytes that wasn't a multiple // of the destination type size. @@ -256,6 +258,8 @@ where } } + mem::forget(dst_guard); + let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; vec -- cgit 1.4.1-3-g733a5 From 7047fb41b6567a43bb2239035c114084807845f6 Mon Sep 17 00:00:00 2001 From: The 8472 Date: Sat, 29 Apr 2023 12:34:52 +0200 Subject: update in-place-iteration module docs --- library/alloc/src/vec/in_place_collect.rs | 33 +++++++++++++++++++++++-------- 1 file changed, 25 insertions(+), 8 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 20ecc50c4b6..90ba1b3a96f 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -6,11 +6,11 @@ //! The specialization in this module applies to iterators in the shape of //! `source.adapter().adapter().adapter().collect::>()` //! where `source` is an owning iterator obtained from [`Vec`], [`Box<[T]>`][box] (by conversion to `Vec`) -//! or [`BinaryHeap`], the adapters each consume one or more items per step -//! (represented by [`InPlaceIterable`]), provide transitive access to `source` (via [`SourceIter`]) -//! and thus the underlying allocation. And finally the layouts of `T` and `U` must -//! have the same size and alignment, this is currently ensured via const eval instead of trait bounds -//! in the specialized [`SpecFromIter`] implementation. +//! or [`BinaryHeap`], the adapters guarantee to consume enough items per step to make room +//! for the results (represented by [`InPlaceIterable`]), provide transitive access to `source` +//! (via [`SourceIter`]) and thus the underlying allocation. +//! And finally there are alignment and size constriants to consider, this is currently ensured via +//! const eval instead of trait bounds in the specialized [`SpecFromIter`] implementation. //! //! [`BinaryHeap`]: crate::collections::BinaryHeap //! [box]: crate::boxed::Box @@ -35,11 +35,28 @@ //! the step of reading a value and getting a reference to write to. Instead raw pointers must be //! used on the reader and writer side. //! -//! That writes never clobber a yet-to-be-read item is ensured by the [`InPlaceIterable`] requirements. +//! That writes never clobber a yet-to-be-read items is ensured by the [`InPlaceIterable`] requirements. //! //! # Layout constraints //! -//! [`Allocator`] requires that `allocate()` and `deallocate()` have matching alignment and size. +//! When recycling an allocation between different types we must uphold the [`Allocator`] contract +//! which means that the input and output Layouts have to "fit". +//! +//! To complicate things further `InPlaceIterable` supports splitting or merging items into smaller/ +//! larger ones to enable (de)aggregation of arrays. +//! +//! Ultimately each step of the iterator must free up enough *bytes* in the source to make room +//! for the next output item. +//! If `T` and `U` have the same size no fixup is needed. +//! If `T`'s size is a multiple of `U`'s we can compensate by multiplying the capacity accordingly. +//! Otherwise the input capacity (and thus layout) in bytes may not be representable by the output +//! `Vec`. In that case `alloc.shrink()` is used to update the allocation's layout. +//! +//! Currently alignments of `T` and `U` must be the same. In principle smaller output alignments +//! could be supported but that would require always calling `alloc.shrink` for those transformations. +//! +//! See `in_place_collectible()` for the current conditions. +//! //! Additionally this specialization doesn't make sense for ZSTs as there is no reallocation to //! avoid and it would make pointer arithmetic more difficult. //! @@ -163,7 +180,7 @@ const fn in_place_collectible( // - 4 x u8 -> 1x [u8; 4], via array_chunks mem::size_of::() * step_merge.get() == mem::size_of::() * step_expand.get() } - // Fall back to other from_iter impls if an overflow occured in the step merge/expansion + // Fall back to other from_iter impls if an overflow occurred in the step merge/expansion // tracking. _ => false, } -- cgit 1.4.1-3-g733a5 From c98070d522d8d12e61219f268ac377aceda30e92 Mon Sep 17 00:00:00 2001 From: The 8472 Date: Sat, 29 Apr 2023 18:31:06 +0200 Subject: relax size and alignment requirements for in-place iteration --- library/alloc/src/vec/in_place_collect.rs | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 90ba1b3a96f..1f03f0d19ec 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -52,8 +52,8 @@ //! Otherwise the input capacity (and thus layout) in bytes may not be representable by the output //! `Vec`. In that case `alloc.shrink()` is used to update the allocation's layout. //! -//! Currently alignments of `T` and `U` must be the same. In principle smaller output alignments -//! could be supported but that would require always calling `alloc.shrink` for those transformations. +//! Alignments of `T` must be the same or larger than `U`. Since alignments are always a power +//! of two _larger_ implies _is a multiple of_. //! //! See `in_place_collectible()` for the current conditions. //! @@ -168,7 +168,7 @@ const fn in_place_collectible( step_merge: Option, step_expand: Option, ) -> bool { - if DEST::IS_ZST || mem::align_of::() != mem::align_of::() { + if DEST::IS_ZST || mem::align_of::() < mem::align_of::() { return false; } @@ -178,7 +178,7 @@ const fn in_place_collectible( // e.g. // - 1 x [u8; 4] -> 4x u8, via flatten // - 4 x u8 -> 1x [u8; 4], via array_chunks - mem::size_of::() * step_merge.get() == mem::size_of::() * step_expand.get() + mem::size_of::() * step_merge.get() >= mem::size_of::() * step_expand.get() } // Fall back to other from_iter impls if an overflow occurred in the step merge/expansion // tracking. @@ -255,12 +255,15 @@ where let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap: dst_cap }; src.forget_allocation_drop_remaining(); - // Adjust the allocation size if the source had a capacity in bytes that wasn't a multiple - // of the destination type size. + // Adjust the allocation if the alignment didn't match or the source had a capacity in bytes + // that wasn't a multiple of the destination type size. // Since the discrepancy should generally be small this should only result in some // bookkeeping updates and no memmove. - if const { mem::size_of::() > mem::size_of::() } - && src_cap * mem::size_of::() != dst_cap * mem::size_of::() + if (const { + let src_sz = mem::size_of::(); + src_sz > 0 && mem::size_of::() % src_sz != 0 + } && src_cap * mem::size_of::() != dst_cap * mem::size_of::()) + || const { mem::align_of::() != mem::align_of::() } { let alloc = Global; unsafe { -- cgit 1.4.1-3-g733a5 From 072b51cbb5b4ee39ae433b5f92a5952054e6caf3 Mon Sep 17 00:00:00 2001 From: The 8472 Date: Mon, 29 May 2023 13:04:26 +0200 Subject: unchecked layout calculations when shrinking during in-place collect Reduces the amount of emitted IR. RawVec has similar optimizations --- library/alloc/src/vec/in_place_collect.rs | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 1f03f0d19ec..e4f96fd7640 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -267,10 +267,20 @@ where { let alloc = Global; unsafe { - let new_layout = Layout::array::(dst_cap).unwrap(); + // The old allocation exists, therefore it must have a valid layout. + let src_align = mem::align_of::(); + let src_size = mem::size_of::().unchecked_mul(src_cap); + let old_layout = Layout::from_size_align_unchecked(src_size, src_align); + + // The must be equal or smaller for in-place iteration to be possible + // therefore the new layout must be ≤ the old one and therefore valid. + let dst_align = mem::align_of::(); + let dst_size = mem::size_of::().unchecked_mul(dst_cap); + let new_layout = Layout::from_size_align_unchecked(dst_size, dst_align); + let result = alloc.shrink( NonNull::new_unchecked(dst_buf as *mut u8), - Layout::array::(src_cap).unwrap(), + old_layout, new_layout, ); let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; -- cgit 1.4.1-3-g733a5 From 115eac03bbd2a4b8b301c3bc627bd0f2c1235525 Mon Sep 17 00:00:00 2001 From: Jake Goulding Date: Sat, 25 Nov 2023 15:45:44 -0500 Subject: Address unused tuple struct fields in the standard library --- library/alloc/src/boxed/thin.rs | 1 + 1 file changed, 1 insertion(+) (limited to 'library/alloc/src') diff --git a/library/alloc/src/boxed/thin.rs b/library/alloc/src/boxed/thin.rs index f83c8f83cc9..a8005b7067d 100644 --- a/library/alloc/src/boxed/thin.rs +++ b/library/alloc/src/boxed/thin.rs @@ -171,6 +171,7 @@ struct WithHeader(NonNull, PhantomData); /// An opaque representation of `WithHeader` to avoid the /// projection invariance of `::Metadata`. #[repr(transparent)] +#[allow(unused_tuple_struct_fields)] // Field only used through `WithHeader` type above. struct WithOpaqueHeader(NonNull); impl WithOpaqueHeader { -- cgit 1.4.1-3-g733a5