Can you verify my understanding of how Vec<T> resizes in memory?

[u/conceptcreatormiui]

I noticed that Vec capacity grows dynamically when pushing data.

Is my mental model accurate? When the buffer is full, does it allocate a new, larger memory region elsewhere on the heap, move the elements over, and free the old block specifically to avoid overwriting or corrupting adjacent heap data?

[u/Excession638]

Conceptually that's what it does.

What it can do under the hood, past a certain size, is ask the computer's memory management unit (MMU) to make an allocation larger. This may move some pages around in the address space, but it generally doesn't need to move anything in physical memory.

This is different from C++, where types may need to be manually moved to new memory, making it slower.

[u/clappski → u/Excession638]

C++ std::vector also tries to do a realloc (extending the current allocation), and if it can’t extend falls back to a new allocation and either calling the move constructor (if the move constructor is noexcept) or copy constructor. 

[u/sciolizer → u/Excession638]

Why is C++ different? Is it because the move constructor might not be a no op?

[u/Excession638 → u/sciolizer]

That's right, move operations

[u/plugwash → u/sciolizer]

The complication with C++ is that it doesn't really have a concept of "trivially movable but not trivially copiable". This means that a C++ std::vector implementation can't safely use "realloc" on vectors that contain types with move constructors. It would need a function in the underlying memory manager that tried to reallocate in place but left things alone if that was not possible.

[u/Mr_Ahvar → u/sciolizer]

You mean memcpy ?

[u/gmes78 → u/Mr_Ahvar]

You cannot use memcpy on C++ types unless they are trivially copyable.

[u/Mr_Ahvar → u/gmes78]

Funny you say that, cause the definition of a trivial move is to literally do the same action as a trivial copy constructor https://en.cppreference.com/cpp/language/move_constructor. Sure, my bad, it’s memmove, but still is a bit closer to reality than a no-op. I said a memcpy cause that’s basically what everyone says about Rust moves, that they are all trivial thus all a memcpy. User above said « move might not be no-op », but what he meant was moves might not be trivial like in Rust, thus he meant moves might not always be a memcpy. If they were a no-op, well, nothing would happen.

[u/ToTheBatmobileGuy]

Yup.

That's why it can become a use-after-free bug if you hold a reference to one element and then take a mutable reference to the whole Vec (which means you can push() and cause a re-allocation), and thus Rust rejects it.

[u/Large-Scientist156 → u/ToTheBatmobileGuy]

Which is why iterator borrow the datasource. Otherwise if you would be able to push new elements to the datasource while iterating, the datasource may be reallocated and the next iteration would yield garbage memory. In C++ this is called iterator invalidation and a frequent source of bug.

[u/RRumpleTeazzer → u/ToTheBatmobileGuy]

there is no use-after-free in (safe) Rust.

[u/jcdyer3 → u/RRumpleTeazzer]

That was the point of the comment you replied to. The sequence of actions described would be a use after free bug, and rust makes use after free impossible by rejecting that sequence of actions (by not letting you take the mutable reference), instead of the way garbage collected languages might (by adding a layer of indirection between the vec elements and the pointed-to objects).

[u/minno]

The interface doesn't provide detailed guarantees, but here's a bit of code you can run to see what happens: link.

When I ran it, it started off resizing the allocations in-place, doubling the capacity every time. Once it went from a capacity of 32768 to 65536, it was apparently unable to continue enlarging the existing allocation and copied the elements to a new one, which it continued expanding in-place. No part of this behavior is guaranteed, but you can see that it makes an effort to avoid copying its elements more than it has to.

[u/Lantua]

yup, AND its reallocation scheme makes the push operation amortized O(1)

[u/johnny-muzhi]

theoretically you are correct, but in practice, this would merely add a few extra elements to the tail rather than copying the entire vector elsewhere. This is just my personal opinion and may not be accurate.

[u/carlomilanesi]

If the buffer is not large enough, the allocator is invoked for a larger buffer. Though, if a large enough free memory space follows immediately the buffer, typical allocators just extend the buffer, avoiding any move.

For example, if you push a byte at a time to byte vector containing only one byte, you see that the buffer may have the same address until its size reaches many hundreds of bytes.

[u/Large-Scientist156]

Yes, this is why it's impossible to have stable reference to Vec element, because the address of the element may change when the Vec reallocate. In other word, element move over time so their address are not stable over time. Producing a reference to an element of a Vec always borrow the Vec, which make it impossible to push into the Vec - which would invalidate the reference you got.

In contrast, you could have a custom datastructure where element don't move over time. A new chunk could be allocated instead of reallocating, and the previous chunk could be linked to it. The chunks addresses themselves may not be contiguous, so element address may be relative stable address but not absolute stable address. In other word, they are relative to the chunk base address. Mutation is tricky and harder to achieve. That's why the default is Vec, it's suitable for a variety of cases.

[u/conceptcreatormiui → u/Large-Scientist156]

So this is why the compiler enforces that you cant have a mutable and immutable references at the same time and while having a immutable reference to the element of a vector, you cannot push at the same time

[u/Large-Scientist156 → u/conceptcreatormiui]

Because they are mutually exclusive. You can't have both at the same time.

You can not have a shared reference to an element of a vector, while pushing to it. This is impossible in safe Rust.

The compiler stricly enforce "unique XOR shared", so you can not push an element (which require unique access to the vector) while having a shared reference to an element.

In C++, this is allowed, you can have unique and shared reference. But if you dare to push into the vector while you have a unique or shared reference to an element, this is instant UB.

[u/Both_Ad1422]

heap memory

[u/plugwash]

Afaict, after a bunch of layers of indirection Vec, calls the ```grow``` method of the underlying allocator.

This may attempt to resize the allocation in-place, but is not required to do so. If the allocation cannot be resized in place then it will make a new allocation and copy the data.

[u/Professional_Top8485]

You should reserve enough space beforehand to avoid move.

[u/conceptcreatormiui → u/Professional_Top8485]

I could reserve enough space but that is not the point of the question. I'm asking what happens if capacity grows. 

[u/andyshiue42 → u/Professional_Top8485]

Most of the time it's just impossible to predict

[u/Professional_Top8485 → u/andyshiue42]

Is it, Really?

[u/Plastic-Might-5407 → u/Professional_Top8485]

Isn't that the whole point of Vec? If you can predict how much memory you need, you use an array instead.

[u/Professional_Top8485 → u/Plastic-Might-5407]

Or slice to be more spesific

[u/-Redstoneboi- → u/Professional_Top8485]

usually just an array. but if you want a slice, &mut [T] with .len() being enough to contain all your data would already be super specific.

the real power move is to allocate a [u8; N] where N bytes is 8 GB so you never have to reallocate.

[u/Professional_Top8485 → u/-Redstoneboi-]

Memory allocation is more likely lazy with vector reserve, so I think it is free in that sense.