在 std::deque 上并行化 std::replace

Question

首先我知道deque 上的多个writter 不是很容易处理。但是通过下面的算法我可以保证没有对元素的并发访问。该算法将双端队列（它非常大，这就是我将其并行化的原因）分成块，然后 std::replaces 替换双端队列中的值。问题是，在某些情况下，替换任意值后，该值似乎仍然存在（顺便说一句：新值与旧值不一样）。是否可能是值未从 cpu 寄存器同步到内存？这里的代码：

std::deque<int*> _deque;
...
int threadsCount = 25;          
int chunkSize = ceil((float) _deque.size() / (float) threadsCount);                                                                                                                          
std::vector<std::thread> threads;
for (int threadNo = 0; threadNo < threadsCount; threadNo++) {
   std::uint64_t beginIndex = threadNo * chunkSize;
   std::uint64_t endIndex = (threadNo + 1) * chunkSize;
   if (endIndex > _deque.size()) {    
      endIndex = _deque.size();      
   }
   std::deque<int*>::iterator beginIterator = _deque.begin() + beginIndex;
   std::deque<int*>::iterator endIterator = _deque.begin() + endIndex;
   threads.push_back(std::thread([beginIterator, endIterator, elementToReplace, elementNew] () {
      std::replace(beginIterator, endIterator, elementToReplace, elementNew);                                      
   }));
}
for (int threadNo = 0; threadNo < threadsCount; threadNo++) {                                                                                                                               
   threads[threadNo].join();     
}

在该算法之后，有时（不确定）被替换的 (elementToReplace) 值仍在双端队列中。

Answer 1

不用手动实现这样的算法，只需传递适当的执行策略即可：

std::replace(std::execution::par, deque.begin(), deque.end(), elementToReplace, elementNew);
//           ^^^^^^^^^^^^^^^^^^^
//     executes the algorithm in parallel

请注意，您必须使用 C++17 或更高版本进行编译。

Answer 2

它看起来像一个竞争条件，但我无法重现它：http://cpp.sh/5egzm 这可能取决于您正在使用的双端队列实现，但它看起来很奇怪

Answer 3

仅供参考：由于上述算法崩溃并且建议的执行策略在我的系统上仍然不可用我使用 GNU 并行：

__gnu_parallel::replace(_deque.begin(), _deque.end(), elementToReplace, elementNew);

我会告诉你它是否有效以及性能统计数据。

在 std::deque 上并行化 std::replace

Parallelizing std::replace on std::deque

c++

memory

parallel-processing

deque