Java Concurrency: CAS vs Locking

Question

Im currently reading the Book Java Concurrency in Practice. In the Chapter 15 they are speaking about the Nonblocking algorithms and the compare-and-swap (CAS) Method.

It is written that the CAS perform much better than the Locking Methods. I want to ask the people which already worked with both of this concepts and would like to hear when you are preferring which of these concept? Is it really so much faster?

Personally for me the usage of Locks is much clearer and easier to understand and maybe even better to maintain. (Please correct me if I am wrong). Should we really focus creating our concurrent code related on CAS than Locks to get a better performance boost or is sustainability a higher thing?

I know there is maybe not a strict rule, when to use what. But I just would like to hear some opinions, experiences with the new concept of CAS.

Answer 1

CAS is generally much faster than locking, but it does depend on the degree of contention. Because CAS may force a retry if the value changes between reading and comparing, a thread can theoretically get stuck in a busy-wait if the variable in question is being hit hard by many other threads (or if it is expensive to compute a new value from the old value (or both)).

The main issue with CAS is that it is much more difficult to program with correctly than locking. Mind you, locking is, in turn, much harder to use correctly than message-passing or STM, so don't take this as a ringing endorsement for the use of locks.

Answer 2

You can look at the numbers between a ConcurrentLinkedQueue and a BlockingQueue. What you will see is that CAS is noticeably faster under moderate (more realistic in real world applications) thread conention.

The most attractive property of nonblocking algorithms is the fact that if one thread fails (cache miss or worse seg fault) then other threads will not notice this failure and can continue on. However, when acquiring a lock, if the lock holding thread has some kind of OS failure every other thread waiting for the lock to be freed will be hit with the failure also.

To answer your questions, yes nonblocking thread safe algorithms or collections (ConcurrentLinkedQueue, ConcurrentSkipListMap/Set) can be significantly faster then thier blocking counterparts. As Marcelo pointed out though, getting nonblocking algorithms correct is very difficult and requires alot of consideration.

You should read about the Michael and Scott Queue, this is the queue implementation for ConcurrentLinkedQueue and explains how to handle a two way, thread safe, atomic function with a single CAS.

Answer 3

There's good book strongly related to the topic of lock-free concurrency: "The Art of multi-processor programming" by Maurice Herlihy

Answer 4

The relative speed of the operations is largely a non-issue. What is relevant is the difference in scalability between lock-based and nonblocking algorithms. And if you're running on a 1 or 2 core system, stop thinking about such things.

Nonblocking algorithms generally scale better because they have shorter "critical sections" than lock-based algorithms.