ArrayList grow method optimization and documentation improvement

[Bernd Eckenfels]

I think it means for the zero case it should not use the else part if it has not the default sizing, since somebody might have created it with a specific size. Not sure if it matters much either way.


--
http://bernd.eckenfels.net
________________________________
Von: core-libs-dev <core-libs-dev-retn at openjdk.org> im Auftrag von Periklis Ntanasis <pntanasis at gmail.com>
Gesendet: Monday, July 11, 2022 12:20:27 AM
An: core-libs-dev at openjdk.org <core-libs-dev at openjdk.org>
Betreff: ArrayList grow method optimization and documentation improvement

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/20220710/8284c272/attachment.htm>