OpenMP/__gnu_parallel for an unordered_map

2019-06-21

An answer to this question on Stack Overflow.

Question

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.

Answer

You can do this by iterating over the buckets of the unordered_map, like so:

#include <cmath>
#include <iostream>
#include <unordered_map>
int main(){
  const int N = 10000000;
  std::unordered_map<int, double> mymap(1.5*N);
  //Load up a hash table
  for(int i=0;i<N;i++)
    mymap[i] = i+1;
  #pragma omp parallel for default(none) shared(mymap)
  for(size_t b=0;b<mymap.bucket_count();b++)
  for(auto bi=mymap.begin(b);bi!=mymap.end(b);bi++){
    for(int i=0;i<20;i++)
      bi->second += std::sqrt(std::log(bi->second) + 1);
  }
  std::cout<<mymap.begin()->first<<" "<<mymap.begin()->second<<std::endl;
  return 0;
}