Monday, March 7, 2011

JVM Performance - Part III - Concurrent Maps

Concurent Maps

The main difference between Hashtable and HashMap is that Hashtable is synchronized. For this reason Hashtable is still used in a lot of concurrent code because it is, in theory, thread safe.  This theory is however normally just a theory, because if you don't write concurrent code correctly, it will still not be thread safe no matter how many synchronized methods you have.

For example you could call get() on the Hashtable, then if it is not there call put(), both operations are synchronized and thread-safe, but in between your get() and put() another thread could have done the same thing and put something there already, in which case your code may be incorrect and have thrown away some other thread's data.  With a Hashtable the solution to this is to synchronize the whole operation on the map.

Object value = map.get(key);
if (value == null) {
    synchronized (map) {
        value = map.get(key);
        if (value == null) {
            value = buildValue(key);
            map.put(key, value);
        }
    }
}

JDK 1.5 added the ConcurrentMap implementation that is thread safe, and designed and optimized for concurrent access. It basically has pages inside the map, to avoid locks on concurrent access to different pages. It also provides useful API such as putIfAbsent() to allow something to be put in the map unless it is already there, in a thread safe manner.  Using putIfAbsent() is more efficient than using a synchronized get() and put() in both concurrency and performance.

Object value = map.get(key);
if (value == null) {
    Object newValue = buildValue(key);
    value = map.putIfAbsent(key, value);
    if (value == null) {
        value = newValue;
    }
}

So, how does the performance and concurrency of HashMap, Hashtable and ConcurrentMap stack up?  This test compare the performance for gets and puts in various Map implementations using 1 to 32 threads. It does 100 gets or puts in a Map of size 100.  Two machines were tested.  The first machines is my Windows XP desktop, that has two cores. The second machine is an 8 core Linux server.  All tests were run 5 times and averaged, Oracle Sun JDK 1.6.23 was used.

Threads, is the number of thread running the test.  The average is the total number of operations performed in the time period by all threads in total.  The %STD is the percentage standard deviation in the results.  The %DIF is the percentage difference between the run and the single threaded run (for the same Map type).

Concurrent Map Performance Comparison (desktop, 2cpu)

MapOpperationThreadsAverage%STD%DIF (with 1 thread)
HashMapget135513060.06%0%
HashMapget241211020.03%16%
HashMapget441325060.15%16%
HashMapget842274850.68%19%
HashMapget1644025321.36%23%
HashMapget3244265141.61%24%
Hashtableget111329560.06%0%
Hashtableget23642360.08%-211%
Hashtableget42746030.14%-312%
Hashtableget82771881.08%-308%
Hashtableget162778810.78%-307%
Hashtableget322967792.51%-281%
ConcurrentHashMapget127710980.04%0%
ConcurrentHashMapget234664512.30%25%
ConcurrentHashMapget434584920.33%24%
ConcurrentHashMapget835102820.31%26%
ConcurrentHashMapget1636131822.36%30%
ConcurrentHashMapget3235994892.23%29%
HashMapput138979250.07%0%
HashMapput226147840.01%-49%
HashMapput424730110.21%-57%
HashMapput824827430.30%-57%
HashMapput1625065190.53%-55%
HashMapput3225797150.30%-51%
Hashtableput110420760.33%0%
Hashtableput24741993.06%-119%
Hashtableput41795506.71%-480%
Hashtableput81831021.63%-469%
Hashtableput163930850.68%-165%
Hashtableput323982771.10%-161%
ConcurrentHashMapput113362920.21%0%
ConcurrentHashMapput25578803.71%-139%
ConcurrentHashMapput43907361.64%-241%
ConcurrentHashMapput83626531.21%-268%
ConcurrentHashMapput1614921230.20%11%
ConcurrentHashMapput3215649260.10%17%

Concurrent Map Performance Comparison (server, 8cpu)

MapOpperationThreadsAverage%STD%DIF (with 1 thread)
HashMapget130475330.0%0%
HashMapget275006030.1%146%
HashMapget4140808280.01%362%
HashMapget8251605690.01%769%
HashMapget16172157571.2%464%
HashMapget32117973307.7%287%
Hashtableget111658340.06%0%
Hashtableget243448516.9%-168%
Hashtableget42032312.7%-473%
Hashtableget82012902.1%-479%
Hashtableget163584592.3%-225%
Hashtableget323039754.7%-283%
ConcurrentHashMapget121196020.0%0%
ConcurrentHashMapget250443170.1%137%
ConcurrentHashMapget494224600.09%344%
ConcurrentHashMapget8101954800.0%381%
ConcurrentHashMapget1697992731.2%362%
ConcurrentHashMapget3295579750.1%350%
HashMapput117298010.02%0%
HashMapput213473230.1%-28%
HashMapput412677700.02%-36%
HashMapput810562260.0%-63%
HashMapput1610554620.01%-63%
HashMapput3210551390.01%-63%
Hashtableput113914580.08%0%
Hashtableput221179313.1%-556%
Hashtableput41910522.8%-628%
Hashtableput82004803.4%-594%
Hashtableput163997482.3%-248%
Hashtableput324008403.2%-247%
ConcurrentHashMapput115035880.2%0%
ConcurrentHashMapput24411430.8%-240%
ConcurrentHashMapput43805651.1%-295%
ConcurrentHashMapput835405411.8%-324%
ConcurrentHashMapput1617366182.8%15%
ConcurrentHashMapput3216996475.7%13%

Very interesting results. Given the desktop machine has 2 CPUs, I would have expected the 2+ threaded tests to have at most 2x the single threaded test.  For the server results with 8 CPUs, I would expect the results to double until 8 threads, then flatten out.

Given Hashtable is synchronized, HashMap is not, and ConcurrentHashMap is partially synchronized, I would have expect HashMap to be about 2x, Hashtable to be about 1x, and ConcurrentHashMap to be somewhere in between. The thing I like best about running performance tests, is that you rarely get what you expect, and these results are not what I would have expected.

My basic premise holds, in that for get() HashMap had the best concurrency, then ConcurrentHashMap, and then Hashtable.  I would have not expected Hashtable to do so bad though.  Given it is synchronized, only one thread can perform a get() at one time, so naively one would expect the same results as a single thread.  The reality is that it had 5x worse performance than a single thread.  The reasons for this include that synchronization has a certain overhead, which modern JVMs optimize out when only a single thread is accessing the object, but with multiple threads this overhead becomes very apparent.  Also, contention in general has a huge performance cost, as the threads are busy waiting for the lock to become available.  In addition just having multiple threads adds some overhead with context switching and such, so in general the more threads, the worse the peformance unless the threads are doing something useful.

The desktop results for get() are worse than I would have expected with 2 CPUs, but perhaps the second CPU was busy with other things, such as the OS and garbage collection, etc.

The put() results are much more perplexing.  First of all, I know that running concurrent puts on a HashMap does not make much sense, as HashMap does not support concurrent puts.  I ran the test anyway, just to see what would happen, and the result is quite surprising.  I would expect similar results to the get() test.  However, HashMap had much worse results, similar to Hashtable, as if it were having some contention.  How could this be given that HashMap has no synchronized methods?  My only explanation is that the puts required modifying the same memory locations, so were experiencing contention on the memory access.  If you have a better explanation, please comment.

I would have also expected the put() concurrency for ConcurrentHashMap to be better.  I think the primary reason for this was that my tests looped over the same set of keys in the same order, so each thread was trying to put the same key at the same time.  Since ConcurrentHashMap works by having multiple pages and only having to lock a page on put() instead of the entire Map, it still had contention because for the most part the threads were accessing the same keys at the same time.  I think this is also why the > 8 threads fared better.  With more threads they got more out of synch, and had less page conflicts.  This is an important point, ConcurrentHashMap will only perform well when it has a large enough size to have many pages, and when the access to it is random.  If all the threads are accessing a single page, it is really no better than a Hashtable.

So, what does all this mean?  In general, if you have static meta-data that is read-only and requires concurrent access, then use HashMap (it is only not thread safe with puts, gets are fine).  If you require concurrent read-write access, then use ConcurrentHashMap.  If you just like being old school, then use Hashtable, but beware the hidden costs of concurrency.

7 comments :

  1. http://www.google.com/codesearch/p?hl=en#ih5hvYJNSIA/src/share/classes/java/util/HashMap.java&q=hashmap%20openjdk&sa=N&cd=1&ct=rc

    http://www.google.com/codesearch/p?hl=en#nScm2ktzXFg/src/share/classes/java/util/Hashtable.java&q=hashtable%20openjdk&sa=N&cd=8&ct=rc

    http://codesearch.google.com/codesearch/p?hl=en#-WpwJU0UKqQ/src/share/classes/java/util/concurrent/ConcurrentHashMap.java&q=concurrenthashmap&sa=N&cd=1&ct=rc

    ReplyDelete
  2. Hi,

    I think there is bug in the code..

    value = map.putIfAbsent(key, value);
    it should be
    value = map.putIfAbsent(key, newValue);

    -Ravi

    ReplyDelete
  3. Try http://sourceforge.net/projects/high-scale-lib/ too if you can.

    ReplyDelete
  4. Nice article , you have indeed cover the topic with great details with benchmarking numbers. I have also blogged my experience on java How Synchronization works in Java. let me know how do you find it.

    ReplyDelete
  5. It seems to me that in the case of HashMap, there could be bugs as the first get is not synchronized. This is basically the double checked locking (broken) pattern.

    http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

    ReplyDelete
  6. Very well written post! Great post. Thanks for sharing the whole source code as it will be more easy to understand by examining the code.
    sap partners

    ReplyDelete
  7. Also be aware that using HashMap.get() concurrently without synchronization can produce an infinite busy loop.
    http://bugs.sun.com/view_bug.do?bug_id=6423457

    ReplyDelete