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

Rowlands, Ben (IT) Ben.Rowlands at morganstanley.com
Mon Aug 13 13:21:20 EDT 2007


Appologies! I did google didn't come up with anything.

Thanks,

Ben Rowlands

> -----Original Message-----
> From: Doug Lea [mailto:dl at cs.oswego.edu] 
> Sent: 13 August 2007 18:16
> To: Rowlands, Ben (IT)
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Adding a createIfAbsent() API?
> 
> 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. 
> 
> 
> 
> 
>
--------------------------------------------------------

NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error.



More information about the Concurrency-interest mailing list