Sunday, December 12, 2010

Why ConcurrentHashMap does not support null values

While doing some performance bench marking, I figured out that I could replace lot of my Hashmaps into ConcurrentHashMap. Now ConcurrentHashMap does not support null values but HashMaps do, so I had to do this extra checks for handling null values, but that was pretty easy in my application.

I was wondering why ConcurrentHashmaps did not support null. A quick look at the code showed, the put method in ConcurrentHashMap throws an explicit NullPointerException after a null check on value.

Listing 1
1. public V put(K key, V value) {
2.   if (value == null)
3.     throw new NullPointerException();
4.   int hash = hash(key.hashCode());
5.   return segmentFor(hash).put(key, hash, value, false);
6. }


Well probably that meant, the passed value could be accessed inside the ConcurrentHashMap without expecting it to be null at any point, during the code flow through the ConcurrentHashMap. I checked the usage of passed in value in ConcurrentHashMap. There was no evidence which would show a possibility of NullPointerException occuring, and hence I was tempted to intrigue more.

So I tweeted on twitter 'Why can't Concurrent Hash Maps take null values ?', hoping that someone will reply back with an answer. I got none till date.

A quick google search did not give me any reliable answers and hence I decided to check it out myself. I created a new class ConcurrentHashMap in my test project (using eclipse), under the package, java.util.concurrent. I commented out the null check in put (removed line 2 and 3 in Listing 1). I wrote a small test program (Multi-Threaded) to do some reads and writes, and ran the program. (I ran the program pre pending my custom java.util.concurrent.ConcurrentHashMap class into the bootstrap class loader, using vm argument -Xbootclasspath/p:). Surprisingly I did not get any errors and everything was fine.

I decided to check the performance at this point.

I wrote a sample program with two threads in an infinite loop. One thread was reading (Listing 2) and the other one was writing (Listing 3) onto the same ConcurrentHashMap.

Listing 2. Reader
1.  int count = 0;
2.  Date startDate = new Date();
3.  while (true) {
4.    ++count;
5.    chm.get("test");
6.    if (count % 1000000 == 0) {
7.      Date endDate = new Date();
8.      System.out.println("Get : " + (endDate.getTime() - startDate.getTime()));
9.      startDate = endDate;
10.   }
11. }

Listing 3. Writer
1.  count = 0;
2.  startDate = new Date();
3.  while (true) {
4.    ++count;
5.    chm.put("test", "null");
6.    if (count % 1000000 == 0) {
7.      Date endDate = new Date();
8.      System.out.println("Put : " + (endDate.getTime() - startDate.getTime()));
9.      startDate = endDate;
10.   }
11. }

This test program was run under two scenarios :

case 1 : With the modified ConcurrentHashMap (with null check on value removed) and Line 5 in Listing 3 being chm.put("test", "null");

case 2 : With the unmodified ConcurrentHashMap (in rt.jar) and Line 5 in Listing 3 changed to chm.put("test", "test");

The numbers are the time taken in millis for 1 million iteratons of each loop shown in Listing 2 and 3.

Case 2.              Case 1. 

Get : 47      Put : 313
Get : 62      Get : 344
Put : 140     Put : 297
Get : 47      Get : 328
Get : 47      Put : 312
Get : 62      Get : 328
Put : 125     Put : 281
Get : 47      Get : 313
Get : 47      Put : 313
Put : 125     Get : 343
Get : 47      Put : 312
Get : 47      Get : 344
Get : 47      Put : 313
Put : 125     Get : 219
Get : 47      Get : 125
Get : 46      Put : 468
Get : 47      Get : 265
Put : 125     Put : 282
Get : 47      Get : 344
Get : 47      Put : 281
Put : 125     Get : 344
Get : 47      Put : 266
Get : 47      Get : 359
Get : 47      Put : 281
Put : 125     Get : 297
Get : 47      Put : 297
Get : 46      Get : 328
Get : 47      Put : 297
Put : 125     Put : 281
Get : 32      Get : 328
Get : 46      Put : 281
Put : 110     Get : 329
Get : 47      Put : 297
Get : 47      Get : 312
Get : 47      Put : 281
Put : 140     Get : 328
Get : 47      Put : 297
Get : 47      Get : 328
Get : 47      Put : 313

Results were interesting and it clearly showed that in worse case, gets would be 5 to 10 times slower with a ConcurrentHashMap supporting Null than the original one. The puts were 3 to 5 times slower. Hence its a no go for ConcurrentHashMap to support null values in its current state.

Reasoning :

The method get in Segment implementation of a ConcurrentHashMap takes a lock on the segment itself, if the value of a HashEntry turns out to be null. This is illustrated in Listing 4.

Listing 4.
1.  V get(Object key, int hash) {
2.    if (count != 0) { // read-volatile
3.      HashEntry e = getFirst(hash);
4.      while (e != null) {
5.        if (e.hash == hash && key.equals(e.key)) {
6.          V v = e.value;
7.            if (v != null)
8.              return v;
9.          return readValueUnderLock(e); // recheck
10.       }
11.       e = e.next;
12.     }
13.   }
14.   return null;
15. }
Now if ConcurrentHashMap does not allows null values then how can the HashEntry have a null value (value is marked volatile in HashEntry). Consider a scenario while a thread may be trying to put a new value on the HashEntry (line 22 in Listing 5) in the put method of the ConcurrentHashMap. The HashEntry object is created but not yet initialized, so that value attribute in HashEntry does not reflects its actual value, but instead reflects null. At this point a reader gets the HashEntry and reads a null for attribute value in HashEntry, thus having a need to recheck with a lock (line 9. Listing 4.).


Listing 5.
1.  V put(K key, int hash, V value, boolean onlyIfAbsent) {
2.    lock();
3.    try {
4.      int c = count;
5.      if (c++ > threshold) // ensure capacity
6.        rehash();
7.      HashEntry[] tab = table;
8.      int index = hash & (tab.length - 1);
9.      HashEntry first = tab[index];
10.     HashEntry e = first;
11.     while (e != null && (e.hash != hash || !key.equals(e.key)))
12.       e = e.next;
13.     V oldValue;
14.     if (e != null) {
15.       oldValue = e.value;
16.       if (!onlyIfAbsent)
17.         e.value = value;
18.       } else {
19.         oldValue = null;
20.         ++modCount;
21.         tab[index] = new HashEntry(key, hash, first, value);
22.         count = c; // write-volatile
23.       }
24.     return oldValue;
25.   } finally {
26.   unlock();
27. }
28.  }

This extra check in Line 9 of Listing 4 is very costly (as we already see it in the test results above) and is avoided if a not null value of HashEntry is encountered. In case the null values are allowed this would require to have this lock acquired each time a null value is accessed, hence making the ConcurrentHashMap slower.

23 comments:

Anonymous said...

Excellent post dude , well compiled and well written

ConcurrentHashMap is indeed best choice in case of multithreaded environment if numbers of reader is much greater than number of writer to avoid contention and to increase throughput and performance but deciding between SynchrnozedHashMap and ConcurrentHashMap is still requires understanding of usecases and actual environment.

Thanks
Javin
FIX Protocol tutorial

anshuiitk said...

Thanks Javin,

Its really about how datastrutures work internally and not about just knowing the APIs.

That said, for e.g. its just not about replacing Hashmaps with CHMs if multithreaded access is needed. You could easily land into race conditions. This is well explained by Derek here

Anonymous said...

Thanks anshuitk for that link.

Why are you not writing any more buddy I landed here to see some more good post from you :)

Thanks
Javin
Why String is immutable in Java

atc said...

Is this a mistake?

chm.put("test", "null");

Why are you doing "null"?

That's putting a String as the value, not a null reference - right? Therefore, aren't your numbers misguided because you're actually putting a value (thus the null check passing) into the map ("null" != null)?

pooja said...

A very nice guide. I will definitely follow these tips. Thank you for sharing such detailed article. I am learning a lot from you.
Devops Training courses
python Training in chennai
Devops Training in Bangalore

gowsalya said...

I'm here representing the visitors and readers of your own website say many thanks for many remarkable
Python Online training
python Course institute in Chennai
Python Course institute in Bangalore

Tech Guy said...

For Blockchain training in bangalore, Visit:
Blockchain training in bangalore

vijay said...

thanks for this informative article it is very useful

aws Training in Bangalore
python Training in Bangalore
hadoop Training in Bangalore
angular js Training in Bangalore
bigdata analytics Training in Bangalore
python Training in Bangalore
aws Training in Bangalore

radhika said...

A very nice guide. I will definitely follow these tips. Thank you for sharing such detailed article. I am learning a lot from you.
AWS training in Chennai

AWS Online Training in Chennai

AWS training in Bangalore

AWS training in Hyderabad

AWS training in Coimbatore

AWS training

Jayalakshmi said...

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well.
java training in chennai

java training in tambaram

aws training in chennai

aws training in tambaram

python training in chennai

python training in tambaram

selenium training in chennai

selenium training in tambaram

deiva said...

Its really about how datastrutures work internally and not about just knowing the APIs.
java training in chennai

java training in omr

aws training in chennai

aws training in omr

python training in chennai

python training in omr

selenium training in chennai

selenium training in omr

praveen said...

Hi very informative blog and i learnt new things form this post,
Thank you so much and keep more update,

hadoop training in chennai

hadoop training in porur

salesforce training in chennai

salesforce training in porur

c and c plus plus course in chennai

shiny said...

Effective and interesting post for reading, i really love it and waiting for updates...

web designing training in chennai

web designing training in annanagar

digital marketing training in chennai

digital marketing training in annanagar

rpa training in chennai

rpa training in annanagar

tally training in chennai

tally training in annanagar

jeni said...

Really impressive post. I read it whole and going to share it with my social circules. I enjoyed your article
sap training in chennai

sap training in velachery

azure training in chennai

azure training in velachery

cyber security course in chennai

cyber security course in velachery

ethical hacking course in chennai

ethical hacking course in velachery

KITS Technologies said...

A big thank you for your blog article.Much thanks again. Awesome.
Oracle Cloud Administration training
Oracle Data Integrator online training
Oracle Data Integrator training
Oracle DBA online training
Oracle DBA training
Oracle Enterprise Manager online training
Oracle Enterprise Manager training
Oracle Exadata online training
Oracle Exadata training
Oracle fusion order management online training

Anonymous said...

hadoop training in bangalore | hadoop online training
iot training in bangalore | iot online training
devops training in banaglore | devops online training

vivekvedha said...

very informative blog and i learnt new things form this post,
Thank you so much and keep more update,
acte chennai

acte complaints

acte reviews

acte trainer complaints

acte trainer reviews

acte velachery reviews complaints

acte tambaram reviews complaints

acte anna nagar reviews complaints

acte porur reviews complaints

acte omr reviews complaints

Mohd Sharique said...

Great Blog to read,Its gives more useful information.Thank lot.

Python Training In Pune
python training institute in pune

Realtime Experts said...

Grateful to you, for sharing those superb expressive confirmations. I'll try to do around a spurring power in reacting; there's a striking course of action that you've crushed in articulating the important goals, as you charmingly put it. Keep Sharing
Grateful to you, for sharing those superb expressive confirmations. I'll try to do around a spurring power in reacting; there's a striking course of action that you've crushed in articulating the important goals, as you charmingly put it. Keep Sharing

gaeloryandow said...

Titanium watches: watches - TITIAN ARTISTS
TITIAN ARTISTS are samsung watch 3 titanium a unique class of titanium cartilage earrings watches, designed to fit the preferences titanium wedding band of many leisure titanium dive knife and leisure micro titanium trim people.

Pranisha said...


Are you looking for the best Azure training in Chennai? Here is the best suggestion for you, Infycle Technologies the best Software training institute in Chennai to study Azure platform with the top demanding courses such as Graphic Design and Animation, Cyber Security, Blockchain, Data Science, Oracle, AWS DevOps, Python, Big data, Python, Selenium Testing, Medical Coding, etc., with best offers. To know more about the offers, approach us on +91-7504633633, +91-7502633633

tismef said...

x566r9lermq369 women sex toys,Clitoral Vibrators,real dolls,masturbators,wholesale sex toys,cheap sex toys,dildo,glass dildo,cheap sex toys l937t3zlcxd342

MeenaKK said...

Thank you for sharing such valuable information. Your blog always provides a fresh perspective, and I find it both informative and enjoyable to read. Keep up the great work!" AWS Training in Pune