ArrayList grow method optimization and documentation improvement

[Periklis Ntanasis]

Hi all,

I was reading the ArrayList source code and I think that the "private
Object[] grow(int minCapacity)" method does not work as it was intended by
the author.

Currently the method looks like this (
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L224-L241
):

/**
 * 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
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
   int oldCapacity = elementData.length;
   if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
{
     int newCapacity = ArraysSupport.newLength(oldCapacity,
    minCapacity - oldCapacity, /* minimum growth */
    oldCapacity >> 1           /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
  } else {
    return elementData = new Object[Math.max(DEFAULT_CAPACITY,
minCapacity)];
  }
}

As far as I understand, the else part performs an optimization for cases
where there are no elements in elementData to be copied to the new array.
Simply an empty array which ensures the requested minCapacity is created.

The problem lies with the if condition "if (oldCapacity > 0 || elementData
!= DEFAULTCAPACITY_EMPTY_ELEMENTDATA)".
This is going to be executed for any elementData !=
DEFAULTCAPACITY_EMPTY_ELEMENTDATA regardless of the oldCapacity value.

So, I believe that the original intention was the else part to also include
cases where the oldCapacity is zero.
This means that the condition should use && instead of || and be written
like that:

if (oldCapacity > 0 && elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

What do you think? Does this make sense?

While we are at it I would also like to point out that the javadoc comment
regarding the "OutOfMemoryError" seems a bit misleading to me.

It says that the OutOfMemoryError will be thrown "if minCapacity is less
than zero".
However, this seems true only before 218204b1a330 (
https://github.com/openjdk/jdk/commit/218204b1a330) which performed this
change, with the previous implementation (
https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L261-L262
and
https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L271-L272
).

Now, an OutOfMemoryError is still possible. "ArraysSupport.newLength()"
method may throw it "if the new length would exceed Integer.MAX_VALUE".
This may depend implicitly on the "minCapacity" value.
However, the condition for the appearance of the error seems not to be
exactly the one described in the comment.

So, I think the javadoc should be updated to reflect the current situation,
probably by using the same comment which exists in the
"ArraysSupport.newLength()" method.

Thank you,
Periklis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20220711/95ad75f7/attachment-0001.htm>