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...

Answer 1

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)

Answer 2

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