Java 1.5 introduced some new cool concurrency stuff which is located in java.util.concurrent package. There are lots of good things there including new ConcurrentHashMap class which I'm going to talk about. That class is targeted to be used in concurrent environment and provides significant performance benefits over synchronized version of HashMap. Javadoc doesn't really provide lots of details on how that class works and why can be better than synchronized version of HashMap. I think that understanding of these details is crucial for using that class in a right way, so I've made some research to undercover implementation details and mechanisms used to implement that class.
Map Regions
Firstly I will repeat what is already said in JavaDoc - that map implementation consists of regions. Each region is hash table - an array where each element is associated with some range of hash codes and contains linked list of entries. It means that structurally region is very similar to normal HashMap. All write operations have to acquire write lock on the one whole region.
All read operations on the region are performed without locking, apart from one small exception. That exception happens on attempt to read value of entry and that value is "null". In that case code suspects that compiler and could possibly assign entry to array element before calling entry's constructor (good example and explanation of that problem can be found here). When that happens code tries to acquire write lock and perform reading inside that lock. Such strategy guarantees that initialization of the object is completed before the reference is assigned to the array element. As it is stated in comments in ConcurrentHashMap's source code, chance that comliler will re-order initialization and assignment in that paticular case is extremely low, so chance of "blocking read" is negligible.
Another interesting thing about region is that it has volatile counter which counts number of modifications of that region. That value is used in many methods of ConcurrentHashMap to identify that region’s state is not changed during execution of current method. Basically it is used as a means of solving ABA problem. It doesn't seem right to me that such strategy is applied even on read methods, the most of them are much slower than they can be without that check. There is also some locking (e.g. in size() operation) of individual segments which looks unnecessary as far as result is not going to be accurate anyway. But, on the other hand, that class was created by Doug Lea who is very respectable for his concurrency research, so I suspect I'm missing something...
Iteration through ConcurrentHashMap
Some other stuff, which may raise questions, is relationship between collection and enumeration objects returned by “keySet()”, “values()”, “entrySet()”, “keys()” and “elements()” and ConcurrentHashMap instance which have created them. Implementation of all these objects is based on internal class HashIterator and the noticeable thing here is that instance of that class has some information about the state of ConcurrentHashmap at the moment of it’s (HashIterator’s instance) creation. As an example, there is direct reference to the segment’s data array and on the moment when the HashIterator instance is actually used, given segment could have already decided to create a new array, because the old one appeared to be too small. It means that data returned by these collections and enumerations may not reflect changes in the instance of ConcurrentHashmap which happened after given collection or enumeration was created.
Performance considerations for these objects are exactly the same as for ConcurrentHashMap’s methods - read methods are non-blocking and for update methods lock is acquired on segment level. Interesting, but not really practically useful fact, is that HashIterator isn’t that smart as ConcurrentHashMap itself and doesn’t lock when entry’s value is null. So in theory, it is possible that iterator created by “elements()” method will return null value from “next()” or “nextElement()”.
Building the map
To build a map properly you have to understand what constructor’s arguments mean. Here is a brief explanation in the light of things which are written above:
Migration to ConcurrentHashMap
Other possible question which can be raised is the migration from synchronized version of HashMap to CuncurrentHashMap. There are several things which has to be evaluated during the migration process:
Firstly I will repeat what is already said in JavaDoc - that map implementation consists of regions. Each region is hash table - an array where each element is associated with some range of hash codes and contains linked list of entries. It means that structurally region is very similar to normal HashMap. All write operations have to acquire write lock on the one whole region.
All read operations on the region are performed without locking, apart from one small exception. That exception happens on attempt to read value of entry and that value is "null". In that case code suspects that compiler and could possibly assign entry to array element before calling entry's constructor (good example and explanation of that problem can be found here). When that happens code tries to acquire write lock and perform reading inside that lock. Such strategy guarantees that initialization of the object is completed before the reference is assigned to the array element. As it is stated in comments in ConcurrentHashMap's source code, chance that comliler will re-order initialization and assignment in that paticular case is extremely low, so chance of "blocking read" is negligible.
Another interesting thing about region is that it has volatile counter which counts number of modifications of that region. That value is used in many methods of ConcurrentHashMap to identify that region’s state is not changed during execution of current method. Basically it is used as a means of solving ABA problem. It doesn't seem right to me that such strategy is applied even on read methods, the most of them are much slower than they can be without that check. There is also some locking (e.g. in size() operation) of individual segments which looks unnecessary as far as result is not going to be accurate anyway. But, on the other hand, that class was created by Doug Lea who is very respectable for his concurrency research, so I suspect I'm missing something...
Iteration through ConcurrentHashMap
Some other stuff, which may raise questions, is relationship between collection and enumeration objects returned by “keySet()”, “values()”, “entrySet()”, “keys()” and “elements()” and ConcurrentHashMap instance which have created them. Implementation of all these objects is based on internal class HashIterator and the noticeable thing here is that instance of that class has some information about the state of ConcurrentHashmap at the moment of it’s (HashIterator’s instance) creation. As an example, there is direct reference to the segment’s data array and on the moment when the HashIterator instance is actually used, given segment could have already decided to create a new array, because the old one appeared to be too small. It means that data returned by these collections and enumerations may not reflect changes in the instance of ConcurrentHashmap which happened after given collection or enumeration was created.
Performance considerations for these objects are exactly the same as for ConcurrentHashMap’s methods - read methods are non-blocking and for update methods lock is acquired on segment level. Interesting, but not really practically useful fact, is that HashIterator isn’t that smart as ConcurrentHashMap itself and doesn’t lock when entry’s value is null. So in theory, it is possible that iterator created by “elements()” method will return null value from “next()” or “nextElement()”.
Building the map
To build a map properly you have to understand what constructor’s arguments mean. Here is a brief explanation in the light of things which are written above:
- Default initial capacity. That parameter is used to calculate initial capacity of segments. The capacity of each segment is nearest power of two bigger than provided initial capacity divided by number of regions (see Default concurrency level). E.g. initial capacity is 1000 and concurrency level is 3, then number of regions is 4 and capacity of each region is 256 (which is nearest power of two bigger than 1000/4). Default value of that argument is 16.
- Default load factor. Is used to identify the moment when the region has to be resized (see section about memory consumption below). No magic, used as is. Default value of that argument is 0.75.
- Default concurrency level. Defines number of regions which will be created. Exact number of regions is nearest power of two bigger than provided concurrency level. Concurrency level is always less than 2^16. E.g. if concurrency level is 18, number of regions will be 32. Default value of that argument is 16. Keep in mind, that more regions (better concurrency), means higher memory consumption.
And, probably, the last bit - memory consumption. In these terms ConcurrentHashMap is approximately the same as HashMap, but multiplied by number of regions. Region grows at the moment when number of elements appeared to be equal to loadFactor*currentSizeOfRegion value. New region size is always twice as big as previous one, maximum size of region is 2^30.
Other possible question which can be raised is the migration from synchronized version of HashMap to CuncurrentHashMap. There are several things which has to be evaluated during the migration process:
- Some methods can use synchronized map object for synchronization purposes. If someone accrue the lock on the object, all it’s methods are locked as well. That’s be biggest fun. There is no simple way to archive such behaviour with CuncurrentHashMap.
- CuncurrentHashMap’s size method is slow. In the worst case it spins couple of time and then get the lock on all regions. This is much-much-much slower than HashMap implementation, which returns back just the value of the “size” field.
- Iterator of CuncurrentHashMap does not throw ConcurrentModificationException. Do not see how this can cause problem, but just keep it is mind.
- Containing the same amount of elements ConcurrentHashMap object requires more memory than HashMap object (see “Building the map” section).
All in all, ConcurrentHashMap is brilliant container. In multi-threaded environments it will have much bigger throughput than synchronized version of HashMap on read and write operations. Such improvement is result of absence of locking on read and using of region-based locking on write operations. There is sill small chance that segment will be locked for a very short time on read, but chance is so small that it can be just ignored. Write operations are locking just one region, other regions can be updated at the same time.
The price for all these improvements are increase in memory usage and some degradation of performance on read operations. More memory is used because each region wastes approximately the same amount of memory as one HashMap. Performance drop on accessing elements is because of ABA checks. Write operations do not seem to introduce any performance degradation, apart from use of locking.
Posts
