Monday, February 16, 2009

Synchronized collections in Java 5+

Picture courtesy of Swamibu@flickr
You probably encountered problem of which collection to use while writing concurrent applications. Which implementation to use when you have N concurrent writers and M concurrent readers? I will try to shortly answer this question on simple example.

The code below presents usage of different collection implementations while having 16 concurrent writer threads and 100 concurrent reader threads. At the same time writer threads modify the collection i.e. add new elements and reader threads iterate through actual collection state and operate on its elements.

public class ConcurrentCollectionsTest {
public static final int READERS_COUNT = 100;
public static final int COLLECTION_SIZE = 5000;
public static final int WRITERS_COUNT = 16;

static volatile int readExceptionCount = 0;
static CountDownLatch latch;

public static void main(String[] args) throws Exception {
Map<String, Collection<String>> map =
new LinkedHashMap<String, Collection<String>>();

map.put("ArrayList",
new ArrayList<String>());

map.put("Synchronized ArrayList",
Collections.synchronizedCollection(
new ArrayList<String>()));

map.put("ConcurrentLinkedQueue",
new ConcurrentLinkedQueue<String>());

map.put("CopyOnWriteArrayList",
new CopyOnWriteArrayList<String>());

for (Entry<String, Collection<String>> e: map.entrySet()) {
Collection<String> collection = e.getValue();
latch = new CountDownLatch(READERS_COUNT + WRITERS_COUNT);
readExceptionCount = 0;

long start = System.currentTimeMillis();
for (int i = 0; i < WRITERS_COUNT; ++i) {
Thread t = new Thread(new Writer(collection));
t.start();
}

for (int i = 0; i < READERS_COUNT; ++i) {
Thread t = new Thread(new Reader(collection));
t.start();
}

latch.await();
System.out.println("-----------------");
System.out.println("Stats for [" + e.getKey() + "]:");
System.out.printf("Collection's size: %d\n", collection.size());
System.out.printf("ConcurrentModificationException count [read]: %d\n", readExceptionCount);
System.out.printf("Duration: %d\n\n", System.currentTimeMillis() - start);
}
}

static class Reader implements Runnable {
private final Collection<String> collection;

Reader(Collection<String> col) {
this.collection = col;
}

public void run() {
try {
for (Iterator<String> i = collection.iterator(); i.hasNext();) {
// additional computing operation just to consume some time
String t = i.next() + "_added";
if (t.length() > 10 && i.hasNext()) {
i.next();
}
}
} catch (ConcurrentModificationException e) {
readExceptionCount++;
}
latch.countDown();
}
}

static class Writer implements Runnable {
private final Collection<String> collection;

Writer(Collection<String> col) {
this.collection = col;
}

public void run() {
try {
for (int i = 0; i < COLLECTION_SIZE; ++i) {
collection.add(Thread.currentThread().getName()
+ System.currentTimeMillis());
}
} catch (Exception e) {
// ignore
}
latch.countDown();
}
}
}

Results on my machine (numbers can vary on different hardware but problems/conclusions will be the same):

-----------------
Stats for [ArrayList]:
Collection's size: 77038
ConcurrentModificationException count [read]: 17
Duration: 1047 ms

-----------------
Stats for [Synchronized ArrayList]:
Collection's size: 80000
ConcurrentModificationException count [read]: 4
Duration: 1141 ms

-----------------
Stats for [ConcurrentLinkedQueue]:
Collection's size: 80000
ConcurrentModificationException count [read]: 0
Duration: 1046 ms

-----------------
Stats for [CopyOnWriteArrayList]:
Collection's size: 80000
ConcurrentModificationException count [read]: 0
Duration: 14344 ms

Conclusions
ArrayList (unsurprisingly) doesn't work at all - there is 17 ConcurrentModificationException on read attempt and what is more unacceptable this collection is in unpredictable state i.e. it's size should be 80000 instead of 77038 - it means that many items were not stored by the writer threads.

Synchronized ArrayList works better i.e. its state is correct but still you need additional synchronization in order to get rid of ConcurrentModificationException while iterating through it.

ConcurrentLinkedQueue works best in this case and does not add any performance penalties.

CopyOnWriteArrayList is the worst in this case because traversal operations does not vastly outnumber mutations.

The last conclusion would be to perform such test before deciding which implementation works best in your particular case. Also, read javadoc carefully to see implications and suggested use cases.

2 comments:

baker said...

This really doesn't make sense to me. How can you compare the performance of a queue to a list when they are different data structures, with different uses.

Anonymous said...

I would like to share with "Urbi et Orbi" another important thing I've just realized: 2*2 = 4!!!!