Close

Java - Concurrent Collections

[Last Updated: Jul 2, 2017]

This is a quick walk-through tutorial of Java Concurrent collections.

Interfaces

java.util.concurrency package extends Queue interface to define new ADTs:



Operations




Implementations


All implementations of collections in java.util.concurrent package are thread safe. These implementations use fine grained fine grained locking/synchronization for thread safety. 

Impl
 
ADT
 
Data Structure
 
Performance 
(Big O notation)
ArrayBlockingQueue BlockingQueue Array of objects.
Bounded.
Supports fairness policy. If fairness=true, threads are guaranteed to access in FIFO order.
A classic bounded buffer. 		offer, peek, poll, size:O(1)
put, take: O(1) if ignore blocking time.

Fairness generally decreases throughput but avoids producer/consumer starvation.
LinkedBlockingQueue BlockingQueue Linked structure.
optionally-bounded 		offer, peek, poll, size:O(1)
put, take uses separate locks, higher throughput. Even more throughput if unbounded (no bound blocking, hence more data passing through).
It has less predictable performance because of dynamic memory allocation and fragmentation (hold locks longer).
ConcurrentLinkedQueue
 Queue Linked structure.
Unbounded.
Not-blocking but still thread-safe.
Null not permitted.
Appropriate choice over LinkedBlockingQueue when many threads access the collection. 		The methods employs an efficient "wait-free" algorithm.
offer, peek, poll:O(1)
size: O(n) because of the asynchronous nature.
size method is not very useful in concurrent applications: if elements are added or removed during execution of this method, the returned result may be inaccurate.
Iterators are weakly consistent (don't throw ConcurrentModificationException and don't show the changes consistently to other threads).
DelayQueue BlockingQueue Internally, it uses a PriorityQueue instance which in turn uses Binary Heap data structure.
Unbounded.
Each element has to implement java.util.concurrent.Delayed interface.
When the method Delayed.getDelayed(TimeUnit unit) returns a value less than or equal to zero, the parent element becomes available in the queue for removing/polling, Regardless available or not, the element is still an element of the queue e.g. size() includes it.
It doesn't permit null. 		offer, poll, remove() and add: O(log n)
remove(Object), contains(Object) O(n)
peek, element, and size: O(1)
PriorityBlockingQueue BlockingQueue Binary Heap.
Unbounded
Uses the same ordering rules as PriorityQueue i.e. Elements are ordered to their natural ordering or by a Comparator provided at construction time. 		offer, poll, remove() and add: O(log n)
remove(Object), contains(Object) O(n)
peek, element, and size: O(1)
put: O(log n). As the queue is unbounded this method never blocks.
take: O(log n). This method blocks until an element becomes available.
SynchronousQueue
 BlockingQueue No standard data structure.
Applies rendezvous channels pattern where one thread handoff data/info to another thread. Each insert operation must wait for a corresponding remove operation by another thread, and vice versa. With this very unusual collection there are no elements stored (just a piece of info is transferred from one thread to another, one at a time).
Bounded: not applicable
put, offer, take, poll, : O(1)
Other methods has no effect as there's no formal collection data structure so poll() always returns null, isEmpty() always returns false, size() always return 0, iterator() always returns empty iterator etc.
LinkedTransferQueue TransferQueue Linked data structure.
Unbounded
Similar handoff concept as SynchronousQueue (above) but is a formal collection and has extra interface level support methods like tryTransfer, transfer etc. A useful transfer scenario: if the queue has elements in it already and transfer/tryTransfer called, it waits for the queue to empty including the new transferred element. 		offer, peek, poll:O(1)
size: O(n)
All blocking methods decrease throughput.
Generally LinkedTransferQueue outperforms SynchronousQueue by many factors.
LinkedBlockingDeque BlockingDeque Doubly linked nodes.
Optionally-bounded.
Appropriate choice over LinkedBlockingDeque when many threads access the collection. 		remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove() and the bulk operations: O(n)
Other operations: O(1)(ignoring time spent blocking).
ConcurrentLinkedDeque Deque Doubly linked nodes.
Unbounded.
Non-blocking but still thread-safe.
Doesn't permit null.
Appropriate choice over LinkedBlockingDeque when many threads access the collection. 		Index based get and remove methods: O(n)
size: O(n). Not reliable because of asynchronous operations
All other methods: O(1)
Iterators are weakly consistent They don't throw ConcurrentModificationException and don't show the changes consistently to other threads.
CopyOnWriteArrayList List Arrays of Objects .
Thread-safe.
All mutative methods (add, set, and so on) are implemented by making a fresh copy of the underlying array. 		add, contains, remove(E e): O(n)
get(Int index), next: O(1)
Lock is only used for write methods to increase throughput for reads. Write operation is costly because copying a new arrays every time.
Not recommended if there are a lot of random writes.
Iterators are very fast (no locks and thread interference). They never throw ConcurrentModificationException, neither are consistent with the writes made after the creation of iterators. Element-changing operations on iterators (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.
CopyOnWriteArraySet Set Arrays of Objects(Internally uses CopyOnWriteArrayList instance, avoiding duplicate elements by using CopyOnWriteArrayList.addIfAbsent).
Thread-safe.
add, contains, remove(E e): O(n)
next: O(1)
Iterator behavior is same as CopyOnWriteArrayList.
ConcurrentSkipListSet NavigableSet Backed by ConcurrentSkipListMap (Skip list data structure), where elements are populated as keys of the map.
Thread-safe.
Insertion, removal, and access operations safely execute concurrently by multiple threads.
contains, add, and remove operations and their variants: O(log n)
next: O(1)
size: O(n). Not reliable because of asynchronous operations.
Iterators and spliterators are weakly consistent.


Important things

  1. The performance cost of all above implementations is: locking and synchronization. Generally if there's only one thread accessing the collection, we should never use concurrent implementations over java.util non-synchronized collections.
  2. All Linked implementations of queues, are efficient as compare to 'LinkedList' (also implements Deque) as there's no searching or removing items by index.
  3. For a typical two threads producer-consumer 'Queue' scenarios, use blocking queues. If multiple threads are accessing then use one of ConcurrentXYZ Queue/Deque implementations.
  4. Above implementations are better choice over Collections.synchronziedXYX methods because those methods synchronize every method on a common lock ('this' monitor), restricting access to a single thread at a time. Above implementations use finer-grained locking mechanism called 'lock striping'.
  5. Sometimes we still want to choose Collections.synchronizedXYZ(..) but remember they result in less throughput. We should use them only if we have low concurrency, and only in scenarios where we want to be sure all changes are immediately visible to the other threads. If we use the iterators, we need to synchronize them externally to avoid ConcurrentModificationException.


Choosing a Concurrent Collection

See Also