kcc__
kcc__

Reputation: 1658

OpenMP Nested For Loop with STL Containers

I am little confused on the following case regarding STL containers in C++. Operations such as push_back(.) are unsafe for threading however otherwise I think STL containers can be used.

std::vector<int> global_vector;

#pragma omp parallel for
for (int i = 0; i < height; i++)
{
 for(std::vector<int>::iterator it = fvec.begin(); it != fvec.end(); it++)
 {
   // process here with some push_back into global_vector
   global_vector.push_back(/*SOMETHING*/);
 }
}

Looking at the above code only the outter for loop is in parallel so I wonder will the push back in the inner for loop be affected making the thread unsafe.

Upvotes: 0

Views: 288

Answers (1)

Gilles
Gilles

Reputation: 9519

The answer is definitely YES, the code such as it is now is thread-unsafe.

The reason for that is that, push_back() depending on and modifying the internal state of the vector, there will be race conditions between the threads for modifying this internal state. To make the code thread-safe, you would need to make sure that no concurrent calls to this method ever happen.

This can probably be enforced this way:

std::vector<int> global_vector;

#pragma omp parallel for
for (int i = 0; i < height; i++) {
    for(std::vector<int>::iterator it = fvec.begin(); it != fvec.end(); it++) {
        // process here with some push_back into global_vector
        #pragma omp critical
        global_vector.push_back(/*SOMETHING*/);
    }
}

However, this code would just be a disaster in term of parallel efficiency, since all accesses would be serialised, with also adding a lot of overheads for managing the locks. So just forget about such an approach.

What you could do however is computing in advance the size of the final vector, along with the indexes you really want to access, and only use stateless accesses functions, and on per-threads disjointed sub-sets of the indexes. This would correspond to use global_vector[i] = /*SOMETHING*/; instead of your global_vector.push_back(/*SOMETHING*/); since you know the per-thread ranges of i indexes are disjoint.

Upvotes: 1

Related Questions