Re: [PATCH v3] rust: alloc: implement `extend` for `Vec`

[Boqun Feng <boqun.feng@gmail.com>]

On Wed, Apr 23, 2025 at 06:40:07PM +0900, Alexandre Courbot wrote:
> On Wed Apr 23, 2025 at 5:51 PM JST, Alice Ryhl wrote:
> > On Wed, Apr 23, 2025 at 10:02:58AM +0900, Alexandre Courbot wrote:
> >> The problem I see is that if you try and do something like:
> >> 
> >>   vec.extend((0..10).into_iter().skip(2));
> >> 
> >> with the standard library, then the use of `skip` will remove the
> >> `TrustedLen` implementation from the resulting iterator and
> >> `extend_desugared` will be called instead of `extend_trusted`, which
> >> could add some unwanted (and unexpected) overhead.
> >> 
> >> If we want an implementation of `extend` as simple as "confidently
> >> increase the length of the vector and copy the new items into it, once",
> >> then we need a trait that can be implemented on both shrinking and
> >> extending adapters. Anything else and we might trick the caller into a
> >> code path less efficient than expected (i.e. my original version, which
> >> generates more core even for the obvious cases that are `extend_with`
> >> and `extend_from_slice`). Or if we rely on `TrustedLen` solely in the
> >> kernel, then `extend` could not be called at all with this particular
> >> iterator.
> >> 
> >> There is also the fact that `TrustedLen` is behind a nightly feature,
> >> which I guess is another obstacle for using it.
> >
> > The stdlib alloc crate relies on specialization to speed up methods
> > related to iterators. We can't use specialization, so losing these
> > optimizations is simply a cost of not using the upstream alloc library
> > that we have to accept.
> 
> Yeah I was surprised to see
> 
>   impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
>   where
>       I: Iterator<Item = T>
> 
> and
> 
>   impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
>   where
>       I: TrustedLen<Item = T>
> 
> in the standard library, which clearly looks like an overlap. Didn't
> know it was relying on a non-standard feature.
> 
> That's going to limit what we can do in the kernel, but nonetheless if
> we can support only the cases that can be optimized I think we would
> have our bases covered.

I think if it's a critical path and we really need the performance, we
can use a non-standard/non-stable feature or get that stabilized.

Regards,
Boqun