I have an application where I want to memoize the results of a function across a number of threads. The single-threaded version of the code I want looks something like this:
int memoized_method(int arg) {
int result;
if (memo.count(arg)) {
result = memo[arg];
}
else {
result = unmemoized_method(arg);
memo[arg] = result;
}
return result;
}
Where memo is a unordered_map. As I understand it, the unordered_map provides guarantees for concurrent reads and for single-threaded writes. My challenge is that, ideally, I need alternate between these modes. This makes it challenging to get the full benefit of the multi-threaded code.
I'll give code to make the dilemma more clear. I could use mutex like this:
mutex mtx;
int memoized_method(int arg) {
int result;
mtx.lock();
if (memo.count(arg)) {
result = memo[arg];
}
else {
result = unmemoized_method(arg);
memo[arg] = result;
}
mtx.unlock();
return result;
}
I don't want this option because it requires critical locks every time I access the memo, which would slow down my particular application a lot. Alternatively, I could do something like this:
mutex mtx;
int memoized_method(int arg) {
int result;
if (memo.count(arg)) {
result = memo[arg];
}
else {
mtx.lock();
result = unmemoized_method(arg);
memo[arg] = result;
mtx.unlock();
}
return result;
}
But this isn't threadsafe, since memo could end up re-hashing while some other thread is in the middle of accessing it.
Essentially, I want the ability to lock access to the "if" portion of the code only when a thread is in the "else" portion. I would also need the ability to let any threads that are in the "if" block when it gets locked to finish it. I can't see a way to use mutex to solve this problem since mutex is tied to one particular code block. Is there a tricky way to do it that I haven't noticed? Or are there other lock types I should be aware of?
