[concurrency-interest] ConcurrentMap.replace

Eric Zoerner eric.zoerner@gemstone.com
Tue, 25 Nov 2003 09:46:11 -0800


By the way, I apologize for bringing this up so late before 1.5.
I do understand your point about not wanting to add an arbitrary predicate, but 
in my opinion putIfPresent is a basic operation that should be provided, and I 
am not satisfied with the suggested workaround. Not only is there a potential 
performance hit but there is also no guarantee of completion in a high 
contention scenario. To me, the use case for an atomic putIfPresent is clear, 
but perhaps I didn't explain it well. The use case is cache eviction without 
destruction of the key. You evict the value regardless of its current value 
leaving the key in place. The purpose is to evict an value from the cache, 
either because it is stale or because you need to free up space. You do not want 
to get rid of the key entirely because its presence provides the application 
with the information that the key still exists and the value can be retrieved on 
demand (e.g. from a database). There are 5 basic operations on a  named object 
in a cache: get, create, destroy, replace, and invalidate (i.e. evict). All of 
those operations can be implemented cleanly using the current ConcurrentMap API 
except for invalidation which requires an atomic putIfPresent operation. You 
cannot use a simple "put" because that may resurrect a key that may have just 
been destroyed. The proposed replace operation, while useful for other cases, is 
inadequate for this purpose because it requires the retry workaround which is 
inefficent and has unpredictable performance in a highly concurrent environment.

Because this operation is missing and the ConcurrentHashMap does not provide 
sufficient access to its subclasses to add this operation, I would most likely 
not use it.

An alternative idea is to provide access to the update Lock that is used for a 
particular key. This would allow applications to implement higher level atomic 
operations (as well as arbitrary predicates) using a ConcurrentMap. For example, 
the putIfPresent operation could then be implemented like so:

/** @return the old value, or null if not present */
Object putIfPresent(ConcurrentMap m, K key, V value) {
    // implementation note: getUpdateLock actually returns the Segment for key
    // which implements the Lock interface
   Lock lock = m.getUpdateLock(key);
   lock.lock();
   try {
     if (!m.containsKey(key))
       return null;
     return m.put(key, value);
   }
   finally {
     lock.unlock();
   }
}



Doug Lea wrote:
>>I can see how this replace method is the same as putIfPresent(K key, V
>>value, V expectedValue), but how would this method work for the case
>>where I don't care what the current value is, but I want to replace it
>>only if containsKey(key) is true? (e.g. I want to atomically replace
>>it regardless of its current value with my NullObject without the side
>>effect of adding the key it if it's been removed)?
> 
> 
> 
> The bad news is that I still have a hard time thinking of a compelling
> use case where you'd want putIfPresent() but not replace(). And I
> worry about the slippery-slope problem here. For example, maybe you
> would like even better:
>   boolean putIf(K key, Predicate<V> predicate, C value)
> supplying a callback function that the map appliess to get(key); that
> could for example here return true if its argumentis non-null.  But as
> a matter of policy, we don't support callbacks in these kinds of
> classes because doing callbacks inside our internal sync schemes would
> make it impossible to provide guarantees about it working.
> 
> The good news is that the new replace() method is a "universal"
> construction that allows you do do any of these things yourself,
> although not quite as efficiently as if each were built in.  For
> example, you can write yourself:
> 
> boolean putIfPresent(ConcurrentMap m, K key, V value) {
>   for (;;) {
>      V old = m.get(key);
>      if (old == null) return false;  // *
>      if (m.replace(key, old, value)) return true;
>   }
> }
> 
> This is basically equivalent to a classic compareAndSet (CAS) loop. 
> As with CAS, it will loop only if contended, i.e., hardly ever in
> most applications.
> 
> You could replace line (*) with any predicate, thus getting
> the effect of the above nonexistent predicate version.
> 
> Can you live with this?
> 
> -Doug