在std :: deque上并行化std :: replace(Parallelizing std::replace on std::deque)

 首先，我知道双端队列中的多个写手不是很容易处理。 但是使用以下算法，我可以保证元素上没有并发访问。 该算法在块中划分了一个deque（它非常大，这就是我将它并行化的原因）并且std :: replaces替换了deque中的值。 问题是，在某些情况下，在替换任意值之后，该值似乎仍然存在（顺便说一下：新值与旧值不同）。 可能是这个值没有从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）值仍然在deque中的情况。 

First of all I know that multiple writters on a deque are not very easy to handle. But with the following algorithm I can guarantee that there is no concurrent access on elements. The algorithm divides a deque (it is very large, thats the reason why I parallelize it) in chunks and the std::replaces replaces a value in the deque. The problem is, that in some cases after replacing an arbitrary value, the value seems to still exist (btw: it is NOT the case that the new value is the same as the old one). Is it maybe the case that the value is not synced out of the cpu register to the memory? Here the code:
 
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();     
}
 
After that algorithm it is sometimes (not deterministic) the case that a replaced (elementToReplace) value is still in the deque.

原文：https://stackoverflow.com/questions/45096976