OMP reduction for loop with std::map

Question

I want to parallelise the following for loop with a std::map with OpenMP 4.0:

int n=5000;
int nbin;

std::map<int, int> histogram;

for (int i = 1; i < n; i++) 
        {
            .
            .
            nbin =....... \\some calculation with integer result 
            ++histogram[nbin];
            

        }

I tried before the for loop:

#pragma omp declare reduction(                     \
                              +:std::map<int, int> :   \
                              omp_out += omp_in      \
                             )      initializer(omp_priv = 0)                    
                            
#pragma omp parallel for reduction(+ : histogram)

But it gives the error: no viable conversion from 'int' to 'std::map<int, int>'

How would be the correct reduction statement?

thanks for help!

Answer 1

Ok, toy example counting characters in a string:

  string text{"the quick brown fox jumps over the lazy dog"};

  charcounter<char,int> charcount;
#pragma omp declare reduction\
  (     \
        +:charcounter<char,int>:omp_out += omp_in       \
        ) \
  initializer( omp_priv = charcounter<char,int>{} )

#pragma omp parallel for reduction(+ : charcount)
  for ( int i=0; i<text.size(); i++ ) {
    char c = text[i];
    charcount.inc(c);
  }

(I think I can probably make that inc function look more like your ++foo[k], but that's for later.)

Implementation of the charcounter class, which is basically a map:

template<typename key,typename value>
class charcounter : public map<key,value> {
public:
  void operator+=( const charcounter<key,value>& other ) {
    for ( auto [k,v] : other )
      if ( this->contains(k) )
        this->at(k) += v;
      else
        this->insert( {k,v} );
  };
  void inc(char k) {
    if ( this->contains(k) )
      this->at(k) += 1;
    else
      this->insert( {k,1} );
  };
};

Note that this only demonstrates that it is possible to do a reduction on a map. Performance may dictate you using a totally different solution.