多线程push_back到std::vector：互斥，放大和就地编辑，或者为结果创建一个向量并将其推回？

Question

假设我们有一个

std::vector<Element> vec

，它已经有 200 个元素。然后，我们要向其中添加

count

元素，每个元素都是在随机的旧元素（前 200 个）的基础上创建的：

for (int index = 0; index < count; index++) {
  vec.push_back(Element(vec[someRandomIndex(0, 200), ...]));
}

count

是一个非常大的数字，比如说 200，而且

Element

的构造函数并不简单，因此使 new

push_back()

的

Element

并行是有好处的。我看到三种方法可以做到这一点：

1. 调整大小

   vec

   并就地修改元素

vec.resize(vec.size() + count);
// this code will be split into chunks and each chunk 
// will be processed in a separate thread. No overlaps, so no data race. 
for (int index = 0; index < count; index++) {
  vec[200+index] = Element(vec[someRandomIndex(0, 200), ...]);
}

2. 为结果创建一个大小为

   count

   的向量，分块编辑向量的元素，然后将整个结果向量

   push_back()

   为

   vec

   。这会使用额外的内存，并且结果向量到

   vec

   的移动在复杂度上是线性的。
3. 为

   std::mutex

   创建

   vec

   并将

   push_back()

   调用放入关键部分。我最不喜欢这种方法，因为每次写入之前都会先进行读取，以便获得随机的旧元素来创建新元素。

哪种技术造成的开销最小？这有一个常见的做法吗？数字

200

只是一个例子，并且可能会变得更大。

Answer 1

分析始终是一个好主意，因为它提供了查看代码运行时“实际”发生的情况的机会。这个过程有两件事需要理解。

1. 向 std::vector 添加元素时，向量的存储是内存的连续部分。每次添加新元素时，当存储已满时，存储会重新分配较大部分的内存，并将存储的全部内容复制构造到新位置，然后将新元素添加到新存储中。当这种情况经常发生时，在将元素放入向量时会消耗 CPU。在添加元素之前调用 std::vector::reserve(N) 以避免重新分配，其中 N 是新元素计数。
2. 当通过push_back()向std::vector插入一个元素时，该元素会被构造然后被复制。如果元素构造很重要，则使用 emplace_back() 创建新元素并使用 std::move 现有元素会更快。
3. 调用 std::vector::resize(N) 默认在内存中构造 N 个元素。

虽然这不是问题的直接答案，但哪种方法最好，我同意上面的评论，即 200 个元素很小，除非元素构造函数做了严重的繁重工作。如果此过程对性能产生重大影响，则可能会发生其他情况。有必要找到根本问题。我的建议只是初步提示。