Why AtomicReference CAS return false with value 128?

Question

I was using AtomicReference to implement AtomicInteger. However while in testing I notice even in single threaded environment the CAS operation got stuck once its value hit 128.. Am I doing something wrong or there is a caveat in AtomicReference (may be related to CPU)? Here is my code:

public class MyAtomInt {
  private final AtomicReference<Integer> ref;

  public MyAtomInt(int init) {
    ref = new AtomicReference<Integer>(init);
  }

  public MyAtomInt() {
    this(0);
  }

  public void inc() {
    while (true) {
      int oldVal = ref.get();
      int nextVal = oldVal + 1;
      boolean success = ref.compareAndSet(oldVal, nextVal); // false once oldVal = 128
      if (success) {
        return;
      }
    }
  }

  public int get() {
    return ref.get();
  }

  static class Task implements Runnable {

    private final MyAtomInt myAtomInt;
    private final int incCount;

    public Task(MyAtomInt myAtomInt, int cnt) {
      this.myAtomInt = myAtomInt;
      this.incCount = cnt;
    }

    @Override
    public void run() {
      for (int i = 0; i < incCount; ++i) {
        myAtomInt.inc();
      }
    }
  }

  public static void main(String[] args) throws Exception {
    MyAtomInt myAtomInt = new MyAtomInt();
    ExecutorService exec = Executors.newSingleThreadExecutor();
    exec.submit(new Task(new MyAtomInt(), 150)).get();
    System.out.println(myAtomInt.get());
    exec.shutdown();
  }
}

Contempt

Why are you trying to implement your own AtomicInteger when the JDK provides it? Are you on a platform where it isn't supported, or is this an exercise? – Lucialucian

This is just a practice to get familiar with the java.util.concurrent.atomic package, and yes we definitely don't need to re-invent the wheels :) – Contempt

Answer 1

The reason for this is that when you box an int into an Integer, you may or may not create a new Integer instance. If you do, then the new instance may not have reference equality with other Integer instances, even if they share the same value. AtomicReference.compareAndSet() uses reference equality (identity) for comparisons.

The key is in how the compiler handles automatic boxing of int values: it emits calls to Integer.valueOf(). As an optimization, Integer.valueOf() has a cache of boxed integers, and by default that cache includes values up to 128. If you box an integer n twice, you will get the same Integer reference back each time if the value was small enough to be in the cache; otherwise, you will get two separate instances.

Currently, you unbox the old value, compute the new value, and when you call compareAndSet() you box the old value again. Once you hit 128, you stop getting cached values, so the second boxed copy is no longer the same one that's in the AtomicReference.

Bark

Thanks, that solved my problem! I was not aware that AtomicReference.compareAndSet() is based on reference comparison. After I replace the int oldVal = ref.get(); with Integer oldVal = ref.get(); to avoid auto-boxing, the code works fine. – Contempt

Great! Keep this in mind when if you have to implement AtomicInteger.compareAndSet() using an AtomicReference :). – Bark

And +1 for your explanation of Integer.valueOf() cache mechanism. – Contempt