0

I have a function memoize that reads and writes a static std::map, eg:

int memoize(int i)
{
static std::map<int,int> map;
const auto iterator = memoizer.find(i);
if (iterator == memoizer.end())
  memoizer[i]=i+1;
else
  return iterator->second;
}

memoize is called by other functions which are called by other functions which are called.... by functions in main. Now if in main I have something like

#pragma omp parallel for
for (int i=0; i<1000; i+++)
  f(i); \\function calling memoize

for (int i=0; i<1000; i+++)
  g(i); \\function calling memoize

then I have a problem in the first loop since std::map is not thread safe. I am trying to figure out a way to lock the static map only if openmp is used (thus only for the first loop). I would rather avoid having to rewrite all functions to take an extra omp_lock_t argument.

What's the best way to achieve that? Hopefully with the least amount of macros possible.

Improve this question
9
  • Consider having two separate functions: one thread-safe and one not. Commented Jan 5, 2020 at 17:23
  • @freakish Is there a thread-safe alternative to std::map? And how do I detect if I'm in an openmp region from within? Commented Jan 5, 2020 at 17:26
  • What I propose is to not detect anything. You write two functions and it is up to the caller to know which one to use. The simplest thread safety in your case would be by locking a static std::mutex. There are more efficient concurrent maps though, you'd have to google it. Commented Jan 5, 2020 at 17:27
  • @freakish The caller doesn't call these functions directly, but other functions calling functions.... calling the two alternatives. Hence the "nested" in the title Commented Jan 5, 2020 at 17:29
  • 1
    If the memoization is worth the time that synchronization with multiple threads would cost, then it is probably also fine if a single thread locks a mutex (even if not needed). Commented Jan 5, 2020 at 17:36

1 Answer 1

Reset to default
3

A very simple solution to your problem would be to protect both the read and the update parts of your code with a critical OpenMP directive. Of course, to reduce the risk of unwanted interaction/collision with some other critical you might already have somewhere else in your code, you should give it a name to identify it clearly. And should your OpenMP implementation permit it (ie the version of the standard being high enough), and also if you have the corresponding knowledge, you can add a hint on how much of contention you expect from this update among the threads for example.

Then, I would suggest you to check whether this simple implementation gives you sufficient performance, meaning whether the impact of the critical directive isn't too much performance-wise. If you're happy with the performance, then just leave it as is. If not, then come back with a more precise question and we'll see what can be done.

For the simple solution, the code could look like this (with here a hint suggesting that high contention is expected, which is only a example for your sake, not a true expectation of mine):

int memoize( int i ) {
    static std::map<int,int> memoizer;
    bool found = false;
    int value;
    #pragma omp critical( memoize ) hint( omp_sync_hint_contended )
    {
        const auto it = memoizer.find( i );
        if ( it != memoizer.end() ) {
           value = it->second;
           found = true;
        }
    }
    if ( !found ) {
        // here, we didn't find i in memoizer, so we compute it
        value = compute_actual_value_for_memoizer( i );
        #pragma omp critical( memoize ) hint( omp_sync_hint_contended )
        memoizer[i] = value;
    }
    return value;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Don't you still have a data race, since one thread could be calling find while the other is inserting? Also OP indicated that i+1 represents the actual time-intensive task, so I guess that should not be part of the critical section. It may be obvious how to resolve this, but I guess it would make a clearer answer if you showed how that can be done.
Indeed there is a race condition between the reads and the writes in the map. ATM, the reading part needs to be protected as well as the writing part might modify it while accessed for reading from another thread. However, even with the reads protected, there will still be some races between threads to be the first to create the ith entry. Is that a true issue, well hard to tell... I'll fix the code
I am not concerned about the race condition that might waste time doing calculations multiple times. I am concerned about undefined behavior. At least from the C++ standard point-of-view calling find and operator[] unsynchronized is a data race and causes undefined behavior. I don't know enough about OpenMP to know whether it puts any other requirements.
likewise. that is why I didn't even try to avoid the possible multiple computations and updates of the map for a given value as they will soon disappear. However, now that the reads are protected as well, the impact on performance might become quite high... To be seen by the OP. If needed, I can think of a 2-level solution with atomics which would be less costly
At second thought, I realized that the access to iterator->second() and even memoizer.end() needed to be protected as well. So I rewrote the code in a way I think is now bulletproof. Whether it is effective is another question though.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.