Volatile and Interlocked.CompareExchange

Recently, when I tried to CAS volatile variable, I got this warning: a reference to a volatile field will not be treated as volatile. So the question is: does CAS succeed or not? I consulted with Jeffrey Richter on this subject, and here is his explanation: when passing volatile variable by ref to method, it is always treated as non volatile. Compiler just don’t distinguish between CompareExchange and all other methods, so it warnings in any case. The CAS operation will succeed, even with volatile variable (or more correct is to say: it will not failure because of volatile variable).  Well, I think that make sense, since the only difference between volatile and non volatile is volatile can’t be optimized and stored in shared memory rather than in CPU cache.  

    In addition he recommended to use Thread.VolatileRead/Write methods instead of declaring variable as volatile for better performance. This is contrasting to conclusion from this article, so I don’t decided which direction is better (despite my personal respect to Jeffrey).

If we talking about multithreading, here are couple bullet points for thinking in spare time:

• According to .NET specifications, reads and writes to/from variables (even non volatile) are atomic (when memory is properly aligned). However, in contrast with volatile variables, other CPUs not guaranteed to see changes “in real time”. Here is nice article explaining .NET 2.0 memory model and phenomenons such as movement of reads and writes in time.
• Operations such as increament are not atomic: to perform it CPU has to follow these steps: 1- Load a value from an instance variable into a register, 2- Increment (or decrement) value, and 3 - Store the value in the instance variable. The same is true for volatile variable.
• It is possible to create concurrent (thread safe) objects and collections without using even single lock (just using volatile and CAS)! Say goodbye to deadlocks, priority inversions, and performance bottlenecks! There are many research on this subject, here are some nice links (I sorted them from basics theoretic to advanced practical):
  • Lock-free and wait-free algorithms - basic idea and definition from wikipedia
  • Software transactional memory - another interesting idea: access and modify shared objects by splitting operations to separate transactions (something like in DB)
  • Here one guy explaining idea of synchronization using CAS operation.
  • Multi Processor Progamming cource from Tel Aviv University - very cool slides with detailed explanations and examples on Java
  • University of Cambridge - including Lock-free library (based on STM idea, implemented on Linux C++). Also I highly recommending to read Concurrent programming without locks paper – extremely interesting!
  • Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms- by Maged M. Michael and Michael L. Scott
  • SXM- C# Software Transactional Memory (STM) by Tim Harris. Unfortunately the licence is not permitting commercial use (yet).
  • NSTM - C# STM by Rulf Suderbucher (Open Source, New BSD License)
  • DSTM2 - Java Software Transactional Memory.
  • java.util.concurrent namespace.A Java library developed by Lea Doug, which is including everything you may need in concurrent programming: free lock hash table, lists, sets, java implementation of M.M. Michael queue and many many more. The full JDK code could be downloaded from here. I am not a lawyer, but as much I understand, this open source code could be modified but is not allowed to be ported to any other language but Java
  • Dr. Cliff Click’s wait free lock free hash table – code (Java) is here, pdf with explanations and benchmark results is here, his lecture on this subject is here.

Is it just me or .NET has a HUGE gap to fill for concurrency support compared to Java? Last point: Microsoft preparing to release in .NET 4.0 library for parallel computations. It will provide API, which will allow to execute separate calculations on different processors. Couple month ago they released preview (not for commercial use yet). The problem is when these calculations performed on shared memory, you still have to synchronize it – and here creating performance bottleneck. Anyone beside me see how to solve that problem?   (Tip – read previous point).

Update (11.03.08): Here is one additional product: Intel Threading Building Blocks (TBB), which includes concurrent collections and parallelism API (Microsoft doing now something similar). Language – C++. Available in commercial and Open Source versions.