ArrayList in multi-thread context

[JerryWang]

We all know the concept that ArrayList is not "thread-safe", but why?

Test via the following code:

package thread;



import java.util.ArrayList;

import java.util.List;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;



class MyThread implements Runnable{



	private List<Integer> myList;

	private Object host;

	public MyThread(List<Integer> list){

		this.myList = list;

	}

	private void updateList(int i){

			myList.add(i);

	}

	@Override

	public void run() {

		for( int i = 0; i < 10;i++){

			updateList(i);

		}

		System.out.println("end: " + myList.size());

	}

}

public class MyExecutor {



	private ArrayList<Integer> taskList = new ArrayList<Integer>();

	private Object object = new Object();

	private void launch(){

		

        ExecutorService executorService= Executors.newFixedThreadPool(10);

        	executorService.execute(new MyThread(taskList));

        	executorService.execute(new MyThread(taskList));

	}

	public static void main(String[] args) {

		MyExecutor test = new MyExecutor();

		test.launch();

	}

}

A beginner of Java programmer may expect the ArrayList will finally have size as 40, since each thread will add twenty integer into it.

Unfortunately, when you run the code above, you will meet with ArrayIndexOutOfBoundsException.

If you set a breakpoint within this exception, you can find in the debugger that the exception is raised in line 459.

Here the internal array maintained by ArrayList class has length 10, however a new element is tried to insert with index 11, so exception occurs.

The reason is that the code in line 459, elementData[size++], is not an atomic operation. The real execution of these code might be reordered by the native compiler, suppose the first thread has growed the internal size of elementData to 10, and then it is preempted and the second thread now increases the variable size to 11, then execution is handed over to the first thread, then exception is raised.

There are many solution in JDK1.8 to resolve it.

The most straightforward approach is to add lock when the ArrayList is inserted.

The new complete source code is:

package thread;



import java.util.ArrayList;

import java.util.List;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;



class MyThread implements Runnable{



	private List<Integer> myList;

	private Object host;

	public MyThread(List<Integer> list, Object object){

		this.myList = list;

		this.host = object;

	}

	

	private void updateList(int i){

		synchronized(this.host){

			myList.add(i);

		}

	}

	

	@Override

	public void run() {

		for( int i = 0; i < 10;i++){

			updateList(i);

		}

		System.out.println("end: " + myList.size());

	}

	

}

public class MyExecutor {



	private ArrayList<Integer> taskList = new ArrayList<Integer>();

	private Object object = new Object();

	private void launch(){

		

        ExecutorService executorService= Executors.newFixedThreadPool(10);



        executorService.execute(new MyThread(taskList, object));

        executorService.execute(new MyThread(taskList, object));

	}

	public static void main(String[] args) {

		MyExecutor test = new MyExecutor();

		test.launch();

	}

}

When I use javap to view bytecode for method updateList, I found out that the method marked via keyword synchronized is wrapped by the set of operation monitorenter and monitorexit in compiled code.

If we replace the ArrayList with Vector, but don't use synchronized keyword to wrap the method, the code can still work. This is simply because the add method in Vector has used synchronized keyword for us:

In this case, the add method in compiled code is not wrapped by monitorenter and monitorexit, please compare it with above updateList.

The compiler is not so smart in my test. See the following code where the synchronized is not necessary at all since it is created locally, every thread will have its own instance:

However in the compiled byte code, the pair of monitorenter and monitorexit are still there.

This example gives us a hint: use synchronized with correct granularity.

Another solution is, create a wrapped List instance which is thread-safe by factory method Collections.synchronizedList.

In this case, when add method is called in the runtime, the thread-safe implementation is called to insert the element into list.