[concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Andrew Haley aph at redhat.com
Tue Apr 19 10:00:50 EDT 2016


On 04/19/2016 12:40 PM, Doug Lea wrote:
> On 04/19/2016 05:35 AM, Dr Heinz M. Kabutz wrote:
>>  I don't see anything in the
>> Map.computeIfAbsent() JavaDoc contract that would make my code invalid.  I guess
>> inside ConcurrentHashMap there is a clause of "so the computation should be
>> short and simple, *and must not attempt to update any other mappings of this
>> map*."
> 
> You are right that something should be said in ConcurrentMap and/or Map,
> not just ConcurrentHashMap.
> 
> In any concurrent context, a computeIfAbsent function with side effects
> that that modify map entries (including especially the initially absent one)
> may be subject to livelock, deadlock, and/or exceptions.
> An exception is the nicest of these options. So as Ben mentioned, we
> updated to do so when possible.
> 
> Similar issues can arise even in non-concurrent settings when the
> side-effecting operations on other map entries throw exceptions
> or cause the initially-absent entry not to be absent.

And indeed if you're trying to memoize a (possibly) recursive
function.  You end up having to do something like this:

    static <T, R> Function<T, R> memoize(Function<T, R> f) {
        HashMap<T, R> values = new HashMap<>();
        return t -> {
            R result = values.get(t);
            if (result == null) {
                result = f.apply(t);
                values.put(t, result);
            }
            return result;
        };
    }

computeIfAbsent() would be very nice here, but you can't use it.

Andrew.


More information about the Concurrency-interest mailing list