CODEWITHSUNDEEP
javamultithreadinglinked-listconcurrentmodification
user1536654
user1536654

Reputation: 11

LinkedList Iterator throwing Concurrent Modification Exception

Is there a way to stop a ListIterator from throwing a ConcurrentModificationException? This is what I want to do:

The problem here lies in the retrieval of these objects. I would obviously be using a ListIterator to do this work. However, I predict this will not get very far, thanks to the ConcurrentModificationException that will be thrown according to the documentation. I want the list to be modifiable, and for the iterators to not care. In fact, it is expected that these objects will create and destroy other objects in the list. I've thought of a few work-arounds:

Thus, my question. Is there a way to stop a ListIterator from throwing a ConcurrentModificationException?

Upvotes: 1

Views: 1361

Answers (4)

Gray
Gray

Reputation: 116908

Is there a way to stop a ListIterator from throwing a ConcurrentModificationException?

That you are asking this question this way shows a lack of understanding of how to properly use threads to increase the performance of your application.

The whole purpose of using threads is to divide processing and IO into separate runnable entities that can be executed in parallel -- independent of each other. If you are forking threads to all work on the same LinkedList then you most likely will have a performance loss or minimal gain since the overhead of the synchronization necessary to keep each of the threads' "view" of the LinkedList in sync would counter any gains due to parallel execution.

The question should not be "how to I stop ConcurrentModificationException", it should be "how can I use threads to improve the processing of a list of objects". That's the right question.

To process a collection of objects in parallel with a number of threads, you should be using an ExecutorService thread-pool. You create the pool with something like the following code. Each of the entries in your LinkedList (in this example Job) would then be processed by the threads in the pool in parallel.

// create a thread pool with 10 workers
ExecutorService threadPool = Executors.newFixedThreadPool(10);
// submit each of the objects in the list to the pool
for (Job job : jobLinkedList) {
    threadPool.submit(new MyJobProcessor(job));
}
// once we have submitted all jobs to the thread pool, it should be shutdown
threadPool.shutdown();
// wait for the thread-pool jobs to finish
threadPool.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
synchronized (jobLinkedList) {
    // not sure this is necessary but we need to a memory barrier somewhere
}
...
// you wouldn't need this if Job implemented Runnable
public class MyJobProcessor implements Runnable {
    private Job job;
    public MyJobProcessor(Job job) {
        this.job = job;
    }
    public void run() {
        // process the job
    }
}

Upvotes: 2

Alex D
Alex D

Reputation: 30455

Please see the answer from @assylias -- his advice is good. I would add that if you decide to write your own linked list class, you need to think very carefully about how to make it thread-safe.

Think about all the ways your list could get mangled if multiple threads tried to modify it simultaneously. Just locking 1 or 2 nodes is not enough -- as an example, take the following list:

A -> B -> C -> D

Imagine that one thread tries to remove B, just as another thread is removing C. To remove B, the link from A needs to "jump" over B to C. But what if C is no longer part of the list by that time? Likewise, to remove C, the link from B needs to be changed to jump to D, but what if B has already been removed from the list by that time? Similar issues arise when nodes are added simultaneously to nearby parts of the list.

If you have 1 lock per node, and you lock 3 nodes when doing a "remove" operation (the node to be removed, and the nodes before and after it), I think it will be thread-safe. You need to also think carefully about which nodes must be locked when adding nodes, and when traversing the list. To avoid deadlocks, you need to make sure to always acquire locks in a constant order, and when traversing the list, you need to use "hand-over-hand" locking (which precludes the use of ordinary Java monitors -- you need explicit lock objects).

Upvotes: 0

assylias
assylias

Reputation: 328737

You seem concerned with performance. Have you actually measured the performance hit of using an O(n) vs O(1) algorithm? Depending on what you are doing and how frequently you are doing it, it might be acceptable to simply use a CopyOnWriteArrayList which is thread safe. Its iterators are also thread safe.

The main performance drag is on mutative operations (set, add, remove...): a new list is recreated each time.

However, the performance will be good enough for most applications. I would personally try using that, profile my application to check that the performance is good enough, and move on if it is. If it is not, you will need to find other ways.

Upvotes: 2

Sean Owen
Sean Owen

Reputation: 66886

You could use one Iterator to scan the list, and use an Executor to do the work on each object by passing off to a pool of threads. That's easy. There's overhead in packaging up work units this way. You still have to be careful to use Iterator method to modify the list, only, but maybe that simplifies the problem.

Or can you perform your work in one pass, then list modification in the next?

Can you split into N lists?

Upvotes: 0

Related Questions