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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <aAkPXBHNDugnXrhc@Mac.home>
Date: Wed, 23 Apr 2025 09:03:40 -0700
From: Boqun Feng <boqun.feng@...il.com>
To: Alexandre Courbot <acourbot@...dia.com>
Cc: Alice Ryhl <aliceryhl@...gle.com>, Danilo Krummrich <dakr@...nel.org>,
	Miguel Ojeda <ojeda@...nel.org>,
	Alex Gaynor <alex.gaynor@...il.com>, Gary Guo <gary@...yguo.net>,
	Björn Roy Baron <bjorn3_gh@...tonmail.com>,
	Benno Lossin <benno.lossin@...ton.me>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Trevor Gross <tmgross@...ch.edu>,
	Joel Fernandes <joelagnelf@...dia.com>,
	John Hubbard <jhubbard@...dia.com>, rust-for-linux@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] rust: alloc: implement `extend` for `Vec`

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