127

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?

rbento
  • 9,919
  • 3
  • 61
  • 61
象嘉道
  • 3,657
  • 5
  • 33
  • 49
  • 5
    That depends what you want to do with the collection. See [my blog post](http://blog.slaks.net/2011/11/one-of-most-useful-additions-to.html) (although it's about .Net, the concepts are the same). You are unlikely to be able to write correct thread-safe code with a `List`. – SLaks Nov 20 '11 at 19:01
  • 1
    Now, I am using *CopyOnWriteArrayList*, but *ConcurrentModificationException* exception is still thrown occasionally. – 象嘉道 Nov 20 '11 at 19:22
  • 2
    Please include more information about what you're doing with the collection so people can answer better, otherwise it's just a guess. – mattsh Nov 20 '11 at 19:34
  • 2
    The `ConcurrentModificationException` might not come from a synchronization problem; it also arises for example in a for-loop over a collection where you try to remove an element from the collection. – toto2 Nov 20 '11 at 19:55
  • 1
    I know it is not part of the package, but has someone tried `Vector`? – WesternGun Mar 18 '19 at 11:23

6 Answers6

112

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 Queues and Maps (and you can make Sets from Maps), 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:

ColinD
  • 108,630
  • 30
  • 201
  • 202
  • 20
    `CopyOnWriteArrayList` has the disadvantage of being very expensive on write (but cheap for reads) If you are doing lots of writes you are better off with a synchronized List or a queue. – Peter Lawrey Nov 21 '11 at 08:00
  • Just to add to this answer, generally you'd want a data-structure to be thread safe only if there are operations that will change the data or add/remove data. So unless you need to change the data in the "List" via some "set" method call, then the only other operation which is the add/remove operations are easily handled by a Queue data-structure (and it is also a best practice, unless of course if there is a need for the exception). – Dame Lyngdoh Apr 07 '21 at 18:27
97

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());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Travis Webb
  • 14,688
  • 7
  • 55
  • 109
  • 9
    *For this reason, you'll find no list implementations in java.util.concurrent* -- Uhm, there is a `ConcurrentHashMap` even though there is a `Collections.synchronizedMap` method. – aioobe Nov 20 '11 at 19:06
  • 12
    Read the Javadocs on `ConcurrentHashMap`. The details of the synchronization implementation are different. using the `synchronized` methods in `Collections` basically just wraps the class in a Java monitor. `ConcurrentHashMap` uses more clever concurrency features. – Travis Webb Nov 20 '11 at 19:08
  • 4
    Yep. Still, it makes your last sentence sort of invalid though. – aioobe Nov 20 '11 at 19:08
  • To add onto aioobe's comment, and as ColinD mentioned there is the CopyOnWriteArrayList – John Vint Nov 20 '11 at 19:12
  • 1
    If use a monitor, the performance of the program is really bad :-( – 象嘉道 Nov 20 '11 at 19:23
  • 11
    Just to add , iteration over newList is not thread safe. !! – bluelurker Mar 12 '17 at 09:43
  • @bluelurker wtf?! If iteration wasn't thread-safe than the list wasn't thread-safe at all. Hard to believe. I'll try it... – The incredible Jan Oct 17 '17 at 10:55
  • 2
    @bluelurker Thread safe if you "manually synchronize on the returned list when iterating over it" (java docs). synchronized (list) { Iterator i = list.iterator(); // Must be in synchronized block while (i.hasNext()) foo(i.next()); } – rimsky Jan 10 '18 at 21:18
10

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.

Ben Manes
  • 9,178
  • 3
  • 35
  • 39
9

ConcurrentLinkedQueue uses a lock-free queue (based off the newer CAS instruction).

Philipp Reichart
  • 20,771
  • 6
  • 58
  • 65
eSniff
  • 5,713
  • 1
  • 27
  • 31
  • 9
    ...which doesn't implement the `List` interface. – aioobe Nov 20 '11 at 19:04
  • You should be able to wrap it in a List interface. The performance benefits are worth it. But you are right :-), it doesn't now. – eSniff Nov 20 '11 at 19:10
  • 1
    eSniff, how would you go about implementing `List.set(int index, Object element)` with ConcurrentLinkedQueue? – John Vint Nov 20 '11 at 19:17
  • 4
    Most of the `List`-specific methods are either not going to be implementable using a `Queue` (add/set at a specific index, for example) or can sort of be implemented but will be inefficient (get from an index). So I don't think you could really wrap it. That said, I think the suggestion of a `Queue` is fine since the OP hasn't really explained why they need a `List`. – ColinD Nov 20 '11 at 19:20
  • 1
    @ColinD that's the answer I was going for. There's good reasons why the CLQ cannot be wrapped in a List. Though I agree, cannot rule out the Queue interface. – John Vint Nov 20 '11 at 19:24
  • Yea, I should have just keep my mouth shut and not answered without thinking about it... You are both right wrapping list would just be ugly. Upvote for all you guys for smacking me around :-). – eSniff Nov 20 '11 at 19:26
  • 2
    ❗️ Worth noting that: _"Beware that, unlike in most collections, the size method is NOT a constant-time operation. Because of the asynchronous nature of these queues, determining the current number of elements requires a traversal of the elements."_ – Behrang Jan 29 '18 at 03:13
  • Yes, size() operation on ConcurrentLinkedQueue is cpu inefficient. – Loïc Guzzetta Mar 23 '23 at 09:29
6

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.

shams
  • 3,460
  • 24
  • 24
3

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.

anre
  • 3,617
  • 26
  • 33