What is the best way to implement a thread-safe Integer Counter ?

Overview and Key Facts

  • You may take into account the following JAVA features
    • Using a static volatile int like  :  volatile int num = 0;            –>  NOT WORKING
    • Use a synchronized method  
    • Using AtomicInteger         like  :  final AtomicInteger num = new AtomicInteger();
  • The Java volatile keyword guarantees visibility of changes to variables across threads
  • Using volatile is not enough to create thread safe code
   Lets assume we have 2 threads incrementing a global volatile int as our Thread Counter
     Thread 1 could read a shared counter variable with the value 20 into its CPU cache, increment it to 21
     Thread 2 could read a shared counter variable with the value 20 into its CPU cache, increment it to 21
     Thread 1 writes Thread Counter value [ which is 21 ] to main memory
     Thread 2 writes Thread Counter value [ which is 21 ] to main memory
   Despite we have incremented our Counter 2x the counter value increases only by 1 !
   This problem can occur as the ++ operator is not thread safe !
  • AtomicInteger uses combination of volatile & CAS for thread-safe implementation of Integer Counter.
  • AtomicInteger class stores its value field in a volatile variable, thus it is a decorator over the traditional volatile variable
  • AtomicInteger provides unique non-blocking mechanism for updating the value after requiring the hardware level support for CAS (compare and set).
  • Syncronized access is using locks and therefore slower than CAS method used by AtomicInteger

 

JAVA test case : IncrementNotThreadSafeMain.java

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class IncrementNotThreadSafeMain {
  public static void main(String... args) throws InterruptedException {
    for (int nThreads = 1; nThreads <= 64; nThreads *= 2)
      doThreadSafeTest(nThreads);
  }

  static class VolatileInt {
    volatile int num = 0;
  }

  private static void doThreadSafeTest(final int nThreads) throws InterruptedException {
    final int count = 100 * 1000 * 1000;

    ExecutorService es = Executors.newFixedThreadPool(nThreads);
    final VolatileInt vi = new VolatileInt();
    System.out.printf("--- Testing with Volatile --- ");
    for (int i = 0; i < nThreads; i++)
      es.submit(new Runnable() {
        public void run() {
          for (int j = 0; j < count; j += nThreads)
             vi.num++;
        }
      });
    es.shutdown();
    es.awaitTermination(1, TimeUnit.MINUTES);
    assert es.isTerminated();
    System.out.printf("With %,d threads should total %,d but was %,d%n", nThreads, count, vi.num /*num.longValue()*/);
    
    System.out.printf("--- Testing AtomicInteger --- ");
    es = Executors.newFixedThreadPool(nThreads);
    final AtomicInteger num = new AtomicInteger();
    for (int i = 0; i < nThreads; i++)
      es.submit(new Runnable() {
        public void run() {
          for (int j = 0; j < count; j += nThreads)
              num.incrementAndGet();
        }
      });
    es.shutdown();
    es.awaitTermination(1, TimeUnit.MINUTES);
    assert es.isTerminated();
    System.out.printf("With %,d threads should total %,d but was %,d%n", nThreads, count, num.longValue() );   
  }
}

Running above Code
$  java  IncrementNotThreadSafeMain
--- Testing with Volatile --- With 1 threads should total 100,000,000 but was 100,000,000
--- Testing AtomicInteger --- With 1 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 2 threads should total 100,000,000 but was 54,089,900
--- Testing AtomicInteger --- With 2 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 4 threads should total 100,000,000 but was 44,019,787
--- Testing AtomicInteger --- With 4 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 8 threads should total 100,000,000 but was 24,731,449
--- Testing AtomicInteger --- With 8 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 16 threads should total 100,000,000 but was 28,908,662
--- Testing AtomicInteger --- With 16 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 32 threads should total 100,000,000 but was 37,063,611
--- Testing AtomicInteger --- With 32 threads should total 100,000,000 but was 100,000,000
--- Testing with Volatile --- With 64 threads should total 100,000,000 but was 79,022,174
--- Testing AtomicInteger --- With 64 threads should total 100,000,000 but was 100,000,000

--> All Volatile tests with more then 2 Threads are failing !

Reference

One thought on “What is the best way to implement a thread-safe Integer Counter ?”

Leave a Reply

Your email address will not be published. Required fields are marked *