Mailing-List: contact open-jpa-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: open-jpa-dev@incubator.apache.org
Received-SPF: softfail (herse.apache.org: transitioning domain of
 dezzio@bea.com does not designate 62.13.136.40 as permitted sender)
Message-ID: <465C6A8D.6050203@bea.com>
Date: Tue, 29 May 2007 14:01:49 -0400
From: "David Ezzio (asmtp)" <dezzio@bea.com>
User-Agent: Thunderbird 1.5.0.10 (Windows/20070221)
MIME-Version: 1.0
To: open-jpa-dev@incubator.apache.org
Subject: Comparison Metrics for OpenJPA's ConcurrentHashMap
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Recently, I did some testing of Map implementations under concurrency.

My primary purpose was to verify the reliability of OpenJPA's 
ConcurrentHashMap implementation. As I got into it, I saw the 
opportunity to get some performance metrics out of the test.

The biggest part of my task was coming up with a reliable and useful 
testing framework. I design it with the following two factors in mind: 
First, I wanted to test the edge conditions where an entry had just been 
added or removed or where a key's value had just been updated. The idea 
is that a number of threads add, remove, and update entries, while other 
threads check to see if these recent modifications are visible (or in 
the case of removals, not visible). Second, I wanted the testing 
framework itself to be free of synchronization. If the testing framework 
used synchronization then it would tend to serialize the readers and 
writers and thereby mask concurrency issues in the map implementation 
under test.

The testing framework uses a non-synchronizing, non-blocking FIFO queue 
as the mechanism for the writing threads to communicate their recent 
modifications to the reading threads.

To prevent writing threads from overwriting recent modifications before 
they could be read and verified, the testing framework walks the hash 
map keys in in a linear (or in the case of updates, circular) order. By 
using a hash map with a large enough capacity, readers have the time to 
verify the recent modifications before the writer threads come back to 
modify that part of the key space again.

Using an adapter for the map implementation, the testing framework 
starts five writer threads and ten reader threads at the same time. 
These threads run wide open for 30 seconds, except that the readers will 
give up their time slice if they find nothing on the queue. The HashMaps 
were all sized for the needed capacity upon creation, so no resizing 
occurred during testing.

I got some interesting results.

Four implementations were tested, Java's unsynchronized HashMap 
implementation, Java's synchronized HashMap implementation, Java's 
ConcurrentHashMap implementation, and OpenJPA's ConcurrentHashMap 
implementation.

Only Java's unsynchronized HashMap failed, as expected, under test. 
Under test, this implementation demonstrates its inability to handle 
concurrency. The other three implementations worked flawlessly under test.

The java.util.concurrent.ConcurrentHashMap implementation (available 
with Java 5 and 6) was the fastest implementation tested.

Java's synchronized wrapper for the HashMap implementation is one to two 
orders of magnitude slower than Java's ConcurrentHashMap implementation.

OpenJPA's ConcurrentHashMap compares equally with Java's 
ConcurrentHashMap in find operations and is 2-4 times slower in mutating 
operations.

Implementation   Add   Remove   Update  Find-a  Find-r  Find-u
---------------+------+-------+--------+-------+-------+------
synchronized     103     35       50      40      37     54
concurrent      13.2    6.4      6.1     0.6     0.3    1.1
OpenJPA         29.8   26.6     27.9     0.6     0.6    0.6


Legend:

synchronized:
java.util.Collections.synchronizedMap(new java.util.HashMap())
concurrent: java.util.concurrent.ConcurrentHashMap
OpenJPA: org.apache.openjpa.lib.util.concurrent.ConcurrentHashMap

Add: time for average add operation
Remove: time for average remove operation
Update: time for average update of new value for existing key
Find-a: time to find a recent addition
Find-r: time to NOT find a recent removal
Find-u: time to find a recent update

These times (in microseconds) are representative, but are not the 
average of several runs. The tests were run on a Dell Dual Core laptop 
under Windows. The performance meter was pegged during the tests.

David Ezzio