Parallel insertion to map

user_10327739 0
Viewed 415

I wanted to create a map ascribing pairs of integers vectors of integers. My purpose is to do it in parallel way. To ensure that I am not trying to push_back at the same time to the same memory entity (by multiple threads), the second coordinate of map's key pairs is responsible for the current thread number. I encountered, however, problems. It seems that some of the values are not inserting properly. Instead of getting 10 values all together, I get always less (sometimes 9, sometimes 8, 6, etc.)

map<pair<int, int>, vector<int> > test;
#pragma omp parallel num_threads(8)
{
    #pragma omp for
    for (int i = 0;i < 10;i++)
    {
        test[make_pair(i % 3, omp_get_thread_num())].push_back(i);
    }
}

I have also tried test.at(make_pair(i % 3, omp_get_thread_num())).push_back(i) and it didn't work either. In this case, however, the execution interrupted with an exception.

I thought that #pragma omp for distributes the for loop into disjoint subsequences of (0,...,9) so that there shouldn't be problem with my code... I am a bit confused. Could someone explain this issue to me?

openmp multithreading c++
2 Answers

As stated, the standard library containers are not thread safe. The appropriate solution for this case is to initialize n-maps (one for each thread) and than join them at the end.

As stated prior, using a mutex (and making access to the map safe) would be a valid solution, however it would also result in worse performance. As every time the map would be accessed each thread would have to wait on the mutex unlocking the data.

It should be noted that a size of 10 is not sufficient to make multithreading worth it, using multiple-threads here would most likely degrade performance.

map<pair<int, int>, vector<int> > test[8];
#pragma omp parallel num_threads(8)
{
    #pragma omp for
    for (int i = 0;i < large_number; i++)
    {
        int thread_id = omp_get_thread_id();
        test[thread_id][make_pair(i % 3, omp_get_thread_num())].push_back(i);
    }
}
#pragma omp barrier 

map<pair<int,int>, vector<int>> combined; 
for (int i = 0; i < 8; ++i) 
    combined.insert(test[i].begin(), test[i].end());
user_81378720

That's because a map is not thread safe (nor is a vector, but this part is not threaded). You have to add mutex, use lock-free containers or prepare your map first.

In this case, start on a single thread by creating all your entries.

#pragma omp single
for (int i = 0;i < 3;++i)
{
for (int j = 0;i < 8;++j)
{
    test.insert(make_pair(make_pair(i, j), vector<int>()));
}
}

Then do your parallel for (add a barrier).

user_22667720
Related