What collection supports multiple simultaneous insertions?

Question

Hi,

We are developing a Java application with several worker threads. These threads will have to deliver a lot of computation results to our UI thread. The order in which the results are delivered does not matter.

Right now, all threads simply push their results onto a synchronized Stack - but this means that every thread must wait for the other threads before results can be delivered.

Is there a data structure that supports simultaneous insertions with each insertion completing in constant time?

Thanks,

Martin

Answer 1

Take a look at java.util.concurrent.ConcurrentLinkedQueue, java.util.concurrent.ConcurrentHashMap or java.util.concurrent.ConcurrentSkipListSet. They might do what you need. ConcurrentSkipListSet, for instance, claims to have "expected average log(n) time cost for the contains, add and remove operations and their variants. Insertion, removal, and access operations safely execute concurrently by multiple threads."

Answer 2

ConcurrentLinkedQueue is designed for high contention. Producers enqueue stuff on one end and consumers collect elements at the other end, so everything will be processed in the order it's added.

ArrayBlockingQueue is a better for lower contention, with lower space overhead.

Edit: Although that's not what you asked for. Simultaneuos inserts? You may want to give every thread one output queue (say, an ArrayBlockingQueue) and then have the UI thread poll the separate queues. However, I'd think you'll find one of the two above Queue implementations sufficient.

Answer 3

Two other patterns you might want to look at are

• each thread has its own collection, when polled it returns the collection and creates a new one, so the collection only holds the pending items between polls. The thread needs to protect operations on its collection, but there is no contention between threads. This is blocking (each thread cannot add to its collection while the UI thread pulls updates from it), but can reduce contention (no contention between threads).

• each thread has its own collection, and appends the results to a common queue which is protected using a Lock.tryLock(). The thread continues processing if it fails to acquire the lock. This makes it less likely that a thread will block waiting for the shared queue.

Answer 4

Right now, all threads simply push their results onto a synchronized Stack - but this means that every thread must wait for the other threads before results can be delivered.

Do you have any evidence indicating that this is actually a problem? If the computation performed by those threads is even the least little bit complex (and you don't have literally millions of threads), then lock contention on the result stack is simply a non-issue because when any given thread delivers its results, all others are most likely busy doing their computations.

Answer 5

Well if you are looking for simultaneous (sounding like parallel) insertions, then any queue implementation cannot insert in parallel. It would be thread safe, but there is some serial work going on to ensure a mutual exclusion for each offer.

Parallel insertions are available with a ConcurrentHashMap or BlockingDeque. The ConcurrentHashMap employs lock striping that will allow for parallel puts into each independent entry (or more accurately segment). The BlockingDeque allows you to offerFirst/offerLast for parallel insertions (assuming enough space on the Deque.

Answer 6

Take a step back and evaluate whether performance is the key design consideration here. Don't think, know: does profiling back it up?

If not, I'd say a bigger concern is clarity and readability of design, and not introducing new code to maintain. It just so happens that, if you're using Swing, there is a library for doing exactly what you're trying to do, called SwingWorker.