How often is memory copied/moved around?

#1

I had a question, given:

let mut v: Vec<T>;
assert_eq!(v.capacity(), v.len());
v.insert(middle, val);

how much memory would be copied around. The vector needs to grow, so it might grow first, copying its whole contents to the new memory, and then do the insert, moving the [middle, len()) elements one to the right. Alternatively, it might copy [0, middle) to the new memory first, insert val, then copy [middle, len()). The difference being, the first approach moves the [middle, len) elements twice, while the second approach moves them only once.

In C++ this question is trivial to answer: define a T with a move constructor that increases an internal count on every move, perform the op, print out the count.

I have no idea how to simply answer this question in Rust, or more in general, how to find out where moves / memcpy-s due to move actually happen.

This is particularly worry-some, since in my experience Rust often memcpys too much memory around all the time. I have to figure this out things before, and the only reliable method I have is… using godbolt to introspect the assembly.

In this case, https://rust.godbolt.org/z/oRJg7V , I need to basically know that what’s happening here is that the vector is first, realloc into new memory (whole vector moved once in the worst case), and then the tail is moved by one to the right (memmove), and then the element is inserted. As opposed to using realloc_in_place, and if that fails, move head, insert, move tail.

I could obviously go ahead and look and the source code, but what I’m looking for is for an easy way to “debug” (or add tests) for performance issues related to unnecessary memcpys/memmoves. As in, how Vec::insert actually works is not the point here, the point is how would I add a test to make sure that it works correctly.

1 Like
#2

That’s what currently happens (if reserve(1)'s triggers an allocator realloc (although increasing a Vec's capacity does not guarantee an "actual Allocator realloc"), it will copy the whole slice); but you are right, the code could be optimized into skipping the [middle, len()) first copy. You could file an issue to get that changed.

#3

As mentioned, the problem isn’t that the implementation of insert is wrong. The problem is that there is no way to test whether the implementation is wrong.

Suppose we fixed the implementation of insert, what would be add as a regression test to make sure that it is not changed back by accident to the previous implementation ?


The consequences of this issue are further reaching than a broken Vec::insert. Nobody can easily test / inspect these things, such that unnecessary memcpy/memmoves happen all the time in Rust, at least when comparing Rust with C or C++.

1 Like