Lazy concurrent map value initialization

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Lazy concurrent map value initialization

Doug Lea
Lazy initialization of map values in ConcurrentMaps is starting to be
a FAQ. It is a variant of the famous double-checked lazy
initialization problem. In both cases, there are no universal answers, but
some common approaches.  Here's a start, including some variants that
Joe has posted in reply to similar questions.  Feel free to add
others.

Problem:
   You have a ConcurrentMap map, where each key maps to a value that
   should be constructed and put into the map only if the key is not
   already mapped.

Solutions

1. Just use map.putIfAbsent(key, new Value(...)).

This applies when constructing the Value doesn't have any irreversible
side effects, so it doesn't hurt to throw it away if already entered
into the map. When contention is expected to be rare, it is even OK if
constructing a new Value is expensive, since it will rarely happen.
(In general, don't be too afraid of occasionally wasting effort
especially on multiprocessors. It is usually cheaper than
blocking. But always verify whether this holds in your application.)

(Aside. The Java Concurrency in Practice book has some examples of
such usages.)

1a. You can further minimize wasted effort by using:
     if (!map.contains(key))
       map.putIfAbsent(key, new Value(...));

This narrows the window in which you might create multiple Values,
but adds overhead for each put.

1b. If applicable, you can also invoke a rollback action if you
lose race to insert, as in:
     if (!map.contains(key))
       if (map.putIfAbsent(key, new Value(...) != null))
          undoEffectsOfCallingNewValue(...);

This might apply if you need to close a connection or somesuch.


2. Use a wrapper around Value classes that perform lazy initialization
on first access. One way to do this is to declare the map as Map<Key,
Future<Value>>, and define a simple custom Future<Value> such as:

   class FutureValue implements Future<Value> {
      private volatile Value value;
      public Value get() {
         Value v = value;
         if (v == null)
            value = v = // initialize, probably under some lock
         return v;
      }
      public boolean isDone() { return value != null; }
      public Value get(long timeout, TimeUnit unit) { return get(); }
      // Don't need cancellation support:
      public boolean isCancelled() { return false; }
      public boolean cancel(boolean interrupt) { return false; }
   }

Or use a FutureTask, especially if you'd like this run in a different
thread. (Java Concurrency in Practice also has some examples of this.)

The main disadvantage is that it imposes an extra level of
indirection, which is usually not a performance concern but may be a
usage concern.  All users of the map must be prepared for map.get(key)
to return a Future, which if non-null, must be dereferenced via
future.get() in order to use.


3. Define the Value class to itself perform lazy initialization on
first use. As in:

   class Value {
      private volatile boolean initialized;
      // lots more fields ...
      public void someMethod() {
         if (!initialized) initialize(); // probably under some lock
         // ... perform method action
      }
   }

This has the disadvantage of requiring initialization checks
on each method call.


4. Define a special RESERVED sentinel Value, and use it as a
reservation, in code looking something like (there are many variants):

    Value v = map.get(key);
    if (v == null && (v = map.putIfAbsent(key, RESERVED)) == null)
       v = RESERVED;
    if (v == RESERVED) {
       v = // initialize, probably under some lock
       if (!map.replace(key, RESERVED, v))
           v = map.get(key);
    }

This has the disadvantage that all users will need to deal with
RESERVED as a value for get, put, etc. You can/should avoid this by
declaring a special purpose Map class that delegates get, put etc to a
ConcurrentMap, and performs these actions inside get, put, etc.  Also,
it only applies when you can come up with a reasonable RESERVED
value. Without generics, you can use
   static final RESERVED = new Object();
With generics, you'd need to either find a way for RESERVED to be an
actual instance of Value class, or internally use a raw Object type,
and use casts within each method.


5. Instead of calling new Value(...) call a factory method that
returns an existing instance if available, as in
   map.putIfAbsent(key, Value.create(...));
This just defers the issue one level deeper, but might apply if for
example Value is a singleton object, in which case you can use either
double-check (with a volatile reference!) or static holders.


6. Give up on ConcurrentMaps, and use custom synchronization wrappers
on unsynchronized maps (HashMap, TreeMap). You can then define
   synchronized void createIfAbsent(K key) {
     if (!map.contains(key))
         map.put(key, new Value())
    }

The disadvantage is much poorer throughput for concurrent operations.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest