skip to content

How does AtomicStampedReference work, and how do you read and update it correctly?

level: seniorimportance: should knowfreq 44%

answer

  1. Pair = (reference, int stamp)
  2. Read both with get(int[] holder)
  3. compareAndSet(expRef, newRef, expStamp, newStamp), stamp+1
  4. Both reference AND stamp must match
  5. Internally boxes an immutable (ref, stamp) holder -> one alloc per update

basics

~20 s

AtomicStampedReference holds a reference plus an int stamp. You read both together with get(int[]), and you compareAndSet the (reference, stamp) pair, bumping the stamp on each update so a value returning to its old self is still detected.

solid answer

~50 s

AtomicStampedReference<V> bundles an object reference with an int 'stamp' (a version number) so CAS can compare both. You read them atomically by passing a one-element int[] to get: it returns the reference and writes the current stamp into the array. To update you call compareAndSet(expectedRef, newRef, expectedStamp, newStamp); it succeeds only if BOTH the reference and the stamp still match what you read, and you conventionally pass newStamp = expectedStamp + 1 so each change advances the version. Because each update advances the stamp, a value that went A→B→A carries a different stamp the second time, so a stale CAS fails and your retry loop re-reads. Internally the (ref, stamp) pair is boxed into an immutable holder swapped atomically, costing one small allocation per successful update. You drive it in the usual read-compute-CAS retry loop; getStamp()/getReference() exist but reading them separately is not atomic, so use the get(int[]) form when you need a consistent snapshot.

code

java · 18 lines
java
AtomicStampedReference<Node> head =
    new AtomicStampedReference<>(initial, 0);

// Lock-free pop whose stamp exposes ABA:
Node pop() {
    int[] holder = new int[1];
    while (true) {
        Node cur = head.get(holder);   // reference + stamp snapshot
        int stamp = holder[0];
        if (cur == null) return null;
        Node next = cur.next;
        // succeeds only if BOTH reference and stamp are unchanged
        if (head.compareAndSet(cur, next, stamp, stamp + 1)) {
            return cur;
        }
        // else: head and/or stamp moved -> retry
    }
}

go deeper

for a junior

Knows AtomicStampedReference stores a reference plus an int stamp and that compareAndSet checks both.

for a middle

Can read with get(int[]) and update with compareAndSet(expRef, newRef, expStamp, newStamp) using stamp+1, and explains the stamp defeats A→B→A.

for a senior

Writes the full read-compute-CAS retry loop, explains why get(int[]) is needed for an atomic snapshot, and knows the internal holder boxing and its per-update allocation cost.

for a principal

Reasons about stamp wraparound limits, when a single mark (AtomicMarkableReference) suffices vs a full version, the allocation/GC trade-offs of the boxed pair under high contention, and how this maps to tagged/double-width CAS in lower-level runtimes.

## What it is `AtomicStampedReference<V>` (in `java.util.concurrent.atomic`) is an atomic holder for **two** things at once: an object **reference** of type `V` and an `int` **stamp**. The stamp is just an integer you control — conventionally a **version counter** you increment on every update. The point is that CAS operates on the *pair*, so two updates that leave the reference equal but advance the stamp are distinguishable. This is how it defeats the **ABA problem** (a value going A→B→A slipping past a value-only CAS). ## Constructing ```java AtomicStampedReference<Node> ref = new AtomicStampedReference<>(initialNode, 0); ``` The second argument is the initial stamp (commonly 0). ## Reading atomically The subtlety: you must read the reference and its stamp **together**, or another thread could change one between your two reads. The API solves this with an out-parameter: ```java int[] stampHolder = new int[1]; Node current = ref.get(stampHolder); // returns the reference... int stamp = stampHolder[0]; // ...and fills in the matching stamp ``` `get(int[] stampHolder)` returns the reference and writes the current stamp into `stampHolder[0]` as one consistent snapshot. There are also `getReference()` and `getStamp()`, but calling them separately is **not** an atomic snapshot — between the two calls another thread may update, so prefer `get(int[])` when you need both consistently. ## Updating atomically ```java boolean success = ref.compareAndSet( current, // expected reference next, // new reference stamp, // expected stamp stamp + 1); // new stamp (advance the version) ``` `compareAndSet` succeeds **only if both** the current reference `==` the expected reference **and** the current stamp equals the expected stamp. On success it installs the new reference and new stamp together. By convention `newStamp = expectedStamp + 1`, so every successful update advances the version. This is exactly what makes A→B→A detectable: the second 'A' carries a stamp two greater than the one you read, so your CAS (which still expects the old stamp) fails. There is also `attemptStamp(expectedRef, newStamp)` to change just the stamp while the reference is unchanged (its Javadoc lets it fail spuriously, so call it in a loop), and `set(newRef, newStamp)` for an unconditional write. ## The retry-loop idiom Like all CAS code you wrap it in a read-compute-CAS loop: ```java int[] holder = new int[1]; while (true) { Node curHead = ref.get(holder); int stamp = holder[0]; Node newHead = compute(curHead); if (ref.compareAndSet(curHead, newHead, stamp, stamp + 1)) break; // CAS failed: someone changed the reference and/or the stamp -> loop } ``` ## How it works inside, and the cost The JVM cannot atomically swap two separate words (reference + int) with one ordinary CAS. So `AtomicStampedReference` boxes the pair into a tiny **immutable holder object** — internally a `Pair<V>` carrying the reference and stamp — and stores a single `volatile` reference to that holder. A `compareAndSet` then CAS-swaps the holder reference. Consequence: each *successful, value-changing* update allocates a new holder object, adding minor allocation/GC pressure. (An optimization avoids allocating when nothing actually changes.) For most code this overhead is negligible compared to the correctness it buys. ## Stamp wraparound The stamp is a 32-bit `int`: `stamp + 1` wraps to a negative number after about 2.1 billion increments from 0, and after 2^32 (about 4.3 billion) it is back at a value seen long ago, re-opening a tiny ABA window. In practice this is astronomically unlikely to coincide with a paused thread holding that exact old stamp, but it is the theoretical limit of the technique; truly paranoid designs use a wider tag. ## When to reach for it - Use `AtomicStampedReference` when you build lock-free structures over a reference that can legitimately return to a prior value (lock-free stacks/queues, free lists, optimistic state machines) and ABA would corrupt them. - If you only need a single 'is it marked/deleted' bit, `AtomicMarkableReference` is lighter. - If the value carries its whole meaning (a counter), you need no stamp at all.

  • Why pass an int[] to get() instead of returning the stamp directly?
    Java methods return one value, but you need the reference and its stamp as one consistent atomic snapshot. The single-element int[] is an out-parameter: get() returns the reference and writes the matching stamp into the array, so both come from the same atomic read. Reading getReference() then getStamp() separately is not atomic and can tear.
  • Is there any cost to using AtomicStampedReference over AtomicReference?
    Yes, a small one. To swap a (reference, stamp) pair atomically the JVM boxes them into an immutable internal holder object and CAS-swaps that holder, so each successful value-changing update allocates a tiny object, adding minor GC pressure. It's usually negligible versus the correctness it provides, and an optimization skips allocation when nothing changed.

  • Reading getReference() and getStamp() in two separate calls and treating them as an atomic snapshot — use get(int[]) instead.
  • Forgetting to increment the stamp on update, which defeats the entire purpose.
  • Believing the (ref, stamp) swap is a free single-word CAS — it actually boxes a holder object, costing an allocation per update.
  • Assuming the int stamp can never wrap — after 2^32 increments (about 4.3 billion) it is back at an old value and reopens a theoretical ABA window.

AtomicStampedReference
Java 1.5

context