<div dir="ltr"><div>Thanks for your response. Sure, maybe it doesn't really matter because it is about micro-optimization. The code is correct in any case.</div><div><br></div><div>However, as I see it the else part could be executed for the following two cases which currently does not:</div><div>1. If the ArrayList is initialized as empty and the shared EMPTY_ELEMENTDATA is used.</div><div>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).</div><div><br></div><div>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.</div><div>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.</div><div><br></div><div>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)".</div><div><br></div><div>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.</div><div><br></div><div>Best regards,</div><div>Periklis<br></div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jul 11, 2022 at 1:31 AM Bernd Eckenfels <<a href="mailto:ecki@zusammenkunft.net">ecki@zusammenkunft.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">
<div></div>
<div>
<div dir="ltr">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.</div>
<div id="gmail-m_641894257871622026ms-outlook-mobile-signature">
<div><br>
</div>
<div><br>
</div>
<div style="direction:ltr">-- </div>
<div style="direction:ltr"><a href="http://bernd.eckenfels.net" target="_blank">http://bernd.eckenfels.net</a></div>
</div>
</div>
</div>
<hr style="display:inline-block;width:98%">
<div id="gmail-m_641894257871622026divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>Von:</b> core-libs-dev <<a href="mailto:core-libs-dev-retn@openjdk.org" target="_blank">core-libs-dev-retn@openjdk.org</a>> im Auftrag von Periklis Ntanasis <<a href="mailto:pntanasis@gmail.com" target="_blank">pntanasis@gmail.com</a>><br>
<b>Gesendet:</b> Monday, July 11, 2022 12:20:27 AM<br>
<b>An:</b> <a href="mailto:core-libs-dev@openjdk.org" target="_blank">core-libs-dev@openjdk.org</a> <<a href="mailto:core-libs-dev@openjdk.org" target="_blank">core-libs-dev@openjdk.org</a>><br>
<b>Betreff:</b> ArrayList grow method optimization and documentation improvement</font>
<div> </div>
</div>
<div>
<div dir="ltr">Hi all,<br>
<br>
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.<br>
<br>
Currently the method looks like this (<a href="https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L224-L241" target="_blank">https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L224-L241</a>):<br>
<br>
/**<br>
* Increases the capacity to ensure that it can hold at least the<br>
* number of elements specified by the minimum capacity argument.<br>
*<br>
* @param minCapacity the desired minimum capacity<br>
* @throws OutOfMemoryError if minCapacity is less than zero<br>
*/<br>
private Object[] grow(int minCapacity) {<br>
int oldCapacity = elementData.length;<br>
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {<br>
int newCapacity = ArraysSupport.newLength(oldCapacity,<br>
minCapacity - oldCapacity, /* minimum growth */<br>
oldCapacity >> 1 /* preferred growth */);<br>
return elementData = Arrays.copyOf(elementData, newCapacity);<br>
} else {<br>
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];<br>
}<br>
}<br>
<br>
<div>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.</div>
<div>Simply an empty array which ensures the requested minCapacity is created.<br>
</div>
<br>
The problem lies with the if condition "if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)".<br>
This is going to be executed for any elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA regardless of the oldCapacity value.<br>
<br>
<div>So, I believe that the original intention was the else part to also include cases where the oldCapacity is zero.</div>
<div>This means that the condition should use && instead of || and be written like that:<br>
</div>
<br>
if (oldCapacity > 0 && elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {<br>
<br>
What do you think? Does this make sense?<br>
<br>
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.<br>
<br>
It says that the OutOfMemoryError will be thrown "if minCapacity is less than zero".<br>
However, this seems true only before 218204b1a330 (<a href="https://github.com/openjdk/jdk/commit/218204b1a330" target="_blank">https://github.com/openjdk/jdk/commit/218204b1a330</a>) which performed this change, with the previous implementation (<a href="https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L261-L262" target="_blank">https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L261-L262</a>
and <a href="https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L271-L272" target="_blank">
https://github.com/openjdk/jdk/blob/9ffe7e1205ea42ffccc9622b3e1c5436cc9898f5/src/java.base/share/classes/java/util/ArrayList.java#L271-L272</a>).<br>
<br>
<div>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.</div>
<div>However, the condition for the appearance of the error seems not to be exactly the one described in the comment.<br>
</div>
<br>
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.<br>
<br>
Thank you,<br>
Periklis</div>
</div>
</div>
</blockquote></div>