OpenMP Parallelizing for loop with map

Question

I am trying to parallelize a for-loop which scans std::map. Below is my toy program:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <cassert>
#include <omp.h>

#define NUM 100000

using namespace std;

int main()
{
  omp_set_num_threads(16);
  int realThreads = 0;
  string arr[] = {"0", "1", "2"};
  std::map<int, string> myMap;
  for(int i=0; i<NUM; ++i)
    myMap[i] = arr[i % 3];

  string is[NUM];

  #pragma omp parallel for
  for(map<int, string>::iterator it = myMap.begin(); it != myMap.end(); it++)
  {
    is[it->first] = it->second;
    if(omp_get_thread_num() == 0)
      realThreads = omp_get_num_threads();
  }
  printf("First for-loop with %d threads\n", realThreads);

  realThreads = 0;
  #pragma omp parallel for
  for(int i=0; i<NUM; ++i)
  {
    assert(is[i] == arr[i % 3]);
    if(omp_get_thread_num() == 0)
      realThreads = omp_get_num_threads();
  }
  printf("Second for-loop with %d threads\n", realThreads);
  return 0;
}

Compilation command:

icc -fopenmp foo.cpp

The output of the above code block is:

First for-loop with 1 threads
Second for-loop with 16 threads

Why am I not able to parallelize the first for-loop?

How are you determining whether you have successfully parallelized? — merlin2011
– merlin2011, Commented Apr 8, 2014 at 2:21
i don't think std::map is thread-safe and can't think a way how it can be looped concurrently without convert it to array first — Bryan Chen
– Bryan Chen, Commented Apr 8, 2014 at 2:24
@merlin2011 - The output comes from omp_get_num_threads() which is inside the for-blocks. — Keval
– Keval, Commented Apr 8, 2014 at 6:08
@BryanChen, as long as the OP is not changing the map (e.g. adding or deleting entries) in his loop and is over iterating over it then it's thread-safe. — Z boson
– Z boson, Commented Apr 8, 2014 at 7:41

Hristo Iliev · Accepted Answer · 2014-04-08 11:50:41Z

3

std::map does not provide random-access iterators, only the usual bi-directional iterator. OpenMP requires that the iterators in parallel loops are of random-access type. With other kind of iterators explicit tasks should be used instead:

#pragma omp parallel
{
  #pragma omp master
  realThreads = omp_get_num_threads();

  #pragma omp single
  for(map<int, string>::iterator it = myMap.begin(); it != myMap.end(); it++)
  {
    #pragma omp task
    is[it->first] = it->second;
  }
}

Note in that case a separate task is created for each member of the map. Since the task body is very computationally simple, the OpenMP overhead will be relatively high in that particular case.

answered Apr 8, 2014 at 11:50

Hristo Iliev

74.8k12 gold badges148 silver badges197 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

OpenMP Parallelizing for loop with map

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related