8

Java has tons of different Collections designed for concurrency and thread safety, and I'm at a loss as to which one to choose for my situation.

Multiple threads may be calling .add() and .remove(), and I will be copying this list frequently with something like List<T> newList = new ArrayList<T>(concurrentList). I will never be looping over the concurrent list.

I thought about something like CopyOnWriteArrayList, but I've read that it can be very inefficient because it copies itself every time it's modified. I'm hoping to find a good compromise between safety and efficiency.

What is the best list (or set) for this situation?

Rogue
  • 636
  • 8
  • 22
  • 1
    Are you sure you need a list? Would a Map or Set meet your needs. It much easier to have concurrent access to a Map or Set than a list. – bhspencer Jun 08 '15 at 02:11
  • @bhspencer Yes, I think a set could work. – Rogue Jun 08 '15 at 02:13
  • If you usually only add and remove elements from the end and you copy the list often the most efficient data structure would be an immutable singly linked list which java unfortunately doesn't have build in but it's a very simple data structure so you can quickly implement it yourself. – Tesseract Jun 08 '15 at 02:23
  • 1
    You can make a ConcurrentSet backed by a ConcurrentHashMap with: Map map = new ConcurrentHashMap(); Set set = Collections.newSetFromMap(map); – bhspencer Jun 08 '15 at 02:24
  • @SpiderPig While that sounds enticing, I'm not too experienced in that area. I have no idea where to begin writing such an implementation. – Rogue Jun 08 '15 at 02:25
  • See this [related question](http://stackoverflow.com/questions/8203864/the-best-concurrency-list-in-java) – augray Jun 08 '15 at 02:37
  • @augray Good info there, but much of it I'd already seen while researching. I saw `Queue` mentioned there. Do you think that would work well here? – Rogue Jun 08 '15 at 02:41
  • Converting a list of your choice to a synchronized list can always be done by using `Collections.synchronizedList(myList)`. As far as efficiency is concerned, it simply makes all calls to the list object synchronize on the list itself. So two threads can't make calls to it at the same time no matter what operations they're performing. – augray Jun 08 '15 at 02:42
  • @Rogue It really depends on whether your use case fits with a queue. If you are okay with always adding and removing from the front, it may be more efficient. See [ConcurrentLinkedQueue](https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html) – augray Jun 08 '15 at 02:43
  • It is hard to suggest without knowing how you are using the `List`, your access pattern etc. – Adrian Shum Jun 08 '15 at 02:49
  • 1
    How often do you call add/remove in comparison to the number of copy operations? And do you really need to add/remove elements from the same list in different threads instead of each thread editing another copy? – Tesseract Jun 08 '15 at 02:51
  • Several threads will be add/remov-ing, and a single looping thread will be copying it and performing operations on the elements in the copied collection frequently (around every second?) – Rogue Jun 08 '15 at 02:55
  • How long is the list? – Tesseract Jun 08 '15 at 02:57
  • I'd expect 0-10 elements on average, but there could be up to 50+ – Rogue Jun 08 '15 at 02:59
  • 1
    50 elements once every second? Then why are you worried about performance? You only need to worry about that if you get to millions of elements per second. – Tesseract Jun 08 '15 at 03:01

4 Answers4

4

As @SpiderPig said, the best case scenario with a List would be an immutable, singly-linked list.

However, looking at what's being done here, a List is unnecessary (@bhspencer's comment). A ConcurrentSkipListSet will work most efficiently (@augray).

This Related Thread's accepted answer offers more insight on the pros and cons of different concurrent collections.

Community
  • 1
  • 1
Rogue
  • 636
  • 8
  • 22
  • 1
    Note that a synchronizedSet also has an object-wide lock (all calls to it will block so only one thread can work with it at a time). If you can find a way to use a concurrent object rather than a synchronized one, you will likely be better off performance-wise (that is, assuming that this resource impacts perfromance, which seems like a safe assumption given the question). – augray Jun 08 '15 at 02:56
  • 1
    If you're willing to use a set, [ConcurrentSkipListSet](https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentSkipListSet.html) will likely be more efficient than a synchronizedSet. From *Java Concurrency in Practice*: "Replacing synchronized collections with concurrent collections can offer dramatic scalability improvements with little risk." – augray Jun 08 '15 at 02:59
1

You might want to look into whether a ctrie would be appropriate for your use case - it has thread-safe add and remove operations, and "copying" (in actuality, taking a snapshot of) the data structure runs in O(1). I'm aware of two JVM implementations of the data structure: implementation one, implementation two.

Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69
0
Collections.newSetFromMap(new ConcurrentHashMap<...>())

This is typically how a normal Set is done (HashSet is really a modified wrapper over HashMap). It offers both the advantages of performance/concurrecy from ConcurrentHashMap, and does not have extra features like ConcurrentSkipListSet (ordering), COW lists (copying every modification), or concurrent queues (FIFO/LIFO ordering).

Edit: I didn't see @bhspencer's comment on the original post, apologies for stealing the spotlight.

0

Hashset being hashing based would be better than List. Add last and remove first will be good with LinkedList. Search will be fast in arraylist being array index based.

Thanks,

Shailendra Singh
  • 483
  • 5
  • 9