AtomicInteger incrementation not behaving as expected

Question

I was reading about AtomicInteger and how its operations are atomic and how these properties make it useful for multithreading.

I wrote the following program to test the same.

I am expecting the final size of the set should be 1000, since each thread loops 500 times and assuming each time a thread calls getNext() it should get a unique number.

But the output is always less than 1000. What am i missing here?

public class Sequencer {

private final AtomicInteger i = new AtomicInteger(0);

public int getNext(){
    return i.incrementAndGet();
}

public static void main(String[] args) {

    final Sequencer seq = new Sequencer();

    final Set<Integer> set = new HashSet<Integer>();

    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            for (int i=0; i<500; i++)
                set.add(seq.getNext());

        }
    },"T1");
    t1.start();


    Thread t2 = new Thread(new Runnable() {
        @Override
        public void run() {
            for (int i=0; i<500; i++)
                set.add(seq.getNext());

        }
    },"T2");

    t2.start();

    try {
        t1.join();
        t2.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

    System.out.println(set.size());

}

}

Answer 1

You are missing that HashSet is not thread-safe. In addition the properties of a set would erase all duplicated numbers, so your test would fail if AtomicInteger was not thread-safe.

Try using a ConcurrentLinkedQueue instead.

Edit: Because it has been asked twice: Using a synchronized set works, but it destroys the idea behind using a lock-free algorithm like the Atomic-classes. If in your code above you replace the set with a synchronized set, then the threads will have to block each time add is called.

This will effectively reduce your application to single-threaded, because the only work done happens synchronized. Actually it will even be slower than single-threaded, because synchronized takes its toll as well. So if you want to actually utilize threading, try to avoid synchronized at all cost.

Answer 2

Try do it in that way using Collections synchronized.

public class Sequencer {

    private final AtomicInteger i = new AtomicInteger(0);

    public static void main(String[] args) {

        final Sequencer seq = new Sequencer();

        final Set<Integer> notSafe = new HashSet<Integer>();
        final Set<Integer> set = Collections.synchronizedSet(notSafe);
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 500; i++)
                    set.add(seq.getNext());

            }
        }, "T1");
        t1.start();


        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 500; i++)
                    set.add(seq.getNext());

            }
        }, "T2");

        t2.start();

        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println(set.size());

    }

    public int getNext() {
        return i.incrementAndGet();
    }
}

Answer 3

HashSet is not thread safe so you are facing problem.You can use Vector or any collection class which is thread safe or run two thread sequentially if you stricly need to use HashSet.

t1.start();
t1.join();

t2.start();
t2.join();

Answer 4

As mentioned in several answers, it fails due to HashSet not being thread safe.

First, lets verify for the sake of your test, that AtomicInteger is indeed thread-safe then proceed to see why your test failed. Modify your test slightly. Use two hashsets, one for each thread. Finally, after joins, merge the second set into the first, by iterating over the second and adding it to the first which will eliminate duplicates(set property). Then do a count on the first set. The count will be what you expect. This proves that it is HashSet that is not thread safe and not the AtomicInteger.

So lets look at what aspect is not thread safe. You're doing onlyf add()s, so clearly add() is the operation that is not thread safe causing the loss of numbers. Lets look at an example pseudo-code non-thread safe HashMap add() that would lose numbers(this is obviously not how it implemented, just trying to state one way in which it could be non-thread safe):

class HashMap {
 int valueToAdd;
 public add(int valueToAdd) {
   this.valueToAdd = valueToAdd;
   addToBackingStore(this.valueToAdd);
 }
}

If multiple threads call add() and they all reach the addToBackingStore() after they've changed this.valueToAdd, only the final value of valueToAdd is added, all other values are overwritten and lost.

Something similar to this is probably what happened in your test.