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.

Friday, December 10, 2010

ArrayList contains() and LinkedList get() gets slower

Its very important to realize when to use what kind of data structure. It is important to understand how similar data structures differ while performing same operations. For e.g. a List interface is implemented by LinkedList as well as the ArrayList, but they widely differ in terms of the implementation. Due to the different practical scenarios, it is often required to use different implementations for the same interface. One should be very careful in choosing the right implementaion for his use.


While debugging a problem in a real system, I realized that the system was much slower in a particular usecase.


The characteristic of the application was as below :


1. The application created say 1 million objects, sequentially one after another per day.

2. A linked list was used as a window to access (say top n) this huge number of objects.

3. The linked list window was of fix size and represented the latest produced objects.


The use case was to access this list and compute some real time numbers for applications use. This is how the list was used.

int sum = 0;
for(int i=0; i
  Object obj = list.get(i);
  sum = sum + obj.value();
}
// sum was used further by the application.


Initially, this may look like a simple case, which would not have any problem. But this is a big performance problem with LinkedList. Well this may also seem to be a very trivial problem to many, but its a very natural programming error which could happen.

This problem may not be visible if the list is short, or if the list is an ArrayList, but here in this case, it was a LinkedList and problem accentuated only with larger set of data. Below is the code Listing from java.util.LinkedList.

Listing 1.
public E get(int index) {
        return entry(index).element;
    }

private Entry entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

As you can see, in order to get an element at index i, the LinkedList has to iterate over all its elements till it reaches the element at location i.

With the ArrayList, the implementation is different. ArrayList maintains an object array to store its content. Whenever an object is requested at the given index, it just has to get it from this object array. This operation is fast and constant with number of objects in terms of time.

The problem with the LinkedList increases with the number of objects and depends on the location of the object in the list. Below is a test program which I wrote just to get some approximate figures of this slowness.

Listing 2.
int marker = 1000000;
List list = new LinkedList();
Date startDate = new Date();
for (int i = 0; i < 6000000; ++i) {
    list.add(i);
    if (i % marker == 0) {
    Date endDate = new Date();
    System.out.println("put " + (i / marker) + "  " + (endDate.getTime() - startDate.getTime()));
    startDate = endDate;
    }
}
startDate = new Date();
marker = marker / 100;
for (int i = 0; i < 6000000; ++i) {
    list.get(i);
    if (i % marker == 0) {
    Date endDate = new Date();
    System.out.println("get " + (i / marker) + "  " + (endDate.getTime() - startDate.getTime()));
    startDate = endDate;
    }
}

I ran the program and plotted the number of get calls against the time taken as shown below :



Here you can see that initially the curve is steep and then its almost at a slope of 1, which is kinda expected. The idea to take away is that the time taken to search an element in the linked list, in the worse case, linearly increases with the number of elements presnet in the list.

When the list implementation is replaced with ArrayList, then the get calls are not even noticable and time difference you get in the loops is 0 milli seconds.  Against the huge numbers we get in case of the LinkedList.

However the same problem occurs with ArrayList when its method contains() is used. The method contains() have the similar implementation as LinkedList's get() method. Hence its very important and useful to know the complete detailed implementation of the datastructure, before using it.