ArrayList grow method optimization and documentation improvement

[Periklis Ntanasis]

Thanks for your response. Sure, maybe it doesn't really matter because it
is about micro-optimization. The code is correct in any case.

However, as I see it the else part could be executed for the following two
cases which currently does not:
1. If the ArrayList is initialized as empty and the shared
EMPTY_ELEMENTDATA is used.
2. If the current capacity of the elementData is zero because of removals
(actually in that case if trimToSize() is used again elementData points to
EMPTY_ELEMENTDATA).

So, I agree that it is not really important but if for some reason the
optimization was originally placed there I would expect it to work for all
the cases where the optimization may be performed.
Currently, the "if (oldCapacity > 0 || elementData !=
DEFAULTCAPACITY_EMPTY_ELEMENTDATA)" is equivalent to "if (elementData !=
DEFAULTCAPACITY_EMPTY_ELEMENTDATA)" (DEFAULTCAPACITY_EMPTY_ELEMENTDATA has
always oldCapacity equals to zero) which seems weird to me.

By the way for the same reason my previous suggestion to change it to "if
(oldCapacity > 0 && elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)" is
actually equivalent to "if (oldCapacity > 0)".

Anyway, maybe I am missing something but this seemed strange to me and I
wanted to bring it to the attention of the mailing list. Feel free to
ignore my comment in case you think that it isn't worth the effort.

Best regards,
Periklis



On Mon, Jul 11, 2022 at 1:31 AM Bernd Eckenfels <ecki at zusammenkunft.net>
wrote:

> 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/20220711/4af35cc8/attachment-0001.htm>