Data types for a concurrent method design

Question

Imagine I have a collection input, which contains approx. 100000 objects.

There is a thread pool of workers, each of which

1. takes an element of that collection,
2. does some calculations and
3. sometimes (in approx. 10 to max. 50 % of cases, i. e. between 10000 and 50000 times per run) adds the results of them to the output collection.

After all items in input have been processed, another routine takes output and does something with it.

I need the thread pool in order to process input as fast as possible. Every element of input should be processed exactly one time.

The order, in which the elements are processed, is irrelevant (both for input and output). output is write-only - the workers will only write there and won't do any other operations on output.

There are two parts of the problem, where thread safety is important:

1. The worker threads need to make sure that when worker thread A processes some element of input, other workers notice it and don't process the same element.
2. After worker finished processing of an element, the results should be added to the output collection.

Questions:

1. Which collection type can I safely use for input collection ( ConcurrentLinkedQueue? ) ?
2. Can I use normal LinkedList for the output collection (if 2 threads try to add different objects to the list at the same time, can it occur that one of the objects won't be saved) ?

Answer 1

CLQ is fine for the input given your constraints, just be careful when polling size() for checking the termination of the input: as mentioned in the doc, it's not a constant time operation.

For the output, I doubt LinkedList is thread-safe, even just for adding. Adding means altering the state of the head node, and if two thread add at the same time this may create issues and detached elements.

You can use another CLQ or a LinkedBlockingDeque . There is also a simpler SynchronizedLinkedList.