时间戳

首页 > 解决方案 > 通过共享对象线程进行迭代是否安全？

c++ - 通过共享对象线程进行迭代是否安全？

问题描述

我有一个看起来有点像这样的并行 C++ 算法：

void recursiveFunction(int p, std::unordered_set<int> localSet) {
    vector<someStruct> toCall;
    if (p > SOMEINT) {
        return;
    }
    #pragma omp parallel for schedule(dynamic, 1) shared(localSet, someGlobalVector, someOtherGlobalVector)
    for (int i = 0; i < someGlobalVector[p].size(); ++i) {
        auto someLocalValue = someGlobalVector[p][i];
        auto someOtherLocal = someOtherGlobalVector[p][i];
        std::unordered_set<int> filtered;
        for (auto elem : localSet) {
            if (someLocalValue.count(elem) == 0) {
                filtered.insert(elem);
            }
        }
        if (checkSomeCondition(p+1, filtered)) {
            #pragma omp critical
            {
                tocall.push_back({someOtherLocal, filtered});
            }
        }
    }
    for (auto [elem1, elem2] : toCall) {
        recursiveFunction(p+1, filtered);
    }
}

通过共享unordered_set线程进行迭代是否安全？

标签： c++multithreadingparallel-processingthread-safetyopenmp

解决方案

通过共享的 unordered_set 线程进行迭代是否安全？

不，根据定义， anunordered_set不是线程安全的。然而，这并不一定意味着一个人的代码在使用这种结构时存在竞争条件；例如，如果一个人只读取数据结构，即使是同时读取，那么一个人是安全的。这就是为什么真正不可变的数据结构根据定义是线程安全的，因为不能修改这些结构，因此得名。

另一方面，如果unordered_set被多个线程同时修改，则一个有竞争条件。尽管如此，unordered_set只要在执行写入时确保互斥，仍然可以以线程安全的方式写入。

当当前由多个线程修改这些结构时，非线程安全的数据结构，例如unordered_set依赖于访问它们的代码来确保互斥。

为了避免竞争条件，可以使用 OpenMP 的critical构造函数在操作期间同步对共享结构的访问insert：

#pragma omp critical
{
  // the code to insure mutual exclusion.
}

However, that would slow down the parallelization due to the overhead of such a synchronization mechanism. Alternatively, one can create data structures that will only be accessed individually by each thread, insert into those structures, and have the main thread merge those structures into one (outside the parallel region).

Let us break down your code a bite:

void recursiveFunction(int p, std::unordered_set<int> localSet) {
    #pragma omp parallel for schedule(dynamic, 1) shared(localSet, someGlobalVector, someOtherGlobalVector)
    for (int i = 0; i < someGlobalVector[p].size(); ++i) {
        auto someLocalValue = someGlobalVector[p][i];
        auto someOtherLocal = someOtherGlobalVector[p][i];
        std::unordered_set<int> filtered
        for (auto elem : localSet) {
            if (someLocalValue.count(elem) == 0) {
                filtered.insert(elem)
            }
        }
    }
}

The localSet, someGlobalVector, someOtherGlobalVector are shared, but they are only read. Hence, as long there is no other thread outside this method (running at the same time) changing those structures, you are fine. The vector<someStruct> toCall is shared, and modified, but the modification happens within a critical constructor, therefore there is no race condition there.

总而言之，假设没有其他线程修改上述共享结构，那么您的代码中没有竞争条件。尽管如此，您可以分析您的代码以验证该critical区域的开销。如果开销太高，您可以尝试以下方法：

void recursiveFunction(int p, std::unordered_set<int> localSet, int total_threads) {
    vector<someStruct> thread_tocall[total_threads];
    vector<someStruct> toCall;
    if (p > SOMEINT) {
        return;
    }
    #pragma omp parallel shared(localSet, someGlobalVector, someOtherGlobalVector)
    {
        int thread_id = omp_get_thread_num();
        for (int i = 0; i < someGlobalVector[p].size(); ++i) {
             auto someLocalValue = someGlobalVector[p][i];
             auto someOtherLocal = someOtherGlobalVector[p][i];
             std::unordered_set<int> filtered;
             for (auto elem : localSet) {
                 if (someLocalValue.count(elem) == 0) {
                    filtered.insert(elem);
                 }
             }
           if (checkSomeCondition(p+1, filtered)) {
                thread_tocall[thread_id].push_back({someOtherLocal, filtered});
            }
         }
    }
    for(int i = 0; i < total_threads; i++)
       for (auto [elem1, elem2] : thread_tocall[i]) {
          recursiveFunction(p+1, filtered);
       }
}

推荐阅读