Qt and Trivial Relocation (Part 2) Relocation and Erasure

09.05.2024 Giuseppe D'Angelo 4 comments

In the last post of this series we discussed the usage of trivial relocation in order to optimize move construction followed by the destruction of the source.

To quickly recap:

• objects of certain datatypes (“trivially relocatable” types) can be moved in memory by simply moving bytes;
• this can be used to optimize certain bulk operations (such as vector reallocation);
• if we have a custom datatype which is trivially relocatable, we can mark it using the Q_DECLARE_TYPEINFO macro so that Qt considers it as such.

In this instalment we are going to explore the relationships between trivial relocation and move assignments.

A different example: vector erasure

Last time we started our investigation of trivial relocation by considering an important use-case: reallocating a vector. This happens when a vector reaches its capacity, but more storage is needed.

Let’s now consider a different operation: erasing an element from the middle of a QVector.

How do we go about it?

QVector<QString> v{ "A", "B", "C", "D" };

v.erase(v.begin() + 1);  // remove B, second element

We can easily come up with a few possible implementation strategies:

1. We could move-assign the “tail” one position to the left, one element at a time, left from right:

Move-assign C over B, move-assign D over (moved-from) C, and so on.

At the end of the sequence of move operations, we would end up with the expected contents in the vector (B has been overwritten), however there is a last moved-from element still around:

After the move assignments, there is a tail of moved-from element(s) that needs to be destroyed.

Since it’s at the tail, we can easily destroy it, update our bookkeeping, and that’s it:

Almost done: destroy the last element, and reduce size by 1.

2. Alternatively, we could std::rotate the tail of the vector so that B (the element to destroy) ends up at the end:

… it’s a rotate!

std::rotate will execute a series of swaps in order to, well, perform a rotation of the tail. After it’s done, we’re left with an element in the last position that needs to be destroyed (in this case, it’s B itself):

We still have a tail of elements to destroy.

Just like the previous example, we can then simply destroy the last element, and update our vector’s bookkeeping (its size has decreased by 1):

Destroying the last element.

Of course, there are other possibilities as well.

“At the end of the day”, one may think, “aren’t these all equivalent?”: they all end up removing B from the vector, and they just differ in how to get there. So why do we even bother discussing this? Surely Qt has chosen an efficient strategy, and whatever it is, it’s just an implementation detail.

… is it truly? As we’ll soon discover, things are way more complicated than this.

Trivial Relocatability for erasure

Let’s go back to our discussion about trivial relocability. If you read the last blog post, you should know that QString is trivially relocatable: we can move QString objects in memory by moving their byte representation. (This is not necessarily the case for std::string.)

You shouldn’t then be surprised by what comes next: QVector can use trivial relocation to optimize vector erasure for these types!

How, exactly? Let’s go back to our QVector<QString> from which we want to erase the second element:

In this case, QVector first destroys the element to be removed:

Then, we need to compact the tail over the destroyed element. Since QString is trivially relocatable, this is done via a memcpy as well! Well, to be pedantic: a memmove, since the source and destination ranges overlap.

After this we’re basically done: there’s no last element to destroy, all we need to do is update the vector’s bookkeeping.

Once more, this optimization constitutes a massive performance gain compared to having to shuffle individual elements around. You can see it in action inside QVector here.

Is this optimization legal? What was relocation again?

In the first instalment we defined relocation as the combination of move construction, followed by the destruction of the source. We also defined trivial relocation as “the same effects, realized by copying bytes” — in particular, without any calls to a type’s move constructor or destructor.

Our motivating example was optimizing the reallocation of a vector, where indeed the vector has move construct elements into the new storage, and destroy elements in the old storage.

However, in order to optimize erasure, we cannot formally use this definition! The point is that erasure does not use move construction at all! It uses move assignments (and destructions). We must therefore carefully reason about what we are doing.

The question we should ask ourselves at this point is: is Qt making an illegal optimization here? Or instead, is it that our definition of relocability needs some refinement?

Sorry for the cliffhanger, but you’ll have to wait for the next post to solve this mystery!

Thank you for reading so far.

Overview about all installments:

• Part 1
• Part 3
• Part 4