Fast, thread-safe Thunk in Java

6 months ago or so I was going through Wealthfront’s website when I stumbled upon their recruiting puzzle for the “Backend software engineer” position. The page is still online but not linked under their Available Positions list so I guess it’s alright to publicly discuss that puzzle.

The puzzle reads

Provide an alternate implementation of the following class (a thunk) that uses no conditional logic. For extra credit, make it thread-safe.

abstract class Thunk<T> {
  private boolean evaluated;
  private T value;
  public T get() {
    if (!evaluated) {
      value = compute();
      evaluated = true;
    }
    return value;
  }
  abstract protected T compute();
}

The first thing that came to me was to (ab)use the exception system:

abstract class Thunk<T> {
   private T value;
   public T get() {
      try {
         value.getClass();
      } catch (NullPointerException e) {
         value = compute();
      }
      return value;
   }
   abstract protected T compute();
}

There are two problems with this though:

  • Using exceptions for flow control is ugly, violates the principle of least astonishment and chances are a kitten will die every time this runs.
  • There is quite a lot of room for argument on whether this is conditional logic or not.

My next thought was about the state pattern:

Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.

In our context that would mean that once the value is computed, the Thunk’s behavior should change to just returning the computed value:

abstract class Thunk<T> {
   private static abstract class ThunkGetter<T> {
      abstract T get();
   }
   private ThunkGetter<T> tGetter = new ThunkGetter<T>() {
      T get() {
         final T value = evaluate();
         tGetter = new ThunkGetter<T>() {
            T get() {
               return value;
            }
         };
         return value;
      }
   };
   public T get() {
      return tGetter.get();
   }
   abstract protected T compute();
}

Going for the extra credit we have to make this thread safe.
We can use a variation of Double-checked locking using Java’s volatiles:

abstract class Thunk<T> {
   private static abstract class ThunkGetter<T> {
      abstract T get();
   }
   private volatile ThunkGetter<T> tGetter = new ThunkGetter<T>() {
      synchronized T get() {
         final T value = evaluate();
         tGetter = new ThunkGetter<T>() {
            T get() {
               return value;
            }
         };
         return value;
      }
   };
   public T get() {
      return tGetter.get();
   }
   abstract protected T compute();
}

Any ideas for alternative solutions?

Advertisements

Posted on July 5, 2011, in Java. Bookmark the permalink. Leave a comment.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: