[concurrency-interest] Adding a createIfAbsent() API?

Doug Lea dl at cs.oswego.edu
Mon Aug 13 13:16:03 EDT 2007

It's about time to recycle this (that I first posted May 15, 2006):

> 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. 

More information about the Concurrency-interest mailing list