Java ConcurrentHashMap implementation

Question

I was just looking at the source code of Java's ConcurrentHashMap and found this line of code:

/*  * The maximum number of times to tryLock in a prescan before possibly blocking on acquire in     * preparation for a locked segment operation. On multiprocessors, using a bounded number of    * retries maintains cache acquired while locating nodes.  */ static final int MAX_SCAN_RETRIES =               Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1 

The MAX_SCAN_RETRIES is used in looking up entries while acquiring lock. My question is how is the number 64 determined for a multi-processor machine? Anybody know the theory behind the number 64?

Answer 1

When dealing with lock retries across multiple CPUs there is a balance that you strike between attempting to get the lock quickly (spinning) and allowing the CPU to switch to another thread to avoid wasting CPU time spinning on the lock that isn't going to be released soon. The actual number of spins allowed for a CPU to attempt to obtain a lock is strongly affected by both the actual speed of the overall system as well as by the amount of code that typically executes within the critical section.

This issue has deep roots in the Stopping Problem and many other issues related to OS design on SMP systems with respect to optimizing concurrency. This kind of design choice is typically resolved via a trial and error approach across many applications; however the choice of 64 looks to me like an arbitrary call on the part of the implementer (the number is a power of two).

Unfortunately this particular code is both buggy and limiting. Buggy in that the documentation for availableProcessors states "This value may change during a particular invocation of the virtual machine," hence potentially causing the lock to spin too many times (should the count move from > 1 to = 1) or too few (in the visa-versa case). It is limiting in that a developer that really needs to tune concurrency in their application has no ability to do so as MAX_SCAN_RETRIES is final (though some tricks may be played with reflection).