c++ - OpenMP(C/C++) : Efficient way of sharing an unordered_map> 和线程之间的 ve​​ctor

Question

我有一个 for 循环，我想使其并行，但是线程必须共享一个 unordered_map 和一个 vector。

因为 for 循环有点大，所以我将在这里发布一个简明的概述，以便我可以清楚地说明我的主要问题。请阅读评论。

   unordered_map<string, vector<int>> sharedUM;

   /*
      here I call a function that updates the unordered_map with some
      initial data, however the unordered_map will need to be updated by
      the threads inside the for loop
   */

   vector<int> sharedVector;
  /* 
     the shared vector initially is empty, the threads will 
    fill it with integers, the order of these integers should be in ascending
    order, however I can simply sort the array after all the 
    threads finish executing so I guess we can assume that the order 
    does not matter
  */

   #pragma omp parallel for
   for(int i=0; i<N; i++){

      key = generate_a_key_value_according_to_an_algorithm();
      std::unordered_map<string, vector<int>::iterator it = sharedUM.find(key);

      /*
       according to the data inside it->second(the value), 
       the thread makes some conclusions which then
       uses in order to figure out whether 
       it should run a high complexity algorithm
       or not.
      */
       bool conclusion = make_conclusion();

       if(conclusion == true){

           results = run_expensive_algorithm();

          /*
             According to the results, 
             the thread updates some values of
             the key that it previously searched for inside the unordered_map
             this update may help other threads avoid running 
             the expensive algorithm
          */

       }

       sharedVector.push_back(i);

   }

最初我保留了代码，所以我只是在 for 循环中使用了 #pragma，但是我遇到了一些关于 sharedVector 更新的问题.所以我决定使用简单的锁来强制线程在写入 vector 之前获取锁。所以在我的实现中我有这样的东西:

      omp_lock_t sharedVectorLock;
      omp_init_lock(&sharedVectorLock);
      ...
      for(...)
      ...
       omp_set_lock(&sharedVectorLock);
       sharedVector.push_back(i);
       omp_unset_lock(&sharedVectorLock);
      ...
      omp_destroy_lock(&sharedVectorLock);

我已经多次运行我的应用程序，一切似乎都运行良好，直到我决定自动重新运行它太多次，直到我得到错误的结果。因为我对 OpenMP 和一般线程的世界还很陌生，所以我不知道当写入者更新某些共享数据时我们应该锁定所有读取器这一事实。正如您在我的应用程序中看到的那样，线程总是从 unordered_map 中读取一些数据，以便得出一些结论并了解有关分配给它们的 key 的信息。但是，如果两个线程必须使用同一个键，并且当某个其他线程试图读取该键的值时，另一个线程已经达到更新这些值的地步，会发生什么情况？我相信这就是我的问题所在。

但是我现在的主要问题是我不确定避免此类事情发生的最佳方法是什么。这就像我的系统在 99% 的时间里都在工作，但是那 1% 的时间毁了一切，因为两个线程很少分配有相同的键，这反过来又是因为我的 unordered_map 通常很大。

锁定 unordered_map 会完成我的工作吗？最有可能，但效率不高，因为想要使用键 x 的线程 A 必须等待线程 B 已经在使用键 y 完成，其中 y 可以与 x 不同。

所以我的主要问题是，我应该如何解决这个问题？当且仅当两个线程使用相同的 key 时，我如何锁定 unordered_map？

提前致谢

Answer 1

1 使用锁和互斥锁。您必须在并行 block 的外部声明并初始化锁变量(在#pragma omp parallel 之前)，然后在并行 block 内部使用它们:(1) 获取锁 (如果另一个线程锁定了它，这可能会阻塞)，(2)用竞争条件更改变量，(3)释放锁。最后，退出并行 block 后将其销毁。在并行 block 内声明的锁是线程本地的，因此不能提供同步。这可以解释您的问题。

2 写入复杂的 C++ 容器。 OpenMP 最初是为简单的 FORTRAN do 循环设计的(类似于 C/C++ for 具有整数控制变量的循环)。任何更复杂的事情都会让你头疼。为了安全起见，C++ 容器上的任何非常量操作都必须在锁内执行(对同一容器上的任何此类操作使用相同的锁)或 omp 临界区(使用同一容器上任何此类操作的相同名称)。这包括 pop() 和 push() 等，除了简单的读取。只有在此类非常量容器操作只占用一小部分时间的情况下，这才能保持高效。

3 如果我是你，我不会为 openMP 而烦恼(我用过它但现在很后悔)。对于 C++，您可以使用 TBB，它还带有一些线程安全但无锁的容器。它还允许您根据递归执行的任务而不是线程来思考(父任务产生子任务等)，但是 TBB 有一些简单的并行 for 循环实现，例如。