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.

32 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)?

Alwin Co Daan said...

Amazing & Great informative blog,it gives very useful practical information to developer like me. Besides that Wisen has established as Best Java Online Training India . or learn thru Online Training mode Java Online Training From India . Nowadays Hibernate ORM has tons of job opportunities on various vertical industry.

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

tamilsasi said...

After reading this web site I am very satisfied simply because this site is providing comprehensive knowledge for you to audience.
Thank you to the perform as well as discuss anything incredibly important in my opinion. We loose time waiting for your next article writing in addition to I beg one to get back to pay a visit to our website in



selenium training in Bangalore
selenium training in Marathahalli
selenium training in Btm layout
selenium training in Jaya nagar
selenium training in Electronic city
selenium training in Kalyan nagar



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

anusha said...


Python Training in ChennaiLearn Python Training in Chennai from industry experts and become a python certified professional.BITA is the Best Python Training Institute in Chennai which is located in ramapuram. Call for more details.

Tech Guy said...

For Data Science training in bangalore, Visit:
Data Science training in bangalore

Tech Guy said...

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

Tech News said...

Visit here -> BIG DATA AND HADOOP TRAINING IN BANGALORE

Tech News said...

Visit here -> Devops 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

Dennis said...

Thanks for your blog!!.
JAVA Development Services
HR Pay Roll Software
SAP Software Services
Hotel Billing Software
Web Design Company
Hospital Management Software

Rajesh Anbu said...

Really nice post. Thank you for sharing amazing information.
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

Venkatesh CS said...

Thanks for sharing valuable information.
hadoop online training in chennai
hadoop online training
best hadoop certification online
hadoop online certification
hadoop training online
hadoop online classes
hadoop online course Chennai
hadoop online training Chennai
hadoop online learning
hadoop online courses
best hadoop online training

nisharoshan said...

Every day I always visit sites to obtain the best information for materials research I was doing.......

Web Designing Training Course in Chennai | Certification | Online Training Course | Web Designing Training Course in Bangalore | Certification | Online Training Course | Web Designing Training Course in Hyderabad | Certification | Online Training Course | Web Designing Training Course in Coimbatore | Certification | Online Training Course | Web Designing Training Course in Online | Certification | Online Training Course

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

Sarthak Yadav said...

Good Post! , it was so good to read and useful to improve my knowledge as an updated one, keep blogging.After seeing your article I want to say that also a well-written article with some very good information which is very useful for the readers....thanks for sharing it and do share more posts likethis. https://www.3ritechnologies.com/course/salesforce-training-in-pune/

Mohd Sharique said...

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

Python Training In Pune
python training institute in pune

Paras Arora said...

Fantastic blog! Thanks for sharing a very interesting post, I appreciate to blogger for an amazing post.
Data Science
Selenium
ETL Testing
AWS
Python Online Classes

Selenium Training in Pune said...

That's really impressive and helpful information you have given, very valuable content.
We are also into education and you also can take advantage really awesome job oriented courses

Myclasstraining 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