Does the map_in_place crate do something the compiler can't already do?

I've been working to get a Vec<Box<dyn TraitObject>> set up to allow shadowing each trait object into its next state (i.e. requiring no additional allocation, behind the pointer anyway). My current working solution, which I think is effectively mapping in-place, can be found here. It might also be worth noting that the end goal is to use rayon's par_iter() on this collection, if it matters.

However, in my searching I found out there may have been a map_in_place() function for vectors quite a while ago (Rust <1.4), and also that there is the map_in_place crate which is still at version 0.1.0 (so it's either old or already perfect?).

Thus, I wonder if the current state of things is because it's something the compiler already does. Was the old Vec method removed because it didn't add anything? Does the map_in_place crate actually add anything that plain, standard, safe Rust isn't already doing?

Perhaps someone with more detailed knowledge of compiler implementations can weigh in. If not, I suppose one way to check would be implementing both with and without the map_in_place crate and comparing the machine code...

I believe currently the vec.into_iter().map().collect() idiom from Vec<T> to Vec<U> gets optimized into a simple in-place mutating loop as long as size_of::<T>() == size_of::<U>() && align_of::<T>() >= align_of::<U>(). Like most optimizations, I don't think this is guaranteed to happen, though.

3 Likes

Yeah, that's what I would expect to be the case, but I just thought I'd ask in case anyone knew for sure. The compiler can work out some pretty impressive optimizations, but I'd hate for it to not work for some reason I haven't managed to find out about yet.

And in my case I don't really have to worry about size changes, both because of the Boxes and moreso because the concrete inner types held by the Boxes won't change; each Box<T as dyn TraitObject> should just get shadowed into the exact same allocated type Box<T as dyn TraitObject>.

The alignment actually has to be equal in order to reuse the allocation.

Currently vec.into_iter().map().collect() is done in place thanks to a specialization in the standard library, not due to compiler optimizations.

4 Likes

Excellent, I'll take that to mean I can trust that Rust is doing what I think it is (in this specific instance).

Yeah, in the current version of the compiler it will reliably be done in place, however there's no guarantee it won't be removed in a future version (although that would be pretty unwanted and unlikely).

1 Like

That sounds cool, how is such specialization implemented?

The code responsible for what you're interested in, along with some comments, is in the file rust/in_place_collect.rs at master · rust-lang/rust · GitHub

In short in core there are two traits that are implemented for adapters that transitively contain a std::vec::IntoIter and always advance it at least once when they yield an element. Then the implementation of FromIterator for Vec is specialized for these adapters in such a way that they read one element, advancing the underlying IntoIter and thus "freeing up" at least one slot to write the result element.

The traits are declared here:

If you want to dig deeper I also suggest looking at the other files in the directory of the first link, in particular:

4 Likes

Awesome, thanks!