A couple weeks ago I came across some code that used an instance of an AtomicInteger, which is part of the java.util.concurrent.atomic package, which I believe the majority of which was written by Doug Lea, author of the excellent util.concurrent library. I wrote the class name down in my todo.txt thinking that it would be interesting to find out how AtomicInteger (and all the other atomic related classes) give you the ability to increment a shared integer in a multi-threaded environment, but I didn’t get around to it until this past weekend. If you’re not familiar with the atomic classes in JDK 5.0, the big takeaway is that they “…support lock-free thread-safe programming on single variables”. In code that means that if you have this:

public final class Counter {
  private long value = 0;
  public synchronized long getValue() {
    return value;
  }

  public synchronized long increment() {
    return ++value;
  }
}

you should be using something more like this:

public class NonblockingCounter {
    private AtomicInteger value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        while (!value.compareAndSet(v, v + 1));
        return v + 1;
    }
}

Regardless of your familiarality, herewith are some notes on my research:

• I downloaded the source code for JDK 5.0 and popped open the source for AtomicInteger, skipping down to the getAndIncrement method. The source for that method is curious, to say the least. It starts with a for loop that never ends, retrieves the current int value, adds one to that value and then fires the compareAndSet method, only returning if the compareAndSet method returns true. It took me a couple minutes to wrap my brain around this small block of code: no locking and what looks like an endless loop. Here it is if you don’t feel like downloading the code yourself:

      public final int getAndIncrement() {
          for (;;) {
              int current = get();
              int next = current + 1;
              if (compareAndSet(current, next))
                  return current;
          }
      }
  

  What’s remarkable about this block is that it seemingly ignores the fact that it was designed to be accessed simultaneously by multiple threads… and in fact that’s exactly how it was designed. If this method were a conversation between a person and a machine, it might go something like this:

  Person: Get me the current value!
  Machine: 1
  Person: Add one to that value!
  Machine: 2
  Person: If 1 is equal to the current value, then set the current value to 2, otherwise, let’s do it all over again!
  Machine: Try again.
  Person: WEEE! Let’s try again!

  I think the exclamation points are apt in this case because it turns out that the atomic classes use algorithms that are sometimes called ‘optimistic’ (which is probably not a trait that you ascribe to most programmers unless they’re talking about schedules) but are described on Wikipedia (and probably elsewhere) as ‘lock-free’ or ‘wait-free’ algorithms. They’re optimistic in the sense that they assume the best case:

  I’m sure that no other threads will be accessing the method when I’m using the method. Even if they do, I don’t care, I’ll just try again (and again and again)…

  Optimistic. The pessimistic version assumes the worst case:

  I’m sure some other thread will be trying to access the method when I’m using the method. I’ll have to block them from using it every time I invoke this method.

  If you check out the Wikipedia article I linked to above, you’ll see the implementation of these lock-free algorithms use atomic primitives, the notable one being the ‘compare and swap‘; the getAndIncrement method on the AtomicInteger class in Java has a corresponding compareAndSet method, which is backed by a class called Unsafe, which itself doesn’t have publicly available documentation. However, if you download the JDK 5.0 source code like I did and peek at it, you’ll see a method that looks like this:

  public final native boolean compareAndSwapInt(Object o, long offset, int expectedValue, int newValue);
  

  And that’s where the source code adventure stopped. If I’m understanding the method signature correctly, it means Sun has a native library (written in C?) for every OS that sets the value of the Object o at memory location ‘offset’ to value ‘newValue’ if the current value is equal to ‘expectedValue’.

• I found a really really great article on IBM developerWorks by Brian Goetz¹ called “Going atomic” (you’ll probably recognize the Counter and NonBlockingCounter examples I posted above). In it he does a great job describing compare and swap and the difference between a lock-free and wait-free implementation and then, just to show off, shows some benchmarking graphs that compare synchronization, ReentrantLock, fair Lock and AtomicLong on an 8-way Ultrasparc3 and a single-processor Pentium 4.

  You should also read his articles on developerWorks called More flexible, scalable locking in JDK and Introduction to nonblocking algorithms.

• Dave Hale wrote an article that discusses the use of AtomicIntegers in a multi-threaded environment called “Parallel Loops with Atomic Integers“. He also pointed out an article published in the March 2005 edition of Dr. Dobb’s Journal called “The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software“.

Hope you learned something today!

¹: I saw Brian speak at the No Fluff Just Stuff Symposium in Boston last fall. He’s as good in person as he is on paper. Go hear him speak if you have a chance.