c++ OpenMP critical: "one-way" locking?

Question

Consider the following serial function. When I parallelize my code, every thread will call this function from within the parallel region (not shown). I am trying to make this threadsafe and efficient (fast).

float get_stored_value__or__calculate_if_does_not_yet_exist( int A )
{    
    static std::map<int, float> my_map;

    std::map::iterator it_find = my_map.find(A);  //many threads do this often.

    bool found_A =   it_find != my_map.end();

    if (found_A)
    {
        return it_find->second;
    } 
    else
    {
      float result_for_A = calculate_value(A);  //should only be done once, really.
      my_map[A] = result_for_A;
      return result_for_A;
    }    
}

Almost every single time this function is called, the threads will successfully "find" the stored value for their "A" (whatever it is). Every once in a while, when a "new A" is called, a value will have to be calculated and stored.

So where should I put the #pragma omp critical ?

Though easy, it is very inefficient to put a #pragma omp critical around all of this, since each thread will be doing this constantly and it will often be the read-only case.

Is there any way to implement a "one-way" critical, or a "one-way" lock routine? That is, the above operations involving the iterator should only be "locked" when writing to my_map in the else statement. But multiple threads should be able to execute the .find call simultaneously.

I hope I make sense. Thank you.

Answer 1

According to this link on Stack Overflow inserting into an std::map doesn't invalidate iterators. The same goes for the end() iterator. Here's a supporting link.

Unfortunately, insertion can happen multiple times if you don't use a critical section. Also, since your calculate_value routine might be computationally expensive, you will have to lock to avoid this else clause being operated on twice with the same value of A and then inserted twice.

Here's a sample function where you can replicate this incorrect multiple insertion:

void testFunc(std::map<int,float> &theMap, int i)
{
    std::map<int,float>::iterator ite = theMap.find(i);

    if(ite == theMap.end())
    {
         theMap[i] = 3.14 * i * i;
     }
}

Then called like this:

std::map<int,float> myMap;

int i;
#pragma omp parallel for
for(i=1;i<=100000;++i)
{
    testFunc(myMap,i % 100);
}

if(myMap.size() != 100)
{
    std::cout << "Problem!" << std::endl;
}

Edit: edited to correct error in earler version.

Answer 2

OpenMP is a compiler "tool" for automatic loop parallelization, not a thread communication or synchronization library; so it doesn't have sophisticated mutexes, like a read/write mutex: acquire lock on writing, but not on reading.

Here's an implementation example.

Anyway Chris A.'s answer is better than mine though :)