Lock-Free Structures

“Lock-free” does not mean “no locks in the source”. It is a precise claim about progress, and the precision is the point.

A lock-free stack

The classic, and short enough to read in full:

class LockFreeStack<T> {
  private head = new Atomic<Node<T> | null>(null);

  push(value: T) {
    const node = new Node(value);
    let current: Node<T> | null;

    do {
      current = this.head.load();
      node.next = current;                              // point at what we saw
    } while (!this.head.compareExchange(current, node)); // publish, or retry
  }

  pop(): T | undefined {
    let current: Node<T> | null;

    do {
      current = this.head.load();
      if (current === null) return undefined;
    } while (!this.head.compareExchange(current, current.next));

    return current.value;
  }
}

The whole structure is one CAS loop. If somebody else changed head between the load and the exchange, we re-read and try again — and that retry only happened because they succeeded, which is exactly the lock-free guarantee.

Why this is harder than it looks

ABA. CAS cannot distinguish “unchanged” from “changed back”, and for pointers that is a correctness bug rather than a curiosity. Tagged pointers or double-width CAS.

Multi-word updates are impossible. CAS handles one word. A structure needing two pointers changed together — a doubly linked list, most balanced trees — has no straightforward lock-free version. Papers exist; they are long.

Correctness is not testable. These algorithms fail on interleavings you will not hit by running the tests a million times. Published lock-free algorithms have shipped with bugs found years later by model checkers.

The performance is not automatic

Under high contention, a CAS loop can be slower than a mutex. Every failed attempt is wasted work and a cache line bounced between cores. A mutex parks the loser, which consumes nothing.

Under low contention, lock-free wins — no syscall, no scheduler.

The honest summary: lock-free is about latency predictability, not throughput. If you need a bounded worst case, it is the tool. If you want the program to be faster on average, measure first, because it often is not.