CODEWITHSUNDEEP
javaperformancemultithreadingdata-structures
Martin Wiboe
Martin Wiboe

Reputation: 2119

What collection supports multiple simultaneous insertions?

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

Upvotes: 3

Views: 250

Answers (5)

Mark Peters
Mark Peters

Reputation: 81074

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.

Upvotes: 1

Michael Borgwardt
Michael Borgwardt

Reputation: 346310

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.

Upvotes: 3

Pete Kirkham
Pete Kirkham

Reputation: 49311

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.

Upvotes: 0

gustafc
gustafc

Reputation: 28865

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.

Upvotes: 10

Brian Clapper
Brian Clapper

Reputation: 26211

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."

Upvotes: 0

Related Questions