std::vector push_back fails when used in a parallel for loop

Question

I have a code that is as follow (simplified code):

for( int i = 0; i < input.rows; i++ )
{
    if(IsGoodMatch(input[I])
    { 
        Newvalues newValues;
        newValues.x1=input.x1;
        newValues.x2=input.x1*2;
        output.push_back( newValues);
    }
} 

This code works well, but if I want to make it parallel using omp parallel for, I am getting error on output.push_back and it seems that during vector resize, the memory corrupted.

What is the problem and how can I fix it?

How can I make sure only one thread inserting a new item into vector at any time?

Answer 1

The simple answer is that std::vector::push_back is not thread-safe.

In order to safely do this in parallel you need to synchronize in order to ensure that push_back isn't called from multiple threads at the same time.

Synchronization in C++11 can easily be achieved by using an std::mutex.

Answer 2

std::vector's push_back can not guarantee a correct behavior when being called in a concurrent manner like you are doing now (there is no thread-safety).

However since the elements don't depend on each other, it would be very reasonable to resize the vector and modify elements inside the loop separately:

output.resize(input.rows);
int k = 0;

#pragma omp parallel for shared(k, input)
for( int i = 0; i < input.rows; i++ )
{
    if(IsGoodMatch(input[I])
    { 
        Newvalues newValues;
        ...
        // ! prevent other threads to modify k !
        output[k] = newValues;
        k++;
        // ! allow other threads to modify k again !
    }
} 

output.resize(k);

since the direct access using operator[] doesn't depend on other members of std::vector which might cause inconsistencies between the threads. However this solution might still need an explicit synchronization (i.e. using a synchronization mechanism such as mutex) that will ensure that a correct value of k will be used.

"How can I make sure only one thread inserting a new item into vector at any time?"

You don't need to. Threads will be modifying different elements (that reside in different parts of memory). You just need to make sure that the element each thread tries to modify is the correct one.

Answer 3

Use concurrent vector

#include <concurrent_vector.h>

Concurrency::concurrent_vector<int> in c++11.

It is thread safe version of vector.