[concurrency-interest] A concurrent, linked HashMap impl

Doug Lea dl at cs.oswego.edu
Tue May 26 19:45:35 EDT 2009


Manik Surtani wrote:
> I've implemented a concurrent, linked map-like structure [1] [2] 
>

Sorry for the delay! (I've mostly been playing volunteer sysadmin
for a bunch of reconfigurations here.)

We've been considering things like this for the several-times-delayed
but still upcoming CustomConcurrentHashMap (CCHM) allowing weak/soft
entries, identity comparisons and (too :-) much more.

I gather that the main motivation for your approach is to support
LRU replacement. Considering that many concurrent maps are used
as caches, this seems to be a common desire. But we've been resisting
supporting pure LRU because list-based approaches
force a sequential bottlenecks at the ends of the lists. So even
a lock-free approach to maintaining an access-ordered list may
encounter enough contention to negate the advantages of cheap
get()'s and usually-uncontended modifications. Additionally,
if you trigger LRU-based removal when hitting a size threshold,
then you end up calling size() a lot, which is also not cheap.
All in all, it is not clear when or by how much a concurrent hash
map approach will have better performance for strict LRU caching
over a simple synchronized LinkedHashMap.

There are a few ways to get LRU-like replacement that
don't impose bottlenecks. Hardware L1 etc caches, facing
the same issues, tend to use various "pseudo-LRU" (google it)
techniques that don't have very good software analogs.
Among the leading candidates is a random sampling approach
(similar to one in the thesis by Konstantinos Psounisy
http://www-rcf.usc.edu/~kpsounis/thesis.html) triggered
by local per-segment threshold overflows. Hopefully
I'll get something using it ready for preliminary release soon.

While I'm at it... There are several alternative concurrent
hash maps in various stages of development, including...

* Moran Tzafrir's Hopscotch hashing:
http://groups.google.com/group/hopscotch-hashing

* Cliff Click's state-based table:
http://sourceforge.net/projects/high-scale-lib/

* Amino project cbbs dictionary based on Shalev & Shavit
http://amino-cbbs.wiki.sourceforge.net/

The diversity reflects the fact that there are a lot of
tradeoffs in hash table design. Some of these are probably
better than j.u.c.ConcurrentHashMap in some contexts, but
it is still not clear if any of them are or can become
better in enough contexts to replace the current algorithms.

-Doug

> 
> [1] 
> http://fisheye.jboss.org/browse/Infinispan/trunk/core/src/main/java/org/infinispan/container/FIFODataContainer.java?r=236 
> 
> [2] 
> http://fisheye.jboss.org/browse/Infinispan/trunk/core/src/main/java/org/infinispan/container/LRUDataContainer.java?r=219 
> 
> [3] 
> http://www.md.chalmers.se/~tsigas/papers/Lock-Free-Deques-Doubly-Lists-JPDC.pdf 


More information about the Concurrency-interest mailing list