How does std::vec::shrink_to_fit work in Rust?

Question

Does std::vec::shrink_to_fit allocate a new, smaller vec.len() buffer of data, copy to it, and destruct the old buffer, or does it somehow indicate to the memory allocator that the uninitialised part of the buffer can be de-allocated, and simply release that part of the memory? Is that even possible? Does that depend on the memory allocator?

And a tangential question which I apologise to ask here, but if that's possible, why don't we, for example, implement popping from the front of a vector as a simple "release std::mem::size_of<T>() amount of memory from the start of the buffer, and increment our pointer by one", rather than shifting all our elements by one?

Hagler

Answer 1

The Vec::shrink_to_fit() uses the Allocator::shrink() method to shrink the allocation (via the internal RawVec::shrink_to_fit(), method which may simply resize the existing allocation in-place without moving the data, or it might return a different memory block.

You can't pop from the front of a vector by re-sizing it, because memory allocations can't have their start address changed, only their length.

Placate

Answer 2

The beautiful thing about rust's documentation is that you can see for yourself! Rust's documentation includes the source code of whole crate and standard library is written very well and you can read it's source code and understand it (and learn a lot from it) even if you are not rust guru.

So let's see what is the answer to your question.

• To the right of method Vec::shrink_to_fit you have a link to source code
• It directs us to this method implementation
• there we are calling shrink_to_fit(self.len) on self.buf which is of type RawVec
• In the file tree on the left we can go to raw_vec.rs
• On line #357 we have implementation of shrink_to_fit for RawVec. It in turn calls RawVec::shrink which is implemented below on line #430
• There we can finally see that on line #442 this function calls self.alloc.shrink. It is a method on unstable Allocator trait

Now this function can be implemented in different ways by different allocators. Some might do a realloc, and some might perform actual shrinking of the memory and do not memmove anything. To see what your program uses you must learn more about your allocator.

If you look at Allocator's methods you will see that there is no method shrink_from_start. This is because that operation isn't a common one and would be much harder to implement in an allocator. That's why using it to implement Vec::remove(0) wouldn't have much sense.

Heighttopaper

I actually tried to, but I gave up right after RawVec::shrink since it got a bit too nested for me and didn't look for what alloc.shrink is😅 – Hagler

Great detailed answer, this is what I did in order to try and answer the question. :) There's no other language/platform with such easy and rich docs and source access like this. Really awesome. – Placate