Why do we need to compareAndSet when set is already atomic in Java?

There are two important concepts in multithreading environment.

1. atomicity
2. visibility

Volatile solves the visibility problem but it does not deal with atomicity e.g. i++. Here i++ is not a single machine instruction rather it is three machine instructions.

1. copy the value to register
2. increment it
3. place it back

AtomicInteger, AtomicReference are based on the Compare and swap instruction. CAS has three operands a memory location V on which to operate, the expected old value A, and the new value B. CAS atomically updates V to the new value B, but only if the value in V matches the expected old value A; otherwise it does nothing. In either case, it returns the value currently in V. This is used by JVM in AtomicInteger, AtomicReference and they call the function as compareAndSet() if this functionality is not supported by underlying processor then JVM implements it by spin lock.

Set is atomic (it is not always correct) but compare and then set is not atomic. So when you have a requirement for this e.g. when the value is X then only change to Y so to do this atomically you need this kind of primitives you can use compareAndSet of AtomicInteger, AtomicReference e.g. atomicLong.compareAndSet(long expect, long update)

You can actually use this primitives to develop powerful datastrucutures like Concurrent stack.

import java.util.concurrent.atomic.AtomicReference; public class MyConcurrentStack<T> { private AtomicReference<Node> head = new AtomicReference<Node>(); public MyConcurrentStack() { } public void push(T t) { if (t == null) { return; } Node<T> n = new Node<T>(t); Node<T> current; do { current = head.get(); n.setNext(current); } while (!head.compareAndSet(current, n)); } public T pop() { Node<T> currentHead = null; Node<T> futureHead = null; do { currentHead = head.get(); if (currentHead == null) { return null; } futureHead = currentHead.next; } while (!head.compareAndSet(currentHead, futureHead)); return currentHead.data; } /** * * @return null if no element present else return a element. it does not * remove the element from the stack. */ public T peek() { Node<T> n = head.get(); if (n == null) { return null; } else { return n.data; } } public boolean isEmpty() { if (head.get() == null) { return true; } return false; } private static class Node<T> { private final T data; private Node<T> next; private Node(T data) { this.data = data; } private void setNext(Node next) { this.next = next; } } } 

You use compareAndSet when you need to update some data already existent in AtomicReference and then put it back to this reference.

For example: you need to increment a value from several threads (or update it in any other way).

Integer n = new Integer(10); AtomicReference<Integer> ref = new AtomicReference<>(n); // later... int i = ref.get().intValue(); // i == 10 // some other thread increments the value in ref and now it is 11 ref.set(new Integer(i + 1)); // Oops! Now ref contains 11, but should be 12. 

But with compareAndSet we could increase it atomically.

Integer n = new Integer(10); AtomicReference<Integer> ref = new AtomicReference<>(n); // later... boolean success = false; do { Integer old = ref.get(); // old == 10 on first pass, 11 on second pass // On first pass some other thread incrments the value in ref and now it is 11 Integer updated = new Integer(old + 1); success = ref.compareAndSet(old, updated); // On first pass success will be false and value in ref will not update } while (!success); // Now ref contains 12 if other thread increments it to 11 between get and set. 

A simple write operation is inherently atomic (in most cases). There's nothing special about set(). If you look at the source code for AtomicInteger.set(), you'll see this:

public final void set(int newValue) { value = newValue; } 

The magic of atomic classes is that they can read and modify atomically. In a multi-threaded environment, if you try to implement compare-and-set logic using a simple if, you might read a value, run some calculation and try to update the variable. But between your read and write operations, the value could have been updated by another thread, invalidating your calculation. Atomic classes make sure that nothing gets between your reads and writes. Hence the compareAndSet() methods, along with getAndSet(), getAndIncrement() etc.

compareAndSet is an essential primitive for non-blocking algorithms.

For example, it's basically impossible to implement wait-free algorithms with atomic read/write only — there must be compareAndSet or something similar.

compareAndSet is much more powerful that atomic read/write.
The power is expressed in consensus number:

• compareAndSet has consensus number infinity
• atomic read/write has consensus number 1

Consensus number is the maximum number of threads for which the concurrent object can solve a consensus problem (threads propose their candidate values and agree on a single consensus value) in a wait-free (i.e. without blocking, every thread is guaranteed to complete in no more that some fixed max number of steps) implementation.
It was proven that objects with consensus number of n can implement any object with a consensus number of n or lower, but cannot implement any objects with higher consensus number.

More explanations can be found in "The Art of Multiprocessor Programming" by M. Herlihy and N. Shavit.

Set is atomic and used to set a new value. compareAndSet compares old value and if it equals to current value, sets new value. If we use set instead of compareAndSet:

if(atomic.get().equals(12)) { atomic.set(13); } 

This will not be thread-safe, because it causes race condition. Result of execution depends on the timing and order of threads. For example, when thread1 gets the value, thread2 can change it. Compound operations such as check-and-act, read-modify-write must be executed as atomic.

Simply put, even set() is atomic, when you just finished assigning the value, it already left the "guarding" by the atomicity granted by set() and it's vulnerable for change. Another if (x==y) before or after set() cannot guarantee the value is the one we need when we set().

Imagine this scenario:

You generate some token locally. You want to share this token between threads as much as possible.

At first it's null:

// static make it shared between singleton instances; volatile makes the change visible immediately to all threads static volatile AtomicReference<String> token = new AtomicReference(null); 

And when getting token:

public String getToken() { if (token.compareAndSet(null, generateToken())) { // entering here means the comparison done atomically finds the token is null and requested a new one log.debug("Generating new token for the first time"); return token.get(); } // atomic comparison returns false, meaning token already present log.debug("Return already generated token"); return token.get(); } 

Some early threads sees the null value, all of them called generateToken(), so they have different token on each thread. But when the 1st thread updates the value, all the other threads will see it. And the later threads will get present token.

When generating token is cheap(locally done, no external API I/O operations), non-lock compareAndSet() ensures higher throughput comparing to a synchronized block. My own tests proven that when there are 100 threads, the difference in time is visible already.

But when generating token is expensive (external API), you may just use synchronized (lock) block to ensure only one thread is doing the HTTP request.