Multi Threading with ArrayList() got ArrayIndexOutOfBoundsException

Question

I've made the following code to run multiple thread through a non thread safe object (here an ArrayList) :

import java.time.LocalDateTime;
import java.util.List;
import java.util.ArrayList;

public class A implements Runnable {
    String name;

    static  List<Integer> list = new ArrayList();
    private static Object lock = new Object();

    A(String name) {
        this.name = name;
    }

    @Override
    public void run() {
        for(int i = 1; i <= 1000; i++) {
            list.add(i);
        }
        System.out.println(list.size());
    }
}

I was expecting this code just to produce wrong answers since ArrayList is not thread-safe. But instead I get this error :

Exception in thread "Thread-1" 1003
2401
2799
3799
java.lang.ArrayIndexOutOfBoundsException: 109
    at java.util.ArrayList.add(Unknown Source)
    at threads.A.run(A.java:16)5123

    at java.lang.Thread.run(Unknown Source)
Exception in thread "Thread-5" java.lang.ArrayIndexOutOfBoundsException: 4164
    at java.util.ArrayList.add(Unknown Source)
    at threads.A.run(A.java:16)
    at java.lang.Thread.run(Unknown Source)
6123

Can anyone explain to me what is leading to this specific error?

where do you create threads? Show me your main method where you create and start threads? — Ravindra Ranwala, Mar 16 '18 at 14:07
"Can anyone explain to me what is leading to this error" - yes, you're using the type in a way which the documentation tells you not to. You shouldn't be surprised when bad stuff happens at that point. — Jon Skeet, Mar 16 '18 at 14:07
You've declared your List as static, so the list is common to every instances of class A. So all your threads access it at the same time. So it crashes — vincrichaud, Mar 16 '18 at 14:11
@vincrichaud I know its not thread safe but I thought it will give wrong answer like size will be lesser than that, But Why this error — RaM PrabU, Mar 16 '18 at 14:13
that's *mainly* because `add` will do a resize internally when data can not fit into the already in place array, so one thread tries to increase that array, while another tries to put into it (where index does not exist) — Eugene, Mar 16 '18 at 14:14
@RaMPrabU So your question is "I know I will have an error but I was expecting just wrong answers not ArrayIndexOutOfBoundsException, why this exception ?" Currently it's unclear what you're asking — vincrichaud, Mar 16 '18 at 14:16
"I know its not thread safe but I thought it will give wrong answer like size will be lesser than that" - which bit of the documentation gave you that impression? — Jon Skeet, Mar 16 '18 at 14:16
@JonSkeet why not understanding those details of why *potentially* it could fail? I don't get it, that's a good question/research to me (not more), especially since the OP said he understands that this will fail — Eugene, Mar 16 '18 at 14:17
I think vincrichaud get's the point. All threads accesses the same list object (since it is static) and parallel adds must fall ... sooner or later. If your are apending a element while another element is appended in another thread, your list is broken at some point. — Flocke, Mar 16 '18 at 14:20
I edited the question to make it clear and in accordance with Eran answer — vincrichaud, Mar 16 '18 at 14:33
@Eugene: I think it could have been written as a reasonable question, and it's better now than it was, but it does still come off as "I'm going to assume that unspecified behavior will take form X, but it takes form Y. Why is my unwarranted assumption unwarranted?" — Jon Skeet, Mar 16 '18 at 15:38

score 9 · Answer 1 · answered Mar 16 '18 at 14:15

Well, you are using a non thread-safe collection in a multi threaded environment without any synchronization.

Let's examine the add method, where you get the exception:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

When multiple threads call this method at the same time, it is quite possible that ensureCapacityInternal(size + 1) verifies there is enough space for 1 new element, but then multiple threads try to add an element at the same time, so elementData[size++] throws ArrayIndexOutOfBoundsException for some of them.

+1 this is entirely correct, just add that this is the least potential surprise that might happen, there are many more, much worse, like stale data, incomplete ArrayList, etc — Eugene, Mar 16 '18 at 14:21

Andrew Tobilko · Accepted Answer · 2018-03-19T09:39:59.977

ArrayList is not a thread-safe class.

Underlying storage for elements is Object[] which is an array. Any array requires the allocation space in memory which is predefined in the compile time. However, when an ArrayList "wants" to add the new element (beyond the underlying array bound), several things have to be done (without your knowledge). Underlying array gets a new (increased) length. Every element of the old array is copied to the new array, and then the new element is added. So, you can expect the ArrayIndexOutOfBoundsException exception when an ArrayList is used in multi-thread environment.

You are adding elements too fast so ArrayList#add() -> grow() -> newCapacity() can't calculate the correct capacity to allocate the memory for all of the elements coming in.

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

At some point of time, the condition s == elementData.length inside ArrayList#add says that there is a space for a new element A. Immediately after that other threads put their elements into the list. Now there is no space for A and elementData[s] = e; throws an exception.

Multi Threading with ArrayList() got ArrayIndexOutOfBoundsException

2 Answers2