Java ArrayList thread unsafe example explanation

If always one add() or remove() call is completely finished before another one is started, your reasoning is correct. But ArrayList doesn't guarantee that as its methods aren't synchronized. So, it can happen that two threads are in the middle of some modifying calls at the same time.

Let's look at the internals of e.g. the add() method to understand one possible failure mode.

When adding an element, ArrayList increases the size using size++. And this is not atomic.

Now imagine the list being empty, and two threads A and B adding an element at exactly the same moment, doing the size++ in parallel (maybe in different CPU cores). Let's imagine things happen in the following order:

• A reads size as 0.
• B reads size as 0.
• A adds one to its value, giving 1.
• B adds one to its value, giving 1.
• A writes its new value back into the size field, resulting in size=1.
• B writes its new value back into the size field, resulting in size=1.

Although we had 2 add() calls, the size is only 1. If now you try to remove 2 elements (and this time it happens sequentially), the second remove() will fail.

To achieve thread safety, no other thread should be able to mess around with the internals like size (or the elements array) while one access is currently in progress.

Multi-threading is inherently complex in that the calls from multiple threads can not only happen in any (expected or unexpected) order, but that they can also overlap, unless protected by some mechanism like synchronized. On the other hand, excessive use of the synchronization can easily lead to poor multi-thread performance, and also to dead-locks.

As a supplement to @RalfKleberhoff's answer,

I think every remove() call is guaranteed to be preceded by at least one add() call,

Yes.

so the code should be OK even the order is messed up

No, that is not a valid inference with respect to a multithreaded program.

Your program contains data races as a result of two threads both accessing the same shared, non-atomic object, with some of those accesses being writes, without appropriate synchronization. The whole behavior of a program that contains data races is undefined, so in fact you cannot draw any conclusions at all about its behavior.

Do not try to cheat or scrimp on synchronization. Do minimize the amount of it that you need by limiting your use of shared objects, but where you need it, you need it, and the rules for determining when and where you need it are not that hard to learn.

ArrayList in java docs says,

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.

Why this code is not thread safe ?

Multiple thread running on Machine runs independent of each other.

  public void method1(int loopNumber) {
        for (int i = 0; i < loopNumber; i++) {  
            method2();
            method3();
        }
    }

Here method2() and method3() are being process sequential within the thread but not across the thread. ArrayList list is common between both thread. which will be in inconstant state between both thread on multi core system.

Interesting test would be add empty check in method3() and set LOOP_NUMBER = 10000;

private void method3()
{
    if (!list.isEmpty())
        list.remove(0);
}

In result you should get same Runtime Exception some thing like java.lang.IndexOutOfBoundsException: Index: 0, Size: 1 or java.lang.IndexOutOfBoundsException: Index: 0, Size: 0 because of same reason inconstant state of variable in list i.e. size.

To fix this issue you could have added synchronized like below or use Syncronized list

public void method1(int loopNumber)
{
    for (int i = 0; i < loopNumber; i++)
    {
        synchronized (list)
        {
            method2();
            method3();
        }
    }
}