Low Latency Java, Part II: Java CAS (Compare-And-Swap) Explained

This article explains the concepts and principles of CAS (Compare-And-Swap) used in the implementation of the LMAX Disruptor RingBuffer.

이글은 LMAX Disruptor RingBuffer 구현에 사용되는 CAS 개념과 원리에 대해서 설명합니다.

0. CAS?

Compare-And-Swap (CAS) is an atomic CPU instruction that forms the foundation of lock-free, non-blocking concurrency in Java. It enables thread-safe modification of shared variables without using traditional locks like synchronized or ReentrantLock.

Compare-And-Swap(CAS)은 Java에서 lock-free, non-blocking 동시성의 핵심을 이루는 원자적 CPU 명령어이다. synchronized나 ReentrantLock 같은 전통적인 락(Lock) 없이도 공유 변수를 스레드 안전하게(thread-safe) 수정할 수 있게 해준다.

1. How CAS Works?

The CAS algorithm follows this pseudocode logic:

if (currentValue == expectedValue) {
   currentValue = newValue;
   return true; // success
} else {
   return false; // another thread changed the value
}

This entire check-and-update operation is executed as a single atomic CPU instruction, so no other thread can interleave between the comparison and the write. When multiple threads attempt a CAS simultaneously, exactly one wins and updates the variable; the losers are not suspended — they are free to retry or take alternative action

2. Java’s Internal CAS Implementation

The Unsafe Class

At the lowest level, Java’s CAS relies on native methods in sun.misc.Unsafe

// Three native CAS methods in sun.misc.Unsafe
public final native boolean compareAndSwapObject(Object o, long offset,
 Object expected, Object x);
public final native boolean compareAndSwapInt(Object o, long offset,
 int expected, int x);
public final native boolean compareAndSwapLong(Object o, long offset,
 long expected, long x);

Java AtomicInteger Source Code Walkthrough

AtomicInteger is the most commonly used atomic class. Here is its core implementation (JDK 8)

public final class AtomicInteger extends Number implements java.io.Serializable {
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            // Calculate the memory offset of the "value" field
            valueOffset = unsafe.objectFieldOffset(
                AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;  // volatile ensures visibility across threads

    // Atomically sets value to 'update' if current value == 'expect'
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

    // Atomically increments by 1, returns the OLD value
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

    // Atomically adds delta, returns the OLD value
    public final int getAndAdd(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }
}

The volatile keyword on value ensures that reads and writes are visible across threads, while CAS ensures atomicity of the update.

The Spin-Retry Loop (getAndAddInt)

The Unsafe.getAndAddInt method reveals the spin (retry) loop — a core CAS pattern:

// Inside sun.misc.Unsafe
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);           // 1. Read current value
    } while (!compareAndSwapInt(o, offset, v, v + delta));  // 2. CAS: retry if failed
    return v;  // return old value
}

If the CAS fails (because another thread changed the value between the read and the CAS attempt), the loop re-reads the current value and retries. This is known as spin locking or optimistic retry.

3. Why CAS for Multi-Threading?

4. Spinning & Wait Strategies in LMAX

CAS spin loops keep threads actively running on the CPU core — they never yield or sleep. A thread in a while (!compareAndSet(...)) loop executes millions of iterations per second doing nothing productive while waiting, consuming 100% of its core. On modern CPUs, this tight loop generates constant cache-line traffic and occupies the entire execution pipeline, preventing hyper-threaded sibling threads from making meaningful progress.

However, this is by design in high-performance systems. LMAX Disruptor’s BusySpinWaitStrategy is intentionally used with dedicated/pinned CPU cores — each consumer thread gets its own physical core, so 100% usage is expected and desired for absolute minimum latency. Internally, the strategy calls Thread.onSpinWait() on each loop iteration, which emits the x86 PAUSE instruction — this does not reduce CPU usage to 0%, but it reduces power draw and frees pipeline resources for hyper-threaded siblings.

[WARN]

• The OpenJDK mailing list recommends: if you must busy-wait, at minimum use Thread.onSpinWait(), and consider Thread.yield() before it if maximum throughput isn't critical.
• Pure CAS spinning at 100% CPU is fine only when you have dedicated cores and need nanosecond-level latency. For most applications, use a backoff strategy (spin → yield → park) to avoid wasting CPU resources.

5. Example & Benchmark