当所有线程都根据搜索结果在数组中设置标志时，是否需要互斥

Question

我有一个代码块，看起来像这个

std::vector<uint32_t> flags(n, 0);
#pragma omp parallel for 
for(int i = 0; i <v; i++) {
// If any thread finds it true, its true. 
// Max value of j is n.
for(auto& j : vec[i]) 
flags[j] = true; 
}
Work based upon the flags.

是否需要互斥锁？我知道缓存一致性将确保所有的写缓冲区都是同步的，并且冲突的缓冲区不会被写入内存。其次，可以通过简单地改变来避免缓存一致性的开销

flags[j] = true; 
to 
if(!flags[j]) flags[j] = true; 

如果标志[j]已经设置，则检查将降低写入频率，从而需要高速缓存一致性更新。即使flags[j]被读取为false，它也只会导致对flags[j]的一次额外写入，这是可以的。

编辑：

是的，多个线程可能并且将尝试写入flags[j]中的同一索引。因此产生了这个问题。

uint32_t被有意使用，而bool没有被使用，因为并行写入布尔值可能会出现故障，因为相邻的布尔值共享相同的字节。但是，即使没有互斥体，从不同线程并行写入同一uint32_t也不会像布尔操作那样出现故障。

FWIW，为了遵守标准，我最终保留了这个或多或少符合标准的代码，尽管不是100%。但是上面显示的非标准代码并没有在测试中失败。我曾经认为它在多套接字机器中会失败，但事实证明x86也提供了多套接字级别的缓存一致性。

#pragma omp parallel 
{
std::vector<uint32_t> flags_local(n, 0);
#pragma omp parallel for
for(int i = 0; i <v; i++) {
for(auto& j : vec[i]) 
flags_local[j] = true; 
}
// No omp directive here, as all threads 
// need to traverse their full arrays.
for(int j = 0; j <n; i++) {
if(flags_local[j] && !flags[j]) {
#pragma omp critical 
{ flags[j] = true; }
}
}
}

Answer 1

C++中的线程安全性使得您不必担心缓存一致性和此类硬件相关问题。重要的是C++标准中指定了什么，我认为它没有提到缓存一致性。这是实现者需要担心的。

对于写入std::vector的元素，规则实际上相当简单：写入向量的不同元素是线程安全的。只有当两个线程写入同一索引时，才需要同步访问(为此，两个线程是否写入相同的值并不重要(。

正如Evg所指出的，我做了一个粗略的简化。重要的是所有线程访问不同的内存位置。因此，对于std::vector<bool>，事情不会那么简单，因为std::vector<bool>的几个元素通常存储在一个字节中。

---

是的，多个踏板可能并将尝试写入标志[j]中的同一索引。

然后您需要同步访问。所有元素最初都是false并且所有写入都写入true这一事实并不相关。重要的是，你有多个线程访问同一内存，并且至少有一个线程对其进行写入。在这种情况下，你需要同步访问，或者你有数据竞争。

Answer 2

在写入时同时访问变量是一种竞争条件，因此这是未定义的行为。

flags[j] = true;

应该受到保护。

或者，您可以使用原子类型(但请参阅如何声明-a-vector-of-atomic-in-c++(。

或者使用std::atomic_ref(c++20(更简单

std::vector<uint32_t> flags(n, 0);
#pragma omp parallel for 
for (int i = 0; i < v; i++) {
for (auto& flag : vec[i]) {
auto atom_flag = std::atomic_ref<std::uint32_t>(flag);
atom_flag = true; 
}
}