[concurrency-interest] Looking for a data struture

Peter Levart peter.levart at gmail.com
Fri Dec 26 06:18:11 EST 2014


Hi Luke,

On 12/22/2014 05:10 PM, Luke Sandberg wrote:
> Thanks for all the responses!
>
> RE: CHM. For the thread-renaming usecase we used CHM for a while but 
> it consistently ended up as one of the highest contention points (as 
> measured by lock wait times) in some of our applications.  Also there 
> is a fairly high fixed overhead.

I would expect CHM to have the lowest contention for concurrent 
insertion and removal of any solution described here, since it uses 
multiple locks (one per bucket in CHM v8) and uncontended locking is 
quite fast. Unless computing identity hashCode for a Thread is a 
contention point? Were you using a pre-JDK8 CHM which uses fixed number 
of "segments" internally with one lock per segment?

The space overhead is not that much greater if your key(s) already use 
identity equals/hashCode so you don't have to wrap them with another 
object (Thread is such class). In CLQ, each element is "wrapped" into a 
node which looks like:

     private static class Node<E> {
         volatile E item;
         volatile Node<E> next;
     }

which is 20 bytes on 32 bit JVM and 32 bytes on 64 bit JVM

In CHMv8, each key/value pair (you can use a singleton object for 
values) is wrapped into a node which looks like:

     static class Node<K,V> implements Map.Entry<K,V> {
         final int hash;
         final K key;
         volatile V val;
         volatile Node<K,V> next;
     }

which is 28 bytes on 32 bit JVM and 48 bytes on 64 bit JVM

Regards, Peter

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141226/40060d35/attachment-0001.html>


More information about the Concurrency-interest mailing list