Futures and Eventual Values Part 1

Last Wednesday evening I gave a presentation on the "Futures" concurrency pattern at the Melbourne Patterns Group. Given that a couple of people have stated that they regret missing out on the presentation, and given that the power point presentation will be of little use without the talking that went with it, I thought that I should blog about the topic.

I first came across the concept of a Future six or so years ago while working on a C++ project a Ericsson. I found them to be an elegant and useful approach to certain types of concurrency problems. Since that time, most of my programming has been targetted at J2EE environments where creating your own threads is generally frowned upon and hence I have never had to use a Future since. So I have had fun this last month doing a bit of research on concurrency patterns and looking at the new concurrency library in the JDK 1.5.

A future is a placeholder for a value of an expression being computed by a separate thread.

I believe that the idea dates back to a language called Multilisp (see R. Halstead, Multilisp: A Language for Concurrent Symbolic Computation, TOPLAS pp.501-538 (Oct 1985). Available from the ACM digital library (http://www.acm.org/)). This paper in turn refers to Algol 68 (Algol 68 User Manual. March 8, 1978. http://members.dokom.net/w.kloke/a68s.txt) which has a similar feature called an Eventual Value.

I am not entirely sure that I understand the difference between an eventual value and a future, but I think that there is a difference as I will try to explain.

First, I will explain what I think an eventual value is. Given that most of us have been brainwashed into thinking in terms of objects, you can think of an eventual value as being a wrapper around a value and having a get() method and a set() method to get and set that value. The eventual value is deemed to initially be in an undetermined state and to remain so until the value is set via the set() method. After the set() method is called the eventual value is said to be in a determined state.

If the eventual value is in a determined state, then calls to the get() method will return the wrapped value without blocking. Otherwise, the get() method will block until some thread calls the set() method.

Imagine we are writing a remote proxy for a weather service able to return the current temperature of a specified city. Due to network latency and the load on the remote service, such a request could take several seconds to return. If we wish the get temperatures from a number of different services, then we can reduce the overall latency by making those requests concurrently. One way of achieving this is for our remote proxy to return eventual values like so:

public class WeatherService {

.....

 public EventualValue getTemperature() {
  final EventualValue result = new EventualValue();
  new Thread() {
   public void run() {
    result.set(remoteWeatherStation.getTemperature());
   }
  }.start();
  return result;
 }
}

The intention is that WeatherService is able to fetch the current termperature of a specified city from a remote service. Rather than waiting for the remote service to reply, the getTemperature() method creates and returns an eventual value, while concurrently making the remote request in a separate thread. When the remote request returns (possibly several seconds later), that thread will call the set() method on the eventual value with the result.

Consider the following possible client code:

WeatherService melb = new WeatherService("Melbourne");
WeatherService sydney = new WeatherService("Sydney");
WeatherService brisbane = new WeatherService("Brisbane");
EventualValue<Float> melbTemperature = melb.getTemperature();
EventualValue<Float> sydneyTemperature = sydney.getTemperature();
EventualValue<Float> brisbaneTemperature = brisbane.getTemperature();
System.out.println("City\t\tTemperature");
System.out.println("Melbourne\t" + melbTemperature.get());
System.out.println("Sydney\t\t" + sydneyTemperature.get());
System.out.println("Brisbane\t" + brisbaneTemperature.get());

The three calls to getTemperature() will each return immediately, and the main thread will not actually block until it reaches melbTemperature.get(). At that point, the thread will block until the remote service returns its value. When the main thread reaches the next line and tries to call sydneyTemperature.get(), it is possible that the remote service has already returned the Sydney temperature, otherwise that call will also block. Either way, the total wall clock time taken to fetch and print the three temperatures should be significantly less than the sum of the times taken to get each temperature individually.

A fairly crude implementation of an EventualValue class might look something like this:

public class EventualValue<T> {
 private T value;

 private boolean ready = false;

 public synchronized void set(T value) {
  this.value = value;
  ready = true;
  notifyAll();
 }

 public synchronized T get() throws InterruptedException {
  while (!ready) {
   wait();
  }
  return value;
 }

}

A real one would supply more methods, e.g. a get() method that takes a timeout. It may also use a separate object for synchronization purposes to prevent clients explicitly performing synchronization operations on the EventualValue themselves.

If you are using Java, you should try to use the features of the new currency library. It comes with the JDK1.5, and you can download a version for older versions of Java. However, instead of providing support for eventual values, Java provides support for futures, and I think a discussion of futures and how I think they differ from eventual values deserves a separate blog.