移动分配比拷贝分配慢 - 错误，功能或未指定？ [英] Move-assignment slower than copy-assignment -- bug, feature, or unspecified?

问题描述

我最近意识到，在C ++ 11（或至少我的实现，Visual C ++）添加移动语义已经积极（非常显着）我的优化之一。 / p>

请考虑以下代码：

  #include< vector& 
 int main（）
 {
 typedef std :: vector< std :: vector< int> >查找表; 
 LookupTable values（100）; // make a new table 
 values [0] .push_back（1）; //填充一些条目
 
 //现在清除表，但保留其缓冲区以供以后使用
 values = LookupTable（values.size（））; 
 
返回值[0] .capacity（）; 
} 
  

我按照这种模式执行容器回收：我将重新使用相同的容器，而不是销毁和重新创建它，以避免不必要的堆释放和（立即）重新分配。

在C ++ 03，工作正常 - 这意味着这个代码用于返回 1 ，因为向量是复制元素的，而它们的底层缓冲区保持原样。因此，我可以修改每个内部向量知道它可以使用与之前相同的缓冲区。

然而，在C ++ 11，我注意到，将右侧的移动移动到左侧，对左侧的每个向量执行元素方式的移动分配。这反过来导致向量丢弃其旧缓冲区，突然将其容量降低到零。因此，我的应用程序现在由于过多的堆分配/释放而显着减慢。

我的问题是：这是一个错误，还是故意？

更新：

我只是意识到这个特定的正确性行为可以取决于 a = A（）是否可以使指向 a 的元素的迭代器无效。但是，我不知道移动赋值的迭代器无效规则是什么，所以如果你知道它们，可能值得一提的是你的答案中的那些。

解决方案

C ++ 11

C ++ 03和C ++ 11之间的OP行为的差异到实现移动分配的方式。
有两个主要选项：

1. 销毁LHS的所有元素。取消分配LHS的底层存储。将底层缓冲区（指针）从RHS移动到LHS。




2. 将RHS的元素移动分配到LHS的元素。

如果RHS有更多的元素，则销毁LHS的任何多余元素或移动构建LHS中的新元素。 sub>如果移动不是noexcept，我认为可以使用选项2。

选项1使所有引用/指针/迭代器无效LHS，并保留RHS的所有迭代器等。它需要 O（LHS.size（））破坏，但是缓冲区本身是O（1）。

选项2仅使被破坏的LHS的多余元素的迭代器无效，或者如果LHS的重新分配发生，则使所有迭代器无效。它是 O（LHS.size（）+ RHS.size（）），因为双方的所有元素都需要处理（复制或销毁）。

据我所知，不能保证在C ++ 11中会发生什么（见下一节）。

理论上，每当您可以使用存储在LHS中的操作之后的分配器取消分配底层缓冲区时，您可以使用选项1。这可以通过两种方式实现：

• 如果两个分配器比较相等，一个可以用于释放通过另一个。因此，如果LHS和RHS的分配器在移动之前比较相等，则可以使用选项1.这是运行时决策。




• 可以从RHS传播（移动或复制）到LHS，LHS中的这个新的分配器可以用于释放RHS的存储。是否传播分配器由 allocator_traits< your_allocator :: propagate_on_container_move_assignment 确定。这由类型属性决定，即编译时决定。

---

< h1> C ++ 11减去缺陷/ C ++ 1y

LWG 2321 （尚未开放），我们保证：

无移动构造函数（或
allocator_traits< allocator_type> :: propagate_on_container_move_assignment :: value 时移动赋值操作符为 true <一个容器（除了数组）的code>）无效任何引用，
指针或引用源
容器的元素的迭代器。 [注意： end（）迭代器不引用任何元素，因此
可能无效。 - 结束注释]




在移动分配中传播的指针必须移动向量对象的指针，但不能移动向量的元素。 （选项1）

默认分配器 LWG缺陷2103 在容器的移动分配期间被传播，因此OP中的技巧被禁止移动各个元素。

---

我的问题是：这种行为是一个错误还是故意的？

不，不可以（可以说）。

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.

解决方案

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).

这篇关于移动分配比拷贝分配慢 - 错误，功能或未指定？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！