The more I learn about multi-threaded programming, the harder it gets. Coordinating multiple threads modifying the same data is complicated. The java.util.concurrent.ConcurrentHashMap, for example, needs with 4264 lines of code two times more lines of code than its single threaded counterpart the java.uti.HashMap with 1617 lines of code.

So I think the best solution for concurrent programming is to avoid shared state.

The first technique to avoid shared state is to copy the data before each modification. This technique relies on the fact that updating a single variable is easy. Only when we need to update multiple variables things get complicated.

Copy before modification

The following shows this technique using a java.util.concurrent.locks.ReentrantLock for writing and a volatile field for reading:

final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;  
public E get(int index) {
     return (E) array[index];
}   
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
       Object[] elements = array;
       E oldValue = (E) elements[index];
       if (oldValue != element) {
          int len = elements.length;
          Object[] newElements = Arrays.copyOf(elements, len);
          newElements[index] = element;
          array = newElements;
      } else {
          // Not quite a no-op; ensures volatile write semantics
      array = elements;
       }
          return oldValue;
    } finally {
    lock.unlock();
    }
}    

The example is based on the class java.util.concurrent.CopyOnWriteArrayList.

Reading consists of reading the volatile variable array and then the ith array element, line 4. Writing consists of Locking the ReentrantLock, line 7. Then if the current element and the new array element are no the same, creating a local copy of the array, line 14, modifying the local copy, line 15 and finally setting the array variable to the newly created array, line 16. Why we need a volatile variable instead of a normal variable is explained in this blog post.

The technique implies to copy the data structure each time we want to modify the data structure. Using so-called persistent data structures we can avoid copying the complete data structures. Persistent data structures keep the old state together with the modification. This post by the bifurcan project compares different libraries which implement persistent data structures.

Copying before modifying works best for workloads consisting of multiple reads and few writes. The second technique work best for the opposite type of workloads, multiple writes and only a few reads:

Asynchronous modification using a single thread

The idea of this technique is to use a single thread which owns the state and a messaging queue to let other threads modify the state through this thread. The following example shows how to implement this technique using the ExecutorService:

ExecutorService executor = Executors.newFixedThreadPool(1);
executor.execute( () -> modifyState() );
executor.execute( () -> modifyState() );
executor.shutdown();
executor.awaitTermination(10, TimeUnit.MINUTES);

To implement this technique with a single threaded ExecutorService we first need to create one, line 1. Then we can modify the state asynchronously using the execute method, line 3 and 4. When we are done we need to stop the ExecutorService, line 4 and wait till the service is terminated, line 5.

Martin Thompson recommends this technique in this blog post for highly contended data structures. The single event processing thread of UI libraries like SWING or SWT is another example usage of this technique. And the idea behind the Akka framework to use messaging between actors instead of shared state is similar to this technique.

What is next?

The two techniques presented here are described in further detail in the book Java Concurrency in Practice by Brian Goetz et al. This book is the best resource to learn concurrent programming.

To start with avoiding shared state we need to know which parts of our application uses shared state. I added a report in vmlens, a tool I developed to test multi-threaded Java, which shows which method uses shared state. This report is described here.

And if you are interested in writing concurrent collections like the mentioned ConcurrentHashMap read the book The Art of multiprocessor programming by Maurice Herlihy and Nir Shavit. This book explains how commonly used data structures can be implemented for multi-threaded access.