Iteration through std containers in openmp

Question

I'm trying to use openmp to multithread a loop through std::set. When I write the following code -

    #pragma omp parallel for
    for (std::set<A>::const_iterator i = s.begin(); i != s.end(); ++i) {
            const A a = *i;
            operate(a);
    }

I get this error:

error: invalid type for iteration variable 'i'
error: invalid controlling predicate
error: invalid increment expression.

Is there an another, correct way to iterate through std containers using openmp? I know I can use int i and iterate from 0 to s.size() and an iterator or operator[] in the loop body, but this looks much less clean.

Solution

Loop parallelization for stl iterators only works since OpenMP 3.0, and only for random access iterators (e.g. vector and deque). You should be able to do something like this:

#pragma omp parallel {
   for (std::set<A>::const_iterator i = s.begin(); i != s.end(); ++i) {
      #pragma omp single nowait {
         operate(*i);
      }
   }
}

Overhead is quite big though because each thread iterates over the whole sequence (but only executes operate on some of it). Your method using an int i is more efficient.

As an alternative take a look at GCC's parallel implementation of std::for_each. See my comment.

EDIT: The STL Parallism TS, which will most likely be part of C++17, might be a good option in the future for iterating over standard containers.

Comments

[quimnuss]

std::set does not have the operator[] and msvc only supports openmp 2.0 :/

[stephan]

@quimnuss: the Parallel STL for msvc might be helpful. Parallelism TS will most likely be part of C++17, so this should be reasonably future-proof (but might still have bugs and not be feature complete, I haven't followed the MS implementation too closely).

[cnst]

Can you possibly clarify since when does for_each has OpenMP annotations? E.g., which gcc version was it introduced in? I'm trying GCC 4.7 (OpenMP 3.1), and it doesn't seem to work.

[stephan]

@cnst: I'm working on Windows right now and don't have GCC here, so my answer might be a bit wrong. But from memory (and the documentation): you have to compile with a couple of flags, e.g. -O3 -fopenmp -march=native in addition to your other flags. Now you can either add -D_GLIBCXX_PARALLEL (=complete std parallel), or selectively #include <parallel/algorithm> and then use e.g. __gnu_parallel::sort(v.begin(), v.end());. If this does not work, let me know and I'll check over the weekend.

[stephan]

And this remark in the documentation is important, @cnst: "Please note that this doesn't necessarily mean that everything will end up being executed in a parallel manner [...]." So, if your code does not seem to run in parallel, set up a toy project with a huge vector with random data and and sort it to be sure that everything works as expected. See also the tuning section of the documentation.