[concurrency-interest] ConcurrentHashMapV8

Zhong Yu zhong.j.yu at gmail.com
Tue Aug 30 16:52:22 EDT 2011


Thanks for clarifying the intended usage for me. Still, given the
heavy restriction on the function, I can't grasp the usefulness of the
method without a realistic use case.

In the following idiom

    if(map.get(k)==null)
        v  = calc(k);
        map.putIfAbsent( k, v );

the 1st line is an optimization, since both calc() and putIfAbsent()
are relatively more expensive than get(), if the key is likely
contained in the map, it's cheaper to try get() first.

The two concerns still exist for computeIfAbsent().

In the lambda expression example,

    computeIfAbsent( k, #{ k -> calc(k) } );

a new object (the function) is created every time, which is quite
expensive relative to get(). So it pays to

    if(map.get(k)==null)
        computeIfAbsent( k, #{ k -> calc(k) } );

If the function depends solely on `k`, we can eliminate the object creation by

    static final Function func = new ...;

    computeIfAbsent( k, func );

with loss of readability provided by lambda expression.

The 2nd concern is that computeIfAbsent() is more expensive* than
get(). So it pays to

    if(map.get(k)==null)
        computeIfAbsent( k, func );

(* based on the latest implementation of computeIfAbsent() - maybe it
can be improved so the idiom above becomes unnecessary )

Finally, comparing the performance of

    v = func.map(k);
    putIfAbsent( k, v );
vs
    computeIfAbsent( k, func );

The two versions perform almost the same, both in uncontended and
contended case, regardless of the complexity of func.map().

Zhong Yu

(I'm sorry if my comments are all negative in nature.)

On Tue, Aug 30, 2011 at 6:13 AM, Doug Lea <dl at cs.oswego.edu> wrote:
> On 08/30/11 00:42, Zhong Yu wrote:
>>
>> The requirement that the computation must not write to entries of
>> different keys seems especially hard to cope with. For example, if a
>> map is used as a cache; when computing value for `k1`, it might be
>> reasonable to disallow recursion on `k1`; however, it will be very odd
>> and inconvenient to disallow `cache.get( k2, #{ load(k2) } )` when
>> computing value for `k1`.
>
> Yes. As I mentioned in other replies, a version suitable for
> arbitrary caches should be based on an internal form of Futures
> that can deal with reservations/place-holders. But this
> (as well as accommodating weak references etc) would
> add a lot of overhead and code bulk to operations for all
> other CHM usages. So stay tuned for a version supporting such things.
>
>> Requiring that the computation is transparent to the caller, must be
>> inexpensive and must not write to the map, will turn away majority of
>> potential users.
>
> That's all for the best. The main problem computeIfAbsent
> addresses is people often getting wrong the alternative
> (and still usually best) idiom of:
> if (map.get(k) == null)
>   map.putIfAbsent(k, new V(k));
> Even though it introduces potential contention (no free lunch),
> with lambda syntax support, computeIfAbsent will be less
> error-prone. As in, something like:
>  map.computeIfAbsent(k, #{k -> new V(k)} };
>
> In other words, the use of locks in CHMV8 is just an internal
> implementation detail that may change at any time (although
> as indicated in other postings, is not too likely to change).
> Even without them, any support for computeIfAbsent introduces
> contention etc, so users should keep the functions short.
>
> -Doug
>
>



More information about the Concurrency-interest mailing list