how to handle cached data structures with multi-threading (e.g. openmp)

Question

I'm using OpenMP to parallelize our C++ library. In there, we have various places where we avoid recomputing some stuff by storing results in a variable (i.e. caching the result for re-use). However, this behavior is hidden to the user in methods by the class. For instance, on first use of a method, the cache will be filled. All subsequent uses will just read from the cache.

My problem is now that in a multi-threaded program, multiple threads can call such a method concurrently, resulting on race conditions on creating/accessing the cache. I'm currently solving that by putting the cache stuff in a critical section, but this slows everything down of course.

An example class might go as follows

class A {
public:
   A() : initialized(false)
     {}
   int get(int a)
      { 
#pragma omp critical(CACHING)
        if (!initialized)
          initialize_cache();
        return cache[a];
      }
private:
   bool initialized;
   void initialize_cache()
     {
       // do some heavy stuff
       initialized=true;
     }
   int *cache;
};

It would be better if the critical section was in the initialize_cache() function, as then it would only lock all threads when the cache hasn't been initialized yet (i.e. only once), but that seems dangerous as then multiple threads could be trying to initialize the cache at the same time.

Any suggestions to improve this? Ideally the solution would be compatible with older OpenMP versions (even v2 for Visual Studio...)

PS: This might have been asked before, but searches for openmp and caching throw up lots of stuff on processor caches, which is not what I want to know...

Can you make a new class and a global variable of that class and have the new ctor do your init? — brian beuning, Jan 16 '15 at 02:05
in real life, my object is set_up at run-time with different parameters. when it's set_up, the cache will be cleared as it's no longer appropriate. so, no I cannot have a global variable. Also, as the computation time of the cache stuff is quite high, and it's not needed in all usage cases, we currently avoid initialising the cache, unless we really need it. (you couldn't know this from the question. I guess this happens when trying to make a simple example). — krthie, Jan 16 '15 at 11:26

score 3 · Answer 1 · answered Jan 17 '15 at 04:49

You can use "Double-Checked-Locking(DCL) pattern" with OpenMP atomic operation, OpenMP v3.1 or later required (read/write option of omp atomic pragma).

class A {
public:
   A() : initialized(false)
     {}
   int get(int a)
      {
        bool b;
#pragma omp atomic read
        b = initialized;
        if (!b) {
#pragma omp critical(CACHING)
          // you must recheck in critical section
          if (!initialized)
            initialize_cache();
        }
        return cache[a];
      }
private:
   bool initialized;
   void initialize_cache()
     {
       // do some heavy stuff
#pragma omp atomic write
       initialized = true;
     }
   int *cache;
};

...But I recommend one of following options rather than DCL pattern:

pthread_once() (POSIX Threads library)
std::call_once() (C++11 Standard library)
thread-safe static variable (C++11 core language feature)

any chance of doing this with earlier versions of openmp? I need to be as cross-platform compatible as possible. Does this solution overcome problems with the DCL pattern (see e.g. http://michaelsuess.net/publications/suess_leopold_singleton_07.pdf) — krthie, Jan 20 '15 at 23:57
AFAIK, there is no portable way before OpenMP v3.0, except straightforwardly use `omp critical` construct. And I think this code works well under OpenMP memory model, because `initialized`'s access are designated as atomic and anyway protected by critical section. — yohjp, Jan 21 '15 at 01:15

score 2 · Answer 2 · edited May 23 '17 at 12:03

A efficient singleton is the best choice for you. Please check here.efficient thread-safe singleton in C++

Also, Herb Sutter talks about that in CppCon 2014

Here is the full code snippet from the video I showed above:

class Foo {
public:
    static Foo* Instance();
private:
    Foo() {init();}
    void init() { cout << "init done." << endl;} // your init cache function.
    static atomic<Foo*> pinstance;
    static mutex m_;
};

atomic<Foo*> Foo::pinstance { nullptr };
std::mutex Foo::m_;

Foo* Foo::Instance() {
  if(pinstance == nullptr) {
    lock_guard<mutex> lock(m_);
    if(pinstance == nullptr) {
        pinstance = new Foo();
    }
  }
  return pinstance;
}

run the code here: http://ideone.com/olvK13

thanks. My cache needs to be object specific, i.e. not a singleton but I'll admit that possible wasn't clear form my question. — krthie, Jan 22 '15 at 07:01

how to handle cached data structures with multi-threading (e.g. openmp)

2 Answers2