[concurrency-interest] ConcurrentHashMap footprint and contention improvements

Doug Lea dl at cs.oswego.edu
Fri Apr 15 07:04:15 EDT 2011

Thanks everyone for on- and off-list feedback.
A few follow-ups:

On 04/14/11 15:52, Rodrigo Kumpera wrote:
> Did you consider other lock free algorithms such as Shalev-Shavit
> Split-Ordered List based hashtable?

Yes. Some variant of Shalev & Shavit is probably the best bet for
an overhaul. The main challenges are finding ways of dealing with
bit reversal and marker-based list deletion without adding per-node
time and space overhead (that would negate main goal of reducing

On 04/13/11 14:24, Ben Manes wrote:
> Another approach to consider for improving write throughput might be to
> guard the lock with a SynchronousQueue and attempt to transfer the operation
> to the thread currently holding the lock.

There may be a version of this that's worthwhile. I had tried
a simpler form, maintaining only a single "in-process" node, but
didn't see measurable benefit -- an immediate barge (via tryLock)
of a thread already holding new node and with warm cache is already
pretty fast. Along these lines: For heavily contended maps, it
is much faster for all threads to call scanAndLock* rather than
immediate tryLock, but this is enough slower under low per-segment
lock contention not to be worthwhile in general. It may be worth
using an adaptive scheme that estimates contention.


More information about the Concurrency-interest mailing list