Choosing the best concurrency list in Java
JavaConcurrencyJava Problem Overview
My thread pool has a fixed number of threads. These threads need to write and read from a shared list frequently.
So, which data structure (it better be a List, must be monitor-free) in java.util.concurrent
package is best in this case?
Java Solutions
Solution 1 - Java
> had better be List
The only List
implementation in java.util.concurrent
is CopyOnWriteArrayList. There's also the option of a synchronized list as Travis Webb mentions.
That said, are you sure you need it to be a List
? There are a lot more options for concurrent Queue
s and Map
s (and you can make Set
s from Map
s), and those structures tend to make the most sense for many of the types of things you want to do with a shared data structure.
For queues, you have a huge number of options and which is most appropriate depends on how you need to use it:
Solution 2 - Java
Any Java collection can be made to be Thread-safe like so:
List newList = Collections.synchronizedList(oldList);
Or to create a brand new thread-safe list:
List newList = Collections.synchronizedList(new ArrayList());
Solution 3 - Java
If the size of the list if fixed, then you can use an AtomicReferenceArray. This would allow you to perform indexed updates to a slot. You could write a List view if needed.
Solution 4 - Java
ConcurrentLinkedQueue
uses a lock-free queue (based off the newer CAS instruction).
Solution 5 - Java
You might want to look at ConcurrentDoublyLinkedList written by Doug Lea based on Paul Martin's "A Practical Lock-Free Doubly-Linked List". It does not implement the java.util.List interface, but offers most methods you would use in a List.
According to the javadoc:
> A concurrent linked-list implementation of a Deque > (double-ended queue). Concurrent insertion, removal, and access > operations execute safely across multiple threads. Iterators are > weakly consistent, returning elements reflecting the state of > the deque at some point at or since the creation of the iterator. They > do not throw ConcurrentModificationException, and may > proceed concurrently with other operations.
Solution 6 - Java
If set is sufficient, ConcurrentSkipListSet might be used. (Its implementation is based on ConcurrentSkipListMap which implements a skip list.)
The expected average time cost is log(n) for the contains, add, and remove operations; the size method is not a constant-time operation.