The simple way to implement multi-threaded applications is to use Java’s built-in synchronization and locking primitives; e.g. the synchronized keyword. The following example shows how we might use synchronized to accumulate counts.

public class Counters {
    private final int[] counters;

    public Counters(int nosCounters) {
        counters = new int[nosCounters];
    }

    /**
     * Increments the integer at the given index
     */
    public synchronized void count(int number) {
        if (number >= 0 && number < counters.length) {
            counters[number]++;
        }
    }

    /**
     * Obtains the current count of the number at the given index,
     * or if there is no number at that index, returns 0.
     */
    public synchronized int getCount(int number) {
        return (number >= 0 && number < counters.length) ? counters[number] : 0;
    }
}

This implementation will work correctly. However, if you have a large number of threads making lots of simultaneous calls on the same Counters object, the synchronization is liable to be a bottleneck. Specifically:

1. Each synchronized method call will start with the current thread acquiring the lock for the Counters instance.
2. The thread will hold the lock while it checks number value and updates the counter.
3. Finally, the it will release the lock, allowing other threads access.

If one thread attempts to acquire the lock while another one holds it, the attempting thread will be blocked (stopped) at step 1 until the lock is released. If multiple threads are waiting, one of them will get it, and the others will continue to be blocked.

This can lead to a couple of problems:

• If there is a lot of contention for the lock (i.e. lots of thread try to acquire it), then some threads can be blocked for a long time.
• When a thread is blocked waiting for the lock, the operating system will typically try switch execution to a different thread. This context switching incurs a relatively large performance impact on the processor.
• When there are multiple threads blocked on the same lock, there are no guarantees that any one of them will be treated “fairly” (i.e. each thread is guaranteed to be scheduled to run). This can lead to thread starvation.

How does one implement Atomic Types?

Let us start by rewriting the example above using AtomicInteger counters:

public class Counters {
    private final AtomicInteger[] counters;

    public Counters(int nosCounters) {
        counters = new AtomicInteger[nosCounters];
        for (int i = 0; i < nosCounters; i++) {
            counters[i] = new AtomicInteger();
        }
    }

    /**
     * Increments the integer at the given index
     */
    public void count(int number) {
        if (number >= 0 && number < counters.length) {
            counters[number].incrementAndGet();
        }
    }

    /**
     * Obtains the current count of the object at the given index,
     * or if there is no number at that index, returns 0.
     */
    public int getCount(int number) {
        return (number >= 0 && number < counters.length) ? 
                counters[number].get() : 0;
    }
}

We have replaced the int[] with an AtomicInteger[], and initialized it with an instance in each element. We have also added calls to incrementAndGet() and get() in place of operations on int values.

But the most important thing is that we can remove the synchronized keyword because locking is no longer required. This works because the incrementAndGet() and get() operations are atomic and thread-safe. In this context, it means that:

• Each counter in the array will only be observable in the either the “before” state for an operation (like an “increment”) or in the “after” state.
• Assuming that the operation occurs at time T, no thread will be able to see the “before” state after time T.

Furthermore, while two threads might actually attempt to update the same AtomicInteger instance at the same time, the implementations of the operations ensure that only one increment happens at a time on the given instance. This is done without locking, often resulting in better performance.

How do Atomic Types work?