Vec::recycle

[llogiq]

Proposal

Problem statement

Re-using a Vec as buffer sometimes runs into lifetime issues. A recycle method that clears the Vec and essentially transmutes it into another Vec (using into_raw_parts & from_raw_parts) with an item type that has the same length and alignment can help here.

Motivating examples or use cases

A blog post at databento shows the following:

let mut buffer: Vec<&[u8]> = Vec::new();
for source in sources {
    let data: Vec<u8> = source.fetch_data(); // ← binding `data` declared here
    buffer.extend(data.split(splitter)); // ← borrowed value does not live long enough
    process_data(&buffer);
    buffer.clear();
}

They cite this as one of the reasons not to rewrite their code in Rust.

Solution sketch

In the closed RFC PR #2802, @golddranks suggests a Vec::recycle function (implementation is fairly trivial and omitted for brevity):

impl<T> Vec<T> {
    /// This clears out this `Vec` and recycles the allocation into a new `Vec`.
    /// The item type of the resulting `Vec` needs to have the same size and
    /// alignment as this `Vec`.
    ///
    /// # Panics
    /// This function will panic if the item type of the result does not have
    /// the same size or alignment (per [`std::mem::size_of`] and
    /// [`std::mem::align_of`], respectively) as the consumed type's items.
    ///
    /// # Examples
    /// ```
    ///# let inputs = ["a b c", "d e f"];
    ///# fn process(_: &[&str]) {}
    /// let mut storage: Vec<&[&str]> = Vec::new();
    /// for input in inputs {
    ///     let mut buffer = storage.recycle();
    ///     buffer.extend(input.split(" "));
    ///     process(&buffer);
    ///     storage = buffer.recycle();
    /// }
    /// ```
    pub fn recycle<U>(self) -> Vec<U> {
        ..
    }

Alternatives

An alternative shorter name would be "reuse". Both names work for me. I decided to suggest recycle because that was what @golddranks' RFC went with, and that had already some discussion.

Yes, this can be written using existing APIs. The wild linker blog even has a section on "Buffer reuse" that shares a fully safe implementation using an iterator-based hack. However, that hack is very much not obvious nor discoverable. And yes, there is a recycle_vec crate that implements the pattern.

Links and related work

• RFC PR #2802
• recycle_vec
• T-Libs discussion on Zulip

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[ChayimFriedman2]

Should the method cause a post-monomorphization error when the size/alignment don't match instead of panic?

[llogiq]

I'd be fine with that if we can get a helpful error message out of it.

[VorpalBlade]

Should the method cause a post-monomorphization error when the size/alignment don't match instead of panic?

As a user I would much prefer any sort of compile time error to a runtime panic. So I would say yes.

[pitaj]

nit: generic parameter on the function should be something other than T

[pitaj]

Does the item type need to have the same size? As long as it is some factor of the current item type's size, it should be possible to reduce the item size, correct?

[ChayimFriedman2]

Theoretically it is possible to use any size as long as the capacity is a multiple of it, the question is whether we want that (it also makes it impossible to detect errors at compile time).

[scottmcm]

Hmm, it feels like it'd be pretty fragile to have it fail to compile or runtime panic when it's looking at explictly-not-guaranteed layout information -- as well as at explictly-not-guaranteed exact capacity numbers. (I don't want bug reports for "we changed the Vec growth strategy and now a bunch of recycle calls are panicking".)

Perhaps we should save the nicer name for something with a trait bound to promise that it'll work, and thus wouldn't need the # Panics section? (With #[marker] traits we could do such a bound quite nicely, actually, adding more things like safe-transmute-based ones later without breaking anyone's existing implementations.)

That would, to me, suggest that if we want to do something short-term without such a bound it should be something like recycle_or_new that always works, but opportunistically re-uses the allocation when possible. Then it would be up to a lint to warn you that "hey, those types have different alignments so it's never going to do anything useful" or similar.

[ChrisDenton]

Hm, I think it's just fine to only support cases where both size and alignment match for the initial version. Maybe this requirement could be loosened in the future but let's not put the cart before the horse. As far as I can tell after following the links in the OP, it would be fine to have:

const {
    assert!(size_of::<T>() == size_of::<U>());
    assert!(align_of::<T>() == align_of::<U>());
}

A panicky version (or a version that returns a Result) may also be useful but that seems more niche and not necessary to fulfil the current requirements (as I understand them).

[programmerjake]

if it supported reducing the element size to a divisor of the original element size but not changing the alignment or increasing size, there wouldn't need to be any panicking checks, all the checks could be done at compile time:

impl<T> Vec<T> {
    pub fn recycle<U>(mut self) -> Vec<U> {
        self.clear();
        const MULTIPLIER: usize = {
            assert!(align_of::<T>() == align_of::<U>());
            let t = size_of::<T>();
            let u = size_of::<U>();
            assert!(t.is_multiple_of(u));
            if t == 0 {
                assert!(u == 0);
                1
            } else {
                t / u
            }
        };
        let capacity = self.capacity() * MULTIPLIER; // can't overflow
        let ptr = ManuallyDrop::new(self).as_mut_ptr().cast::<U>();
        unsafe { Vec::from_raw_parts(ptr, 0, capacity) }
    }
}

[llogiq]

Yes, reducing the size by an integer factor is possible. However, as we see from the code, that opens up a can of worms special cases that we'd need to document and maintain. Also it would make the marker trait machinery we'd need to get a compile time error far more complex. I'd like to see a motivating use case for that in the wild before I'd invoke this complexity.

Using a lint to get a compile time error is a clever option. I must admit I hadn't thought of that 🤦. However, unless we make it a forbid compiler lint, we should still keep the asserts and panic because people might #[allow] or simply not run the lint.

[programmerjake]

well, we already have reducing the size by an integer factor for vectors of arrays: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.into_flattened

For the trait marker machinery you speak of, I don't expect it to be much harder to have a T: SizeIsMultipleOf<U> than it would be to have a T: SizeIsSameAs<U>, both of which either require generic const exprs or compiler magic. I think we probably don't need any traits.

[VorpalBlade]

Why do you need a marker trait, rather than a const assert? Both will generate compile time errors as far as I understand? And post-mono errors is nothing to be afraid of.

[hanna-kruppe]

Here’s my classification of the options discussed so far:

• A marker trait can be designed to allow only those element type changes that are in some way (by the language and/or by the author of the type) guaranteed to work. Just lifting the “check size and align” into a more or less magic trait doesn’t achieve this but an explicit-opt-in marker trait prevents cross-crate semver hazards. The downside is that buffer reuse isn’t possible whenever the trait isn’t implemented or the bound can’t be added.
• A post-mono error or runtime panic based on actual size and alignment allows the most cases of buffer reuse (in contrast to an opt-in trait). The flip side is that people can depend on it working when it’s not guaranteed by language and/or authors of library types involved.
• Doing the buffer reuse opportunistically and falling back to reallocation or Vec::new() when it’s not possible, is the most robust in that you can always use it and it’ll never break your program. Of course, people would generally prefer a guarantee that the buffer is actually reused.

Note that the second and third options are interchangeable in that you can build either out of the other with a little bit of safe code (though building 3 out of the post-mono-error variant is very annoying and non-obvious, and probably depends on undocumented details of how const eval and monomorphization interact).