Why is there a loop in getAndSet() of AtomicInteger and similar classes?

Question

For what purpose a loop is used in this code

public final int getAndSet(int newValue) {
    for (;;) {
        int current = get();
        if (compareAndSet(current, newValue))
            return current;
    }
}

Answer 1

There is a school of thought that states that you should use locks as frugally as you can. I.e. never use a lock if you can avoid it, and if you must use one, lock for the minimum time. The reasoning behind this stems from the sometimes considerable cost of taking the lock in the first place along with the cost of one thread waiting while another holds a lock on a resource it needs.

There has been available for a very long time, cpu instructions called Compare and Set (or CAS for short) designed to help with this that essentially do:

if (value == providedValue) {
  value = newValue;
  return true;
} else {
  return false;
}

these instructions can execute at machine-code level and are significantly faster than creating a lock.

Imagine you want to add 1 to a number using one of these instructions in a way that will consistently work correctly under high parallel load. Clearly you could code it as:

int old = value;
if ( compareAndSet(old, old+1) ) {
  // It worked!
} else {
  // Some other thread incremented it before I got there.
}

But what could we do if the CAS failed? You guessed it - try again!

boolean succeeded = false;
do {
  int old = value;
  if ( compareAndSet(old, old+1) ) {
    // It worked!
    succeeded = true;
  } else {
    // Some other thread incremented it before I got there. Just try again.
  }
} while (!succeeded);

And there you see the pattern you observe.

Using this and similar idioms it is possible to implement many functions and even some quite complex data structures using no locks at all (commonly called Lock Free). For example, here is a Lock-Free implementation of a Ring Buffer.