[concurrency-interest] Problem with using an unbounded map of Mutex lock objects

Doug Lea dl at cs.oswego.edu
Tue Jun 6 07:41:39 EDT 2006


Joe Bowbeer wrote:
> 
> However, I can suggest a couple optimizations for your striping implementation.
> 
> 1. Spread the bits in the hash code.
> 

Joe - thanks for the implicit reminder to update this. Last month
we did some analysis of java.util.HashMap and found that the hash
bit scrambling function could be improved, and did so for HashMap.
(I think this version might now be in Mustang builds.)
But hadn't gotten around to ConcurrentHashMap. This is not
quite black magic but close to it. You can analytically determine
general properties, but then use brute-force testing of candidate
functions to find best in a family, Doing this led to:

     static int hash(Object x) {
         // This function ensures that hashCodes that differ only by
         // constant multiples at each bit position have a bounded
         // number of collisions.
         int h = x.hashCode();
         h ^= (h >>> 20) ^ (h >>> 12);
         return h ^ (h >>> 7) ^ (h >>> 4);
     }

> 
> 2. Require LOCK_NUMBER to be a power of two, such as 128.
> 
> In this way, a binary AND (&) can replace division (/).
> 

Absolutely. If (and only if) you use a decent bit spreader like
above, this should give a very noticeable speedup. The mod (%)
operator is very slow on most processors, and especially so in
Java, where there is sign-based adjustment on top of the hardware
instruction.

-Doug


More information about the Concurrency-interest mailing list