[concurrency-interest] ConcurrentHashMapV8

Doug Lea dl at cs.oswego.edu
Tue Aug 30 06:33:41 EDT 2011

On 08/29/11 20:42, Nathan Reynolds wrote:
>  > Further digressing: Despite disadvantages, using locks for statistically very
> short lists turns out to be much more stable and efficient than alternative
> non-blocking strategies I tried
> I realize this is a digression, but it is interesting to me. Are you saying that
> compareAndSet() took more time than locks?

No. The issue is that CHM needs to manage all five of:
insert/remove bin head, insert/remove internal node, and
split the list into upper and lower parts during
resize and replace with forwarding node; all the while maintaining
concurrent readability. There are non-blocking techniques for each
of these in isolation (mainly: deletion via dummy nodes that
I use in ConcurrentSkipLists, and bit-reversed node ordering
for splitting) but together, they introduce a lot of overhead
and contention storms. (For similar reasons, Herlihy & Shavit
recommend lazy-list-locking. which is an upside-down version
of the technique here.) for most list operations rather than
non-blocking techniques. Even though these require more atomic
operation overhead, in the vastly most common case they are
uncontended and thus cheap on recent processors, and more than make
up for the reduction  in other per-node bookkeeping that you'd
need to track dummy nodes etc. On contention, they block threads
out rather than allowing a lot of pointwise CAS misses and retries.

Plus, CHMV8 does still use a single CAS for the most common
update operation, adding a new node into an empty bin.


More information about the Concurrency-interest mailing list