Monday, May 28, 2007

Efficient Concurrency

There are many ways to write thread-safe code for situations where concurrent readers and writers modify a shared data-structure:
  • Using locks: but this is very inefficient under high read-write load, especially because multiple readers interfere with each other.
  • Using read-write locks: this works better, because readers can run concurrently while no writes are taking place.
  • Using non-blocking algorithms based on the Compare-and-Swap (CAS) primitive: this works very well at low to moderate load levels, but makes the application code more complicated.
  • Using striping: where different sections of a large structure are protected with different locks (java.util.concurrent.ConcurrentHashMap uses this technique)
  • Using copy-on-write structures: where a new copy of a structure is made on every write. Reads do not interfere with each other. This works well if the number of reads are much, much higher than the number of writes.
  • Using immutable, functional structures: this is arguably the best way to manage concurrency. Reads do not interfere with each other. Writes need to acquire a lock for a very short time while replacing the root of the structure.

On to some real code. Here's an immutable/functional List that I recently implemented:
http://jiva.googlecode.com/svn/trunk/jiva/src/net/xofar/util/collection/immutable/List.java


The basic ideas behind the implementation of the above class are:
  • The List class is abstract.
  • List has two subclasses: Cons and Nil.
  • Nil stands for an empty list.
  • A Cons has two cells. One holds a value; the other points to the rest of the List. So a Cons essentially implements a singly-linked list.
  • The last entry in a list is a Nil. At this point in the list, the rest of the list is empty.
  • As a user of the List class, you never see Cons and Nil. You create a List using a factory method, and then use List operations to work on the list.
  • The core List operations are:
public List<T> prepend(T elem)
public T head();
public List<T> tail();
public boolean isEmpty();
public List<T> remove(T elem);

Some interesting things to note about these operations are:
  • The only way you can add something to a list is to prepend() to it. This returns a new list with the additional element. Threads that already hold a reference to the list continue to see the list as it was before the prepend.
  • head() and tail() give you a clean way to iterate through the list.
  • isEmpty() allows you to check for the end of the list.
  • As a concession to the need for modification, List supplies a remove(T elem) method. This gives you back a new list that does not contain the supplied element. The implementation of this method uses an optimized form of copy-on-write.
In a future post, I will talk about a good use for immutable/functional lists in a highly concurrent situation. These kinds of lists also lend themselves very well to algorithms that build their results in a bottom-up fashion (this will be the subject of yet another post).

Thursday, May 24, 2007

A FutureResult based on FutureTask

This morning, I was looking within the java.util.concurrent package for something in the spirit of the FutureResult class in Doug Lea's util.concurrent library. Surprisingly enough, I did not find anything (did I miss something?).

So I cooked up my own version:

public class FutureResult<V> {
volatile V result;

volatile Exception problem;

final FutureTask<V> resultSyncer;

public FutureResult() {
Callable<V> resultReturner = new Callable<V>() {
public V call() throws Exception {
if (problem != null) {
throw problem;
} else {
return result;
}
}
};
resultSyncer = new FutureTask<V>(resultReturner);
}

public void set(V result) {
this.result = result;
resultSyncer.run();
}

public void setException(Exception problem) {
this.problem = problem;
resultSyncer.run();
}

public V get() throws InterruptedException, ExecutionException {
return resultSyncer.get();
}
}


The latest code for this class is available at:
http://jiva.googlecode.com/svn/trunk/jiva/src/net/xofar/util/concurrent/FutureResult.java

Functionality of this nature can, of course, also be implemented with the help of plain-old wait/notify or condition variables. But this seemed like a neat way to accomplish what I wanted...