Java Concurrency: CAS vs. Blocking

Question

I am reading a Java Concurrency book in practice. Chapter 15 deals with non-blocking algorithms and the Comparison and Swap Method (CAS).

It is written that CAS works much better than locking methods. I want to ask people who have already worked with both of these concepts and would like to hear, when you prefer, which of these concepts? Is it really much faster?

For me, the use of locks is much clearer and more understandable and perhaps even better to support (please correct me if I am wrong). Should we really focus on creating our parallel CAS related code than locks to improve performance or increase stability?

I know that it may not be a strict rule when to use what. But I just wanted to hear some opinions, experience with the new CAS concept.

Answer 1

CAS is usually much faster than locking, but it depends on the degree of competition. Because CAS can force a retry if the value changes between reading and comparing, a thread could theoretically be stuck in a busy wait if the variable in question hits many other threads (or if it is expensive to calculate the new value from the old value (or both).

The main problem with CAS is that it is much more difficult to program than when locking. Keep in mind that locking, in turn, is much harder to use correctly than messaging or STM , so do not take this as a confirmation of a call to use locks.

Answer 2

The relative speed of operations is basically not a problem. The difference in scalability between locking and non-locking algorithms is important. And if you work in 1 or 2 cores, stop thinking about such things.

Non-blocking algorithms usually scale better because they have shorter "critical sections" than lock-based algorithms.

Answer 3

You can see the numbers between ConcurrentLinkedQueue and BlockingQueue. What you will see is that CAS is noticeably faster with moderate (more realistic in real applications) threads.

The most attractive feature of non-blocking 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 to work. However, when acquiring a lock, if the lock commit thread has some kind of OS failure, every other thread waiting for the lock to be released will also be hit by a failure.

To answer your questions, yes, non-blocking thread-safe algorithms or collections (ConcurrentLinkedQueue, ConcurrentSkipListMap / Set) can be significantly faster than their blocking copies. As Marcelo noted, getting the right locking algorithms is very difficult and requires a lot of attention.

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

Answer 4

There is a good book, strongly related to the topic without concurrency blocking: The Art of Multiprocessing by Maurice Herlihy

Answer 5

If you are looking for a comparison in the real world, here is one. Our application has two (2) topics: 1) a read stream to capture a network packet, and 2) a consumer stream that receives a packet, counts it, and reports statistics.

Topic # 1 exchanges one packet at a time with thread # 2

Result # 1 - uses CAS-based user exchange using the same principles as SynchronousQueue, where our class is called CASSynchronousQueue:

30,766,538 packets in 59.999 seconds :: 500.763Kpps, 1.115Gbps 0 drops libpcap statistics: recv=61,251,128, drop=0(0.0%), ifdrop=0 

Result # 2 - when replacing our CAS implementation with standard java SynchronousQueue:

 8,782,647 packets in 59.999 seconds :: 142.950Kpps, 324.957Mbps 0 drops libpcap statistics: recv=69,955,666, drop=52,369,516(74.9%), ifdrop=0 

I do not think that the difference in performance could not be more clear.