“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

This article was picked up by Java Advancements.

Hello, I’m looking at the mountains.

We all know that ArrayList in Java is non-thread-safe, so familiar that we rarely even ask about it in job interviews.

But do we really know how it works? Or what happens when you use an ArrayList with multiple threads?

Some time ago, we stepped on the pit, and directly stepped on two pits, today to pick a pick.

Cui hua, on the source code

Let’s start with the add logic for ArrayList:

  1. Check whether the array in the queue has not yet been added
  2. If yes, set the required length to 10. If no, set the required length to the current queue length +1
  3. Determine if the required length is greater than the array size
  4. If yes, expand the array size by 1.5 times (the first expansion will be from 0 to 10, and the subsequent growth will be 1.5 times).
  5. Add elements to array, queue length +1

Attached code, interested in can look at the source.

/**
 * 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) {
    // Determine whether the array size is sufficient, if not, increase the size by 1.5 times, size is the current queue length
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // assign the subscript size to the queue length +1, starting at 0
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // Determine whether the element was added for the first time, if so, return the default queue length, which is now 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    If the element is not added for the first time, the current queue length +1 is returned
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // If the required length is greater than the array length in the queue, expand the capacity
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // Here is the code for the 1.5-fold expansion
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

It’s just not safe

As you can see from the above code, none of the elements in the ArrayList have the slightest consideration for multithreading; complete efficiency takes precedence.

Strange ArrayIndexOutOfBoundsException

Let’s assume that the size of the array has reached the critical edge, for example, the current size is 10, and now there are 9 elements in the array, i.e. size=9, and then two threads add elements to the queue simultaneously:

  1. Thread 1 starts to enteraddMethod, get size=9, callensureCapacityInternalMethod to determine the capacity, the array capacity is 10, do not need to expand
  2. Thread 2 also entersaddMethod, get size=9, callensureCapacityInternalMethod to determine the capacity, the array capacity is still 10, and there is no need to expand
  3. Thread 1 starts assigning values, which iselementData[size++] = e, size becomes 10, reaching the array capacity limit
  4. Thread 2 starts the assignment using size=10, i.eelementData[10] = eBecause the subscript starts at 0, the current array capacity is 10ArrayIndexOutOfBoundsException.

By one step, thread 2 becomes the exception throwing killer. But it’s good to throw an exception, because we know something went wrong and we can follow the exception

Spooky null elements

ElementData [size++] = e does two steps: elementData[size++] = e

elementData[size] = e;
size++;
Copy the code

Let’s say there are still two threads to assign, and the array size is relatively large. For example, if the array size is 10, size=5:

  1. Thread 1 starts to enteraddMethod, get size=5, callensureCapacityInternalMethod to determine the capacity, the array capacity is 10, do not need to expand
  2. Thread 2 also entersaddMethod, get size=5, callensureCapacityInternalMethod to determine the capacity, the array capacity is still 10, and there is no need to expand
  3. Thread 1 starts the assignment and executeselementData[size] = eAt this time, size=5, the executionsize++Earlier, thread 2 started assigning
  4. Thread 2 starts the assignment and executeselementData[size] = e, so thread 2 overwrites the value assigned by thread 1
  5. Thread 1 starts executionsize++And the size = 6
  6. Thread 2 starts executionsize++And the size = 7

That is, two elements are added, the queue length is +2, but only one element is actually added to the queue, and one element is overwritten.

This situation will not immediately report the error, the investigation is very troublesome. And with the popularity of JDK 8, it is possible to use filters to filter empty elements, so that errors are not immediately detected until a business exception occurs, by which time the error scene has disappeared and the investigation is confusing.

ElementData [size++] = e; elementData[size++] = e It all starts with JVM bytecode.

The second exception occurs through JVM bytecode

Let’s start with some simple code:

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[3];
        int index = 0;
        nums[index++] = 5; }}Copy the code

Java and javap -v -l main. class to obtain the bytecode:

The remarks below are the ones I added later. The remarks also list the changes of local variable scale and stack value, so you need to be patient.

public class Main minor version: 0 major version: 52 flags: ACC_PUBLIC, ACC_SUPER Constant pool: #1 = Methodref #3.#12 // java/lang/Object."<init>":()V #2 = Class #13 // Main #3 = Class #14 // java/lang/Object #4 = Utf8 <init> #5 = Utf8 ()V #6 = Utf8 Code #7 = Utf8 LineNumberTable #8 = Utf8 main #9 = Utf8 ([Ljava/lang/String; )V #10 = Utf8 SourceFile #11 = Utf8 Main.java #12 = NameAndType #4:#5 // "<init>":()V #13 = Utf8 Main #14 = Utf8 java/lang/Object { public Main(); descriptor: ()V flags: ACC_PUBLIC Code: stack=1, locals=1, args_size=1 0: aload_0 1: invokespecial #1 // Method java/lang/Object."<init>":()V 4: return LineNumberTable: line 1: 0 public static void main(java.lang.String[]); descriptor: ([Ljava/lang/String;)V flags: ACC_PUBLIC, ACC_STATIC Code: Stack 0: iconst_3 // Push int (3) to the top of the stack args 3 1: Newarray int // Creates an array with a primitive type (such as int, float, char...) and pushes its reference value to the top of the stack. // push int (0) to args, nums= array reference null 4: iconst_0 Int args, nums= array reference, index=0 null 6: Aload_1 // Push the second reference type local variable to the top of the stack args, nums= array reference, index=0 array reference 7: Args, nums= array reference, index=0 0, array reference 8: Args, nums= array reference, index=1 0, array reference 11; Args, nums= array reference, index=1 5, 0, array reference 12: Args, nums= array reference, index=1 null 13: return void LineNumberTable: line 3: 0 // int[] nums = new int[3]; line 4: 4 // int index = 0; line 5: 6 // nums[] ++] = 5;Copy the code

As you can see from the bytecode above, nums[index++] = 5 is converted to 5 instructions, from 6 to 12. The general operation is as follows:

  1. Push arrays and subscripts onto the stack
  2. Append subscripts
  3. Push the new value onto the stack
  4. Take the top three elements of the stack and start assigning subscripts to the elements

The error occurs when an array assignment is performed by pushing both the array reference and the subscript onto the top of the stack at the same time, which is two steps from the subscript assignment.

solution

The solution is simply to be aware of a multithreaded environment and not use an ArrayList. Can use Collections. SynchronizedList () returns the synchronous queue, can also use the CopyOnWriteArrayList this queue, or extend ArrayList, the add method converts into the form of a synchronization method.

At the end of the article to summarize

The operations of the entire ArrayList class are non-thread-safe, which can cause problems when used in a multithreaded environment. As mentioned above, the add operation can have two kinds of exception behavior, one is the array out of bounds exception, and the other is the loss and null value. This is just the simplest add operation, but when add, addAll, and GET are used together, there are more exceptions. Therefore, pay attention to whether the operation is single thread. If not, use other queues for lightning protection.

Recommended reading

  • There are anti-pattern interface constants in the JDK
  • What do we need to pay attention to when Java Import imports packages?
  • Java Concurrency Basics (1) : Synchronized
  • Java Concurrency Basics (2) : The main thread waits for the child thread to terminate
  • Java Concurrency basics (iii) : Talk more about CountDownLatch
  • Java Concurrency Basics (4) : CyclicBarrier
  • Java concurrency basics (5) : multithreaded sequential printing for interview practice
  • What happens if you have to use an ArrayList in multiple threads?
  • Rediscover queues in Java
  • Java difference between Vector and SynchronizedList
  • What happens if you have to use an ArrayList in multiple threads? (Chapter 2)
  • This article describes 24 operations for Java8 Stream Collectors
  • Java8 Optional 6 kinds of operations

Hello, I’m looking at the mountains. Swim in the code, play to enjoy life. If this article is helpful to you, please like, bookmark, follow. Welcome to follow the public account “Mountain Hut”, discover a different world.