What are the possible problems caused by adding elements to unsynchronized ArrayList's object by multiple threads simultaneously?

Question

What are the possible problems caused by adding elements to unsynchronized ArrayList's object by multiple threads simultaneously?

Tried to run some experiments with a static ArrayList with multiple threads but couldn't find much.

Here i am expecting much of the side effects of not synchronizing an ArrayList or like Objects in a multithreaded environment.

Any good example showing side effects would be appreciable. thanks.

below is my little experiment which ran smoothly without any exception.

I also wonder why it didn't throw any ConcurrentModificationException?

import java.util.ArrayList;
import java.util.List;

public class Experiment {
     static List<Integer> list = new ArrayList<Integer>();
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println("A " + i);
            new Thread(new Worker(list, "" + i)).start();
        }
    }   
}

class Worker implements Runnable {
    List<Integer> al;
    String name;

    public Worker(List<Integer> list, String name) {
        this.al = list;
        this.name = name;
    }

    @Override
    public void run() {
        while (true) {
            int no = (int) (Math.random() * 10);
            System.out.println("[thread " + name + "]Adding:" + no + "to Object id:" + System.identityHashCode(al));
            al.add(no);
        }
    }
}

Bryner

Because the docs state "This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible." AFAIK, ArrayList does not enforce rules to disallow this. It's Iterator does. If you wanna see results, try removing items from one of the threads while others are adding and see if the results are as expected. Right now, all threads are simply adding to the list (and print as soon as they add to it, which is the biggest flaw of this test), so you can't expect your console to display strange results – Chrissy

Your threads are actually somewhat synchronized because of System.out.println... – Chez

Re, "Tried to run some experiments...but couldn't find much." That's what makes concurrency bugs so insidious: They can sometimes be hard to reproduce. Sometimes, a program that allows threads unsynchronized access to shared data can survive months of testing, only to crash at a customer site after it has been released. (Don't ask me how I know!) – Convoy

Re, "...a static ArrayList..." Be careful with your words there. There is no such thing as a static object in Java. What's static in your example is the variable, not the list. But more to the point, what's important in your example is that the list is shared by several threads. You don't need a static variable to share data: That's just one easy way of doing it. – Convoy

@Chez you give me another angle of view. Thanks – Bryner

Answer 1

You will usually encounter issues when the list is resized to accommodate more elements. Look at the implementation of ArrayList.add()

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

if there is no synchronization, the array's size will change between the call to ensureCapacityInternal and the actual element insertion. This will eventually cause an ArrayIndexOutOfBoundsException to be thrown.

Here is the code that produces this behavior

final ExecutorService exec = Executors.newFixedThreadPool(8);
final List<Integer> list = new ArrayList<>();
for (int i = 0; i < 8; i++) {
    exec.execute(() -> {
        Random r = new Random();
        while (true) {
            list.add(r.nextInt());
        }
    });
}

Zollie

Thanks @noscreen I almost forgot about that. – Bryner

Answer 2

By adding element into unsunchronized ArrayList used by multiple thread, you may get null value in place of actual value as you desired.

This happen because of following code of ArrayList class.

 public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
     }

ArrayList class first check its current capacity and if require then increment its capacity(default capacity is 10 and next increment (10*3)/2) and put default class level value in new space.

Let suppose we are using two thread and both comes at same time to add one element and found that default capacity(10) has been fulled and its time to increment its capacity.At First threadOne comes and increment the size of ArrayList with default value using ensureCapacity method(10+(10*3/2)) and put its element at next index(size=10+1=11) and now new size is 11. Now second thread comes and increment the size of same ArrayList with default value using ensureCapacity method(10+(10*3/2)) again and put its element at next index (size=11+1=12) and now new size is 12. In this case you will get null at index 10 which is the default value.

Here is the same code for above.

package com;

import java.util.ArrayList;
import java.util.List;

public class Test implements Runnable {

    static List<Integer> ls = new ArrayList<Integer>();

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(new Test());
        Thread t2 = new Thread(new Test());

        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(ls.size());
        for (int i = 0; i < ls.size(); ++i) {
            System.out.println(i + "  " + ls.get(i));
        }
    }

    @Override
    public void run() {
        try {
            for (int i = 0; i < 20; ++i) {
                ls.add(i);
                Thread.sleep(2);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

output:

39
0  0
1  0
2  1
3  1
4  2
5  2
6  3
7  3
8  4
9  4
10  null
11  5
12  6
13  6
14  7
15  7
16  8
17  9
18  9
19  10
20  10
21  11
22  11
23  12
24  12
25  13
26  13
27  14
28  14
29  15
30  15
31  16
32  16
33  17
34  17
35  18
36  18
37  19
38  19

1. After running two or three time you will get null value sometime at index 10 and some time at 16.

2. As mentioned in above Answer by noscreenname you may get ArrayIndexOutOfBoundsException from this code code. If you remove Thread.sleep(2) it will generate frequently.

3. Please check total size of array which is less then as you required. According to code it should 40(20*2) but you will get different on every time.

Note : It is possible you may have to run this code multiple time to generate one or multiple scenario.

Acescent

Thank you for this reconfirmation. I acutally am in a situation in which a 3rd party library which lazily initializes an array which then contains null values occasionally. I suspected that the initialization code is sometimes triggered by two different threads and this answer hardens my suspicion. Thanks. – Prothesis

Answer 3

Here is a simple example: I add 1000 items to a list from 10 threads. You would expect to have 10,000 items at the end but you probably won't. And if you run it several times you will probably get a different result each time.

If you want a ConcurrentModificationException, you can add a for (Integer i : list) { } after the loop that creates the tasks.

public static void main(String[] args) throws Exception {
   ExecutorService executor = Executors.newFixedThreadPool(10);
   List<Integer> list = new ArrayList<> ();
   for (int i = 0; i < 10; i++) {
     executor.submit(new ListAdder(list, 1000));
   }
   executor.shutdown();
   executor.awaitTermination(1, TimeUnit.SECONDS);

   System.out.println(list.size());
}

private static class ListAdder implements Runnable {
  private final List<Integer> list;
  private final int iterations;

  public ListAdder(List<Integer> list, int iterations) {
    this.list = list;
    this.iterations = iterations;
  }

  @Override
  public void run() {
    for (int i = 0; i < iterations; i++) {
      list.add(0);
    }
  }
}

Chez

Answer 4

ConcurrentModificationException occurs only when you modify the list when the same list is iterated using Iterator. Here you are simply adding data to you list from multiple threads which will not produce the exception. Try to use iterator some where & you will see the exception.

Find below your example modified to produce ConcurrentModificationException.

public class Experiment {
     static List<Integer> list = new ArrayList<Integer>();
     public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println("A " + i);
            new Thread(new Worker(list, "" + i)).start();
        }
        Iterator<Integer> itr = list.iterator();
        while(itr.hasNext()) {
            System.out.println("List data : " +itr.next());
        }
    }   
}

Ohalloran