Does AtomicInteger really produce atomic integer?

Question 1

One major issue with your code is that you add the numbers to a HashSet which is not thread safe. That is the reason for what you are observing. If you used a thread safe collection, you would get the expected result:

final Set<Integer> integers = new ConcurrentSkipListSet<>();

But that introduces an additional layer of synchronization. Another alternative is to use a plain array int[] numbers = new int[1000]; and use: numbers[next-1]++; to count the occurences.

New code for reference:

public static void main(String[] args) throws Exception {

    final AtomicInteger sequencer = new AtomicInteger(1);
    final int[] integers = new int[1000];

    final Runnable task = new Runnable() {

        @Override
        public void run() {
            int next = sequencer.getAndIncrement();
            integers[next-1]++;
        }
    };
    List<Thread> threads = new ArrayList<>();
    for (int i = 0; i < 1000; i++) {
        Thread t = new Thread(task);
        t.start();
        threads.add(t);
    }
    for (Thread t : threads) {
        t.join();
    }
    for (int i = 0; i < 1000; i++) {
        if (integers[i] != 1) System.out.println(i + " -> " + integers[i]);
    }
}

Question 2

If I run your program on my computer, I observe incorrect output about 1 in 10 times. (This is with the console emulator in Netbeans 7.)

However, if I modify it to check the size of the set after all threads are complete, it always contains 1,000 unique integers. This is true even when there are errors in the output generated by the individual threads while it is running. (That is, in the lines printed by the threads, there are duplicates printed, but the true size of the set after execution is complete is actually 1,000)

Therefore I conclude that the problem is having 1,000 threads all writing to the PrintStream that your platform provides for System.out is corrupting the output. On my platform I can see corrupted output during execution, but there are always 1,000 unique integers in the set at the end.

public static void main(String[] args) throws InterruptedException {

    final AtomicInteger sequencer = new AtomicInteger(1);
    final Set<Integer> integers = new ConcurrentSkipListSet<Integer>();

    final Runnable task = new Runnable() {

        @Override
        public void run() {
            int next = sequencer.getAndIncrement();
            integers.add(next);
            System.out.println(next);
        }
    };
    List<Thread> threads = new ArrayList<Thread>(1000);
    for (int i = 0; i < 1000; i++) {
        Thread t = new Thread(task);
        t.start();
        threads.add(t);
    }

    for (Thread t : threads) {
        t.join();
    }
    System.out.println(integers.size());
}

Question 3

AtomicInteger makes calls to the Unsafe class, which in turn makes native calls. So yes AtomicInteger may theoretically return non atomic updates. This would depend on the JVM and and the underlying architecture it is running.

However given the nature of threads I would always assume the bug is in my code not the JVM.

I ran this code and was unable to detect any collisions. JDK 1_7_45 win 7

  public static void main(String[] args) {

      final AtomicInteger sequencer = new AtomicInteger(1);
      final Set<Integer> integers = new HashSet<Integer>();

      final Runnable task = new Runnable() {

          @Override
          public void run() {
              int next = sequencer.getAndIncrement();
              synchronized (integers){
                  if(integers.contains(next)){
                      System.out.println("duplicate detected " + next);
                  }
                  integers.add(next);
              }
          }
      };


      for(int j = 0; j < 1000; j++){
          System.out.print("testing " + j +" ");
          sequencer.set(0);
          integers.clear();
          List<Thread> threads = new ArrayList<Thread>(10000);
          for (int i = 0; i < 1000; i++) {
              Thread t = new Thread(task);
              threads.add(t);
              t.start();
          }
          for (Thread t : threads) {
              try {
                  t.join();
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
          }
          System.out.println("integers size " + integers.size());
      }
  }

Question 4

As others have said:

Wait for all threads to finish at the end of the end of the loop using Thread.join(). References to all the Threads must have been stored in a Collection of course
close() STDOUT before exiting

Around the program:

Pipe the output through sort and/or wc -l
Use diff to check against a list of numbers created by a simple loop
Exit with warning if diff finds a difference

Repeat 10'000 times in a scripted loop.

Report back.

Question 5

The updated output contains 7 ints printed twice.

(took your output | sort | uniq --count | sort )

prints this at the end (first col is number of times seen, 2nd col is the value)

This is because you are printing the size of the HashSet which is not threadsafe so sometimes the size isn't showing the updated value.

Changing to a threadsafe Set implementation should work.

Question 6

To me, it's because of ConcurrentSkipListSet.size(). This kind of weakly consistent collection although thread-safe are not precise on iterations or counting in general.

From Javadoc of ConcurrentSkipListSet.size()

Beware that, unlike in most collections, the size method is not a constant-time operation. Because of the asynchronous nature of these sets, determining the current number of elements requires a traversal of the elements. Additionally, the bulk operations addAll, removeAll, retainAll, and containsAll are not guaranteed to be performed atomically. For example, an iterator operating concurrently with an addAll operation might view only some of the added elements.