[concurrency-interest] Can this be done with ConcurrentHashMap ?

Donnie Hale donnie@haleonline.net
Thu, 23 Dec 2004 19:20:25 -0500


Tim, Doug, Brian, & Larry - I appreciate the prompt and on-point responses.
Two follow-ups:

1) In the code below, I want to make sure I understand what is supposed to
happen in Memoize.compute, within the outermost "if (f == null)" block. It
would seem that two threads could both get into this block if
"cache.get(arg)" returns null. Assuming I've got that right, then we have 2
threads instantiating a FutureTask and attempting to put it in the map via
"cache.putIfAbsent". However, only one of those threads will win; and the
other will be returned the winning thread's FutureTask. Only the winning
thread will run the FutureTask. Not being up-to-speed on Futures and
FutureTasks, I'm guessing that even if the losing thread executes the line
"return f.get()" first, it will not return until "ft.run()" completes in the
winning thread?

2) I'll admit to being a little disappointed. A host of wonderful new
concurrency utilities have been released, and, the first time I go to use
them, I come up against this. I believe based on the similarity of responses
that what I've presented is a recurring pattern. Yet a direct solution isn't
provided so I have to do some cut-and-paste of the (obviously useful) code
that's been provided. It would seem that if in fact this is a common pattern
that the solution would be provided more directly.

Thanks again for the responses,

Donnie


-----Original Message-----
From: Tim Peierls [mailto:tim@peierls.net] 
Sent: Thursday, December 23, 2004 11:51 AM
To: Donnie Hale
Cc: concurrency-interest@altair.cs.oswego.edu; Joseph Bowbeer
Subject: Re: [concurrency-interest] Can this be done with ConcurrentHashMap
?

Donnie Hale wrote:
> Assuming what I want to do is clear, is this possible with a 
> ConcurrentHashMap?

Here's a general solution that uses ConcurrentHashMap that you can adapt for
your purposes. This is code that Joe Bowbeer wrote and presented at a
JavaOne talk; I don't think there are any limitations on its use. (Joe,
speak up if you think there might be.)

public interface Computable<A, V> {
     V compute(A arg) throws Exception;
}

public class Memoize<A, V> implements Computable<A, V> {
     public Memoize(Computable<A, V> c) {
         this.c = c;
     }
     public V compute(final A arg) throws Exception {
         Future<V> f = cache.get(arg);
         if (f == null) {
             Callable<V> eval = new Callable<V>() {
                 public V call() throws Exception {
                     return c.compute(arg);
                 }
             };
             FutureTask<V> ft = new FutureTask<V>(eval);
             f = cache.putIfAbsent(arg, ft);
             if (f == null) { f = ft; ft.run(); }
         }
         return f.get();
     }
     private final ConcurrentMap<A, Future<V>> cache =
         new ConcurrentHashMap<A, Future<V>>();
     private final Computable<A, V> c;
}

You would use this as follows:

   class MyLengthyOperation implements Computable<Key, Value> {
       public Value compute(Key key) {
           // Lengthy operation here, takes key and returns
           // a value.
       }
   }

   // instead of map:
   Computable<Key, Value> map =
       new Memoize<Key, Value>(new MyLengthyOperation());

   // and then you can get values:

   for (Key key : interestingKeys) {
       Value value = map.compute(key);
       // do something with value
   }

--tim