A Programmer's Apology

While making Graphing Calculator thread-safe, I examined all the classes to determined which could be shared by multiple threads. Equations, for example, after being constructed in the main thread, are conceptually static, and can be read by multiple readers in threads started after the equation is fully constructed. However, while they are conceptually static, they contain one field which is lazy-evaluated introducing a race condition if multiple threads try to write to that structure simultaneously. The original code looks like this:

if (not fAlreadyEvaluated) {
   fValue = ComputeValue();
   fAlreadyEvaluated = true;
   }
return fValue;

This could easily be made thread-safe by protecting all access with a mutex lock. However, nearly all accesses are read-only. Only the first access (by any thread) needs to write the value. Locking a mutex for every read would make the reads much more expensive. One could optimize for the common case by using a lock only to make the lazy evaluation a critical section to insure that only one thread ever writes the value. That leads to code like this:

if (not fAlreadyEvaluated) {
   Lock(fMutex); 
   if (not fAlreadyEvaluated) { 
      fValue = ComputeValue();
      fAlreadyEvaluated = true;
      }
   Unlock(fMutex);
   }
return fValue;

Note the second text of fAlreadyEvaluated after acquiring the mutex. This is necessary as another thread may have done the work while this thread of execution was waiting to acquire the lock. This is known as the Double Checked Locking Pattern. Schmidt and Harrison dissect this pattern extensively in this excellent paper of 1997.

Unfortunately, the pattern is flawed, and cannot be implemented correctly and portably in C++ at all. While Schmidt and Harrison rightly consider the problems of compiler optimizations, instructions reordering, and cache consistency, they do not consider the possiblity of CPU read and write reordering allowed by relaxed consistency of current CPUs. Meyers and Alexandrescu address those problems in C++ and The Perils of Double-Checked Locking and Double-Checked Locking, Threads, Compiler Optimizations, and More (2004).

Andrei's Summary: Multithreading is just one damn thing after, before, or simultaneous with another.

While there is no portable way to implement DCLP in C++, Meyers and Alexandrescu do show how it can be used correctly if your implementation provides a mechanism for memory barriers respected by both the compiler and the CPU. The code in Graphing Calculator now looks something like:

if (!fAlreadyEvaluated) {
   OurLock lock(fMutex);
   if (!fAlreadyEvaluated) {
      fValue = ComputeValue();
      OurWriteBarrier();
      fAlreadyEvaluated = true;
      }
   }
return fValue;

I'm unsure if I need an additional read barrier where Meyers and Alexandrescu show an acquire barrier in their. Anyone?