OpenMP/__ gnu_parallel用于unordered_map [英] OpenMP/__gnu_parallel for an unordered_map

问题描述

在代码的某个时刻，我必须对unordered_map中的所有元素进行操作.为了加快此过程，我想使用openMP，但是幼稚的方法不起作用:

std::unordered_map<size_t, double> hastTable;

#pragma omp for
for(auto it = hastTable.begin();
    it != hastTable.end();
    it ++){
//do something
}

其原因是，unordered_map的迭代器不是随机访问迭代器. 另外，我尝试了在for_each上使用__gnu_parallel指令.但是下面的代码

#include <parallel/algorithm>
#include <omp.h>

__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          //do something with item.secon
                        });

与(gcc 4.8.2)编译

 g++ -fopenmp -march=native -std=c++11

不并行运行.用向量切换unordered_map并使用相同的__gnu_parallel指令并行运行.

为什么在无序映射的情况下它不能并行运行?有解决方法吗?

在下面，我给您一些简单的代码，再现了我的问题.

#include <unordered_map>
#include <parallel/algorithm>
#include <omp.h>

int main(){

//unordered_map                                                                                                                                      
std::unordered_map<size_t, double> hashTable;
double val = 1.;
for(size_t i = 0; i<100000000; i++){
  hashTable.emplace(i, val);
  val += 1.;
}
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          item.second *= 2.;
                        });

//vector                                                                                                                                             
std::vector<double> simpleVector;
val = 1.;
for(size_t i = 0; i<100000000; i++){
  simpleVector.push_back(val);
  val += 1.;
}
__gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double & item)
                        {
                          item *= 2.;
                        });

}

期待您的回答.

解决方案

您可以在存储桶索引的范围内拆分循环，然后创建一个存储桶内迭代器来处理元素. unordered_map具有.bucket_count()和允许进行此操作的特定于存储桶的迭代器begin(bucket_number)，end(bucket_number).假设您没有从1.0修改默认的max_load_factor()并具有合理的哈希函数，则每个存储桶 average 1个元素，并且在空存储桶上不要浪费太多时间.

At some point in my code I have to make operations on all elements in an unordered_map. In order to accelerate this process I want to use openMP, but the naive approach does not work:

std::unordered_map<size_t, double> hastTable;

#pragma omp for
for(auto it = hastTable.begin();
    it != hastTable.end();
    it ++){
//do something
}

The reason for this is, that the iterator of an unordered_map is no random access iterator. As an alternative I have tried the __gnu_parallel directives working on for_each. But the following code

#include <parallel/algorithm>
#include <omp.h>

__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          //do something with item.secon
                        });

compiled with (gcc 4.8.2)

 g++ -fopenmp -march=native -std=c++11

does not run parallel. Switching the unordered_map with a vector and using the same __gnu_parallel directive runs in parallel.

Why does it not run in parallel in case of the unordered map? Are there workarounds?

In the following I give you some simple code, which reproduces my problem.

#include <unordered_map>
#include <parallel/algorithm>
#include <omp.h>

int main(){

//unordered_map                                                                                                                                      
std::unordered_map<size_t, double> hashTable;
double val = 1.;
for(size_t i = 0; i<100000000; i++){
  hashTable.emplace(i, val);
  val += 1.;
}
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          item.second *= 2.;
                        });

//vector                                                                                                                                             
std::vector<double> simpleVector;
val = 1.;
for(size_t i = 0; i<100000000; i++){
  simpleVector.push_back(val);
  val += 1.;
}
__gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double & item)
                        {
                          item *= 2.;
                        });

}

I am looking forward to your answers.

解决方案

You could split a loop over ranges of bucket indices, then create an intra-bucket iterator to handle elements. unordered_map has .bucket_count() and the bucket-specific iterator-yielding begin(bucket_number), end(bucket_number) that allow this. Assuming you haven't modified the default max_load_factor() from 1.0 and have a reasonable hash function, you'll average 1 element per bucket and shouldn't be wasting too much time on empty buckets.

这篇关于OpenMP/__ gnu_parallel用于unordered_map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！