Collection size expansion logic refactor in Java 18

In Java 18, the array expansion code has huge change compared to Java 8. For Java 18 ArrayList and PriorityQueue, their array expansion calls ArraysSupport.newLength().

ArrayList

We only discuss the scenario of appending 1 element.

Let’s take a look of what inside the ArrayList.

// This is ArrayList's the simplest adding function, which aims to append the element
public boolean add(E e) {
    // 1. The default user interface modifies modCount directly.
    //    Java 8 did it in ensureCapacityInternal().
    modCount++;
    // 2. elementData is the internal Object[] array that wrapped and maintained by ArrayList
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    // 3. s == internal array's length means that the internal array full
    if (s == elementData.length)
        // 4. Internal array will be changed to a new array with bigger capacity
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

The main responsibility of grow() is to expand the size of internal array elementData.

// When the outside wants to append 1 element, the grow() helper method will set the minCapacity = 1
private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 4. Test if the internal array is empty array
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 4.1 If not empty array, calculate a new capacity using ArraysSupport.newLength()
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 4.2 If internal array is empty, in our case grow(size + 1), it will be given a DEFAULT_CAPACITY = 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

Compared to Java 8, Java 18 removed ensureCapacityInternal(), ensureExplicitCapacity() and let grow() to undertake more responsibility. Previously ensureCapacityInternal() is responsible for testing elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA while ensureExplicitCapacity() is responsible for some task of ArraysSupport.newLength().

Let’s take a look of what inside ArraysSupport.

// A soft maximum array length imposed by array growth computations.
// Some JVMs (such as HotSpot) have an implementation limit that will cause OutOfMemoryError("Requested array size exceeds VM limit")
public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

// 5. ArraysSupport.newLength() is responsible for calculate a new length.
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // 5.1 From our case, minGrowth = minCapacity - oldCapacity = size + 1 - size = 1
    //                    max(minGrowth, prefGrowth) = max(1, 1/2 * size) = size / 2
    //     So the prefLength = 3/2 * size
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    // 5.2 If 3/2 * size < SOFT_MAX => size < 2/3 * SOFT_MAX, return the prefLength
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        return hugeLength(oldLength, minGrowth);
    }
}

// In our general appending case, minGrowth = 1
private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError(
            "Required array length " + oldLength + " + " + minGrowth + " is too large");
    // 5.3 If size + 1 <= SOFT_MAX => size <= SOFT_MAX - 1, return SOFT_MAX
    } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
        return SOFT_MAX_ARRAY_LENGTH;
    } else {
        // 5.4 If size > SOFT_MAX - 1, return 1
        return minLength;
    }
}

Java 18 considered the limitation of special Hotspot JVM by setting a SOFT_MAX to Integer.MAX_VALUE - 8 rather than directly expand the internal array to Integer.MAX_VALUE.

The whole internal array size growing during appending element one by one is clear:

1. When 1 < size < 2/3 * SOFT_MAX, the elementData will add 1/2 size
2. When 2/3 * SOFT_MAX < size <= SOFT_MAX - 1, adding 1/2 * SOFT_MAX may cause the whole elementData.length > Integer.MAX_VALUE. So it extends elementData to SOFT_MAX directly.
3. When SOFT_MAX - 1 < size, just keep growing 1.
   • In most common case, we don’t store the Integer.MAX_VALUE amount of elements into one ArrayList
   • This growing 1 operation may aim to delay the application crash.

PriorityQueue

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                       /* preferred growth */);
    queue = Arrays.copyOf(queue, newCapacity);
}

The only difference of grow() strategy between PriorityQueue and ArrayList is the preferred growth. ArrayList prefers expand half of its current capacity while PriorityQueue prefers only grow 2 when less than 64 and grow half when big than 64.