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

问题描述 投票:0回答:1

假设我们有一个

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), ...]);
}
  1. 为结果创建一个大小为
    count
    的向量,分块编辑向量的元素,然后将整个结果向量
    push_back()
    vec
    。这会使用额外的内存,并且结果向量到
    vec
    的移动在复杂度上是线性的。
  2. std::mutex
    创建
    vec
    并将
    push_back()
    调用放入关键部分。我最不喜欢这种方法,因为每次写入之前都会先进行读取,以便获得随机的旧元素来创建新元素。

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

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

c++ multithreading vector push-back
1个回答
0
投票

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

  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 个元素很小,除非元素构造函数做了严重的繁重工作。如果此过程对性能产生重大影响,则可能会发生其他情况。有必要找到根本问题。我的建议只是初步提示。

© www.soinside.com 2019 - 2024. All rights reserved.