Can't I remove element from Java shared ArrayList while simultaneously adding into it

Question

Firstly I'm not using iterator here.

I'm using 2 threads on an shared ArrayList ,1st is used to adding values into ArrayList and other is to make a temporary copy of it and do some operations on it and then removing all temp elements from original list.

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

public class ArraylistTest {

    public static void main(String...ar){
        new AddingThread().start();
        new RemovalThread().start();
    }
}

class RemovalThread extends Thread{
    static List<Integer> originalBigList = new ArrayList<>();

    @Override
    public void run(){
        System.out.println("RemovalThread started");
        while(true){
            try {
                sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("creating copy of originalBigList");
            List<Integer> tempList = new ArrayList<>(originalBigList);
            System.out.println("copied list");
            //
            //some operations on copied temp list
            //
            System.out.println("removing tempList elements after completing operations");
            System.out.println("originalBigList before removing size "+originalBigList.size());
            originalBigList.removeAll(tempList);
            System.out.println("removed!!");
            System.out.println("after size "+originalBigList.size());
        }
    }
}

class AddingThread extends Thread{

    @Override
    public void run(){
        System.out.println("Adding thread started");
        int ctr = 0;
        while(true){
            RemovalThread.originalBigList.add(ctr);
            ctr++;
        }
    }
}

Output :-

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 4102267
Exception in thread "Thread-0" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3210)
    at java.util.Arrays.copyOf(Arrays.java:3181)
    at java.util.ArrayList.grow(ArrayList.java:261)
    at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
    at java.util.ArrayList.add(ArrayList.java:458)
    at AddingThread.run(ArraylistTest.java:47)

Now my question is that i'm seeing in the output that the statement which is copying the list is executed which is making temp list from original list, but removal statement is not executing and not giving any Exception and i'm using simple arraylist not synchronised,so why is it so?

Is there any internal lock on remove or add operation? if yes then what is the use of Collections.synchronised( arraylist )?

Answer 1

I found your problem look at the following code

 public static void main(String ...args){
    long start = System.currentTimeMillis();
    List<Integer> l1 = new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();

    for(int i = 0 ; i < Integer.MAX_VALUE/10000;i++){
        l1.add(i);
        l2.add(i);
    }

    System.out.println(String.format("Field both arrays in %s seconds",(System.currentTimeMillis()-start)/1000) );
    start = System.currentTimeMillis();
    l1.removeAll(l2);

    System.out.println(String.format("Removed one array from other %s seconds",(System.currentTimeMillis()-start)/1000) );

}

Field both arrays in 0 seconds

Removed one array from other 34 seconds

It is a huge array now look at the output remove toke a huge amount of time and in your case, AddingThread makes the array huge so it's working it just takes a lot of time and meanwhile, AddingThread keeps working.By the way, it is understandable why it takes so long each value needs to be found first so it's O(n^2).Look how it works when I use HashSet instead of List (note:HashSet search is O(1))

public class HashSetTest {
public static Object obj = new Object();
public static void main(String... ar) {
    new AddingThread().start();
    new RemovalThread().start();
}

}

class RemovalThread extends Thread {
static Set<Integer> originalBigSet = new HashSet<>();
@Override
public void run() {
    System.out.println("RemovalThread started");
    while (true) {
        try {
            sleep(1000);
            System.out.println("creating copy of originalBigSet");
            Set<Integer> tempList;
            synchronized (HashSetTest.obj) {
                tempList = new HashSet<>(originalBigSet);
            }
            System.out.println("copied list");
            //
            //some operations on copied temp list
            //
            System.out.println("removing tempList elements after completing operations");
            System.out.println("originalBigSet before removing size " + originalBigSet.size());
            synchronized (HashSetTest.obj) {
                originalBigSet.removeAll(tempList);
            }
            System.out.println("removed!!");
            System.out.println("after size " + originalBigSet.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

}

class AddingThread extends Thread {

@Override
public void run() {
    System.out.println("Adding thread started");
    int ctr = 0;
    while (true) {
        synchronized (HashSetTest.obj) {
            RemovalThread.originalBigSet.add(ctr);
        }
        ctr++;
    }
}

}

Answer 2

Similar to the answer of @urag (especially the remark about being O(n²)), you can see the effect by modifying AddingThread like, so it adds only a limited number of items:

class AddingThread extends Thread{

    @Override
    public void run(){
        System.out.println("Adding thread started");
        int ctr = 0;
        while(true){

          if (ctr < 100_000) {
            RemovalThread.originalBigList.add(ctr);
            ctr++;
           }
      }
  }
}

This results in:

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 100000
removed!!
after size 0

Now, change 100_000 to 1_000_000, and you'll wait for a long time, and only see::

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 1000000

Answer 3

The following line

            List<Integer> tempList = new ArrayList<>(originalBigList);

Will iterate inside list constructor over originalBigList to create your tempList and if AddingThread will run in paralel it will throw the ConcurrentModificationException that kills your RemovalThread maybe you don't see it in console but it is probably there. I would sugest to use CopyOnWriteArrayList for your originalBigList