Concurrent threads adding to ArrayList at same time - what happens?

Question

We have multiple threads calling add(obj) on an ArrayList.

My theory is that when add is called concurrently by two threads, that only one of the two objects being added is really added to the ArrayList. Is this plausable?

If so, how do you get around this? Use a synchronized collection like Vector?

Blocked

Answer 1

There is no guaranteed behavior for what happens when add is called concurrently by two threads on ArrayList. However, it has been my experience that both objects have been added fine. Most of the thread safety issues related to lists deal with iteration while adding/removing. Despite this, I strongly recommend against using vanilla ArrayList with multiple threads and concurrent access.

Vector used to be the standard for concurrent lists, but now the standard is to use the Collections synchronized list.

Also I highly recommend Java Concurrency in Practice by Goetz et al if you're going to be spending any time working with threads in Java. The book covers this issue in much better detail.

Lupelupee

"it has been my experience that both objects have been added fine" just want to point out that this is just sheer luck. Likely the window for a data corruption issue with ArrayList is extremely small, but it still exists – Apropos

Right, and that's sort of my point. In the vast majority of cases there will be no problem; but we don't program to the majority of cases. Thus why I strongly recommended against using ArrayList. – Lupelupee

If two threads read the same value of the list being modified, we are bound to lose an update depending on which thread finishes updating the list first because the second thread will overwrite the update of the first thread. – Mandel

Answer 2

Any number of things could happen. You could get both objects added correctly. You could get only one of the objects added. You could get an ArrayIndexOutOfBounds exception because the size of the underlying array was not adjusted properly. Or other things may happen. Suffice it to say that you cannot rely on any behavior occurring.

As alternatives, you could use Vector, you could use Collections.synchronizedList, you could use CopyOnWriteArrayList, or you could use a separate lock. It all depends on what else you are doing and what kind of control you have over access to the collection.

Jarrettjarrid

Answer 3

I came up with the following code to mimic somewhat a real world scenario.

100 tasks are run in parallel and they update their completed status to the main program. I use a CountDownLatch to wait for task completion.

import java.util.concurrent.*;
import java.util.*;

public class Runner {

    // Should be replaced with Collections.synchronizedList(new ArrayList<Integer>())
    public List<Integer> completed = new ArrayList<Integer>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        Runner r = new Runner();
        ExecutorService exe = Executors.newFixedThreadPool(30);
        int tasks = 100;
        CountDownLatch latch = new CountDownLatch(tasks);
        for (int i = 0; i < tasks; i++) {
            exe.submit(r.new Task(i, latch));
        }
        try {
            latch.await();
            System.out.println("Summary:");
            System.out.println("Number of tasks completed: "
                    + r.completed.size());
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        exe.shutdown();
    }

    class Task implements Runnable {

        private int id;
        private CountDownLatch latch;

        public Task(int id, CountDownLatch latch) {
            this.id = id;
            this.latch = latch;
        }

        public void run() {
            Random r = new Random();
            try {
                Thread.sleep(r.nextInt(5000)); //Actual work of the task
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            completed.add(id);
            latch.countDown();
        }
    }
}

When i ran the application 10 times and at least 3 to 4 times the program did not print correct number of completed tasks. Ideally it should print 100(if no exceptions happen). But in some cases it was printing 98, 99 etc.

Thus it proves that concurrent updates of ArrayList will not give correct results.

If i replace the ArrayList with a Synchronized version, the program outputs the correct results.

Thrave

Answer 4

You could also get a null, an ArrayOutOfBoundsException, or something left up to the implementation. HashMaps have been observed to go into an infinite loop in production systems. You don't really need to know what might go wrong, just don't do it.

You could use Vector, but it tends to work out the interface is not rich enough. You will probably find that you want a different data structure in most cases.

Vinegar

I've also seen null added each time I had threads do an add() at the same time. – Psychotechnology

Answer 5

you can use List l = Collections.synchronizedList(new ArrayList()); if you want thread safe version of arrayList.

Erase

asking for clarify, would this be done in the constructor? – Quadrivium

Answer 6

In my recently experience using ArrayList to add new elements from different threads will miss a few of them, so using Collections.synchronizedList(new ArrayList()) avoid that issue.

List<String> anotherCollection = new ArrayList<>();
List<String> list = new ArrayList<>();
// if 'anotherCollection' is bigger enough it will miss some elements.
anotherCollection.parallelStream().forEach(el -> list.add("element" + el));

List<String> listSync = Collections.synchronizedList(new ArrayList<>());
// regardless of 'anotherCollection' is bigger it will add all the elements.
anotherCollection.parallelStream().forEach(el -> list.add("element" + el));

Myca

I believe last line should be anotherCollection.parallelStream().forEach(el -> listSync.add("element" + el)); – Categorical

Answer 7

The behavior is probably undefined since ArrayList isn't threadsafe. If you modify the list while an Iterator is interating over it then you will get a ConcurrentModificationException. You can wrap the ArrayList with Collection.synchronizedList or use a thread-safe collection (there are many), or just put the add calls in a synchronized block.

Zarf

Answer 8

You could use instead of ArrayList(); :

Collections.synchronizedList( new ArrayList() );

or

new Vector();

synchronizedList as of me preferable because it's:

• faster on 50-100%
• can work with already existing ArrayList's

Cracknel

I've had the some issue while using CompletableFuture with multiple threads adding data to a single ArrayList. What I noticed was occasionally one or two elements were missing in the arrayList after completableFuture completes. Solution was to use the Collections.synchronizedList( new ArrayList() ) & everything worked perfectly afterwards. – Maines

Answer 9

java.util.concurrent has a thread-safe array list. The standard ArrayList is not thread-safe and the behavior when multiple threads update at the same time is undefined. There can also be odd behaviors with multiple readers when one or more threads is writing at the same time.

Plenipotentiary

Answer 10

http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

Since there is no synchronization internally, what you theorize is not plausible.

So, things get out of sync, with unpleasant and unpredictable results.

Dispirited

Right, saw that. I had thought that a ConcurrentModificationException would have been thrown which is not happening for us.. maybe we're running into another side affect of not using a thread safe collection.. – Blocked

@Marcus that appears to only be the case if you modify the list while iterating over it. Also, there is no guarantee this exception will be thrown. – Dispirited