Move-assignment slower than copy-assignment — bug,

Question

I recently realized that the addition of move semantics in C++11 (or at least my implementation of it, Visual C++) has actively (and quite dramatically) broken one of my optimizations.

Consider the following code:

#include <vector>
int main()
{
    typedef std::vector<std::vector<int> > LookupTable;
    LookupTable values(100);  // make a new table
    values[0].push_back(1);   // populate some entries

    // Now clear the table but keep its buffers allocated for later use
    values = LookupTable(values.size());

    return values[0].capacity();
}

I followed this kind of pattern to perform container recycling: I would re-use the same container instead of destroying and recreating it, to avoid unnecessary heap deallocation and (immediate) reallocation.

On C++03, this worked fine -- that means this code used to return 1, because the vectors were copied elementwise, while their underlying buffers were kept as-is. Consequently I could modify each inner vector knowing that it could use the same buffer as it had before.

On C++11, however, I noticed that this results in a move of the right-hand side onto the left-hand side, which performs an element-wise move-assignment to each vector on the left-hand side. This in turn causes the vector to discard its old buffer, suddenly reducing its capacity to zero. Consequently, my application now slows down considerably due to excess heap allocations/deallocations.

My question is: is this behavior a bug, or is it intentional? Is it even specified by the standard at all?

Update:

I just realized that correctness of this particular behavior may depend on whether or not a = A() can invalidate iterators that point to the elements of a. However, I don't know what the iterator invalidation rules for move-assignment are, so if you're aware of them it may be worth mentioning those in your answer.

Answer 1

C++11

The difference in the behaviours in the OP between C++03 and C++11 are due to the way move assignment is implemented. There are two main options:

1. Destroy all elements of the LHS. Deallocate the LHS's underlying storage. Move the underlying buffer (the pointers) from the RHS to the LHS.

2. Move-assign from the elements of the RHS to the elements of the LHS. Destroy any excess elements of the LHS or move-construct new elements in the LHS if the RHS has more.

_{I think it is possible to use option 2 with copies, if moving is not noexcept.}

Option 1 invalidates all references/pointers/iterators to the LHS, and preserves all iterators etc. of the RHS. It needs O(LHS.size()) destructions, but the buffer movement itself is O(1).

Option 2 invalidates only iterators to excess elements of the LHS which are destroyed, or all iterators if a reallocation of the LHS occurs. It is O(LHS.size() + RHS.size()) since all elements of both sides need to be taken care of (copied or destroyed).

As far as I can tell, there is no guarantee which one happens in C++11 (see next section).

In theory, you can use option 1 whenever you can deallocate the underlying buffer with the allocator that is stored in the LHS after the operation. This can be achieved in two ways:

• If two allocators compare equal, one can be used to deallocate the storage allocated via the other one. Therefore, if the allocators of LHS and RHS compare equal before the move, you can use option 1. This is a run-time decision.

• If the allocator can be propagated (moved or copied) from the RHS to the LHS, this new allocator in the LHS can be used to deallocate the storage of the RHS. Whether or not an allocator is propagated is determined by allocator_traits<your_allocator :: propagate_on_container_move_assignment. This is decided by type properties, i.e. a compile-time decision.

---

C++11 minus defects / C++1y

After LWG 2321 (which is still open), we have the guarantee that:

no move constructor (or move assignment operator when allocator_traits<allocator_type> :: propagate_on_container_move_assignment :: value is true) of a container (except for array) invalidates any references, pointers, or iterators referring to the elements of the source container. [ Note: The end() iterator does not refer to any element, so it may be invalidated. — end note ]

This requires that move-assignment for those allocators which are propagated on move assignment has to move the pointers of the vector object, but must not move the elements of the vector. (option 1)

The default allocator, after LWG defect 2103, is propagated during move-assignment of the container, hence the trick in the OP is forbidden to move the individual elements.

---

My question is: is this behavior a bug, or is it intentional? Is it even specified by the standard at all?

No, yes, no (arguably).

Answer 2

See this answer for a detailed description of how vector move assignment must work. As you are using the std::allocator, C++11 puts you into case 2, which many on the committee considered a defect, and has been corrected to case 1 for C++14.

Both case 1 and case 2 have identical run time behavior, but case 2 has additional compile-time requirements on the vector::value_type. Both case 1 and case 2 result in memory ownership being transferred from the rhs to the lhs during the move assignment, giving you the results you observe.

This is not a bug. It is intentional. It is specified by C++11 and forward. Yes, there are some minor defects as dyp pointed out in his answer. But none of these defects will change the behavior you are seeing.

As was pointed out in the comments, the simplest fix for you is to create an as_lvalue helper and use that:

template <class T>
constexpr
inline
T const&
as_lvalue(T&& t)
{
    return t;
}

// ...

// Now clear the table but keep its buffers allocated for later use
values = as_lvalue(LookupTable(values.size()));

This is zero-cost, and returns you to precisely the C++03 behavior. It might not pass code review though. It would be clearer for you to iterate through and clear each element in the outer vector:

// Now clear the table but keep its buffers allocated for later use
for (auto& v : values)
    v.clear();

The latter is what I recommend. The former is (imho) obfuscated.