Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
On Tue, Jan 26, 2016 at 5:44 AM, Jason Mehrenswrote: > Hi Martin, > > Are you sure about the change where addElement is now calling the public > (non-final) version of add? I would think that we would want to avoid any > type of compatibility changes with regard to Vector. Jason, you are right that we shouldn't be changing observable calls to public methods.
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
webrev refreshed - http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Vector-grow/ On Tue, Jan 26, 2016 at 4:28 AM, Remi Foraxwrote: > Hi Martin, > sorry for jumping on this conversation lately, > please don't be seduced by the dark side, Too late! I've already committed such changes to ArrayList.java. No one would do this sort of bytecode golf if it didn't have measurable effects on microbenchmarks. We've been asking hotspot maintainers to kill their method-bytecode-size heuristics for a long time, but still no sign of it happening. > I understand that the code is 1 byte bigger, but i think that the following > code > final int s = this.size; > Object[] elementData = this.elementData; > if (s == elementData.length) { > elementData = grow(); > } > > is more readable than > final int s; > Object[] elementData; > if ((s = size) == (elementData = this.elementData).length) > elementData = grow(); Vector.insertElementAt is not performance critical, and not near MaxInlineSize, so I did as you ask. In core libraries readability is slightly less important than performance.
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
On 1/26/16 4:28 AM, Remi Forax wrote: please don't be seduced by the dark side, Clearly, he feels the call from light. :-) On 1/26/16 10:25 AM, Martin Buchholz wrote: webrev refreshed - http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Vector-grow/ Hi Martin, Thanks for the updates. Looks like Jason and Remi already looked at it, but in case you were waiting for me, I looked at it too. Looks fine. In core libraries readability is slightly less important than performance. For some values of "slightly." :-) s'marks
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
Hi Martin, sorry for jumping on this conversation lately, please don't be seduced by the dark side, I understand that the code is 1 byte bigger, but i think that the following code final int s = this.size; Object[] elementData = this.elementData; if (s == elementData.length) { elementData = grow(); } is more readable than final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow(); cheers, Rémi - Mail original - > De: "Martin Buchholz" <marti...@google.com> > À: "Stuart Marks" <stuart.ma...@oracle.com> > Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net> > Envoyé: Mardi 26 Janvier 2016 01:49:41 > Objet: Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int) > > I already regret touching crufty old Vector, but it had the same bug > to fix, and more surprisingly the same sort of performance improvement > from doing the obvious port. So ... Stuart, please review also > > http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Vector-grow/ > https://bugs.openjdk.java.net/browse/JDK-8148174 > > > On Fri, Jan 22, 2016 at 2:30 PM, Stuart Marks <stuart.ma...@oracle.com> > wrote: > > > > > > On 1/22/16 12:02 PM, Martin Buchholz wrote: > >> > >> I went "by the book" as you suggested and now throw > >> InvalidObjectException when size < 0. > >> (But I've been saying for a decade: if we're serious about > >> Serialization, it needs to be someone's full time job) > > > > > > "Admiral, if we go by the book, years could turn into decades." > > > > Thanks for the update; this looks great to me. > > > > s'marks >
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
I already regret touching crufty old Vector, but it had the same bug to fix, and more surprisingly the same sort of performance improvement from doing the obvious port. So ... Stuart, please review also http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Vector-grow/ https://bugs.openjdk.java.net/browse/JDK-8148174 On Fri, Jan 22, 2016 at 2:30 PM, Stuart Markswrote: > > > On 1/22/16 12:02 PM, Martin Buchholz wrote: >> >> I went "by the book" as you suggested and now throw >> InvalidObjectException when size < 0. >> (But I've been saying for a decade: if we're serious about >> Serialization, it needs to be someone's full time job) > > > "Admiral, if we go by the book, years could turn into decades." > > Thanks for the update; this looks great to me. > > s'marks
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
On Fri, Jan 22, 2016 at 10:03 AM, Stuart Markswrote: > On readObject(), ok, you went ahead and rearranged some stuff. You hit a > couple of the issues I had spotted, namely the multiple assignment to > elementData and the potentially confusing reuse of the name 'elementData'. > > The other issue was if size is less than zero. This could only occur with a > corrupted or tampered serialized data stream. The old code would > "successfully" deserialize a dysfunctional ArrayList instance, whereas the > modified code will throw NegativeArraySizeException from readObject(). > > I don't know if that was intentional, but I prefer the new behavior! > > Strictly speaking I think throwing InvalidObjectException would preferable, > but if you want to push what you have, I'm ok with it. I went "by the book" as you suggested and now throw InvalidObjectException when size < 0. (But I've been saying for a decade: if we're serious about Serialization, it needs to be someone's full time job) I'll commit tomorrow if I don't hear otherwise.
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
Hi Martin, Thanks for adding the comments and @ignore. On readObject(), ok, you went ahead and rearranged some stuff. You hit a couple of the issues I had spotted, namely the multiple assignment to elementData and the potentially confusing reuse of the name 'elementData'. The other issue was if size is less than zero. This could only occur with a corrupted or tampered serialized data stream. The old code would "successfully" deserialize a dysfunctional ArrayList instance, whereas the modified code will throw NegativeArraySizeException from readObject(). I don't know if that was intentional, but I prefer the new behavior! Strictly speaking I think throwing InvalidObjectException would preferable, but if you want to push what you have, I'm ok with it. s'marks On 1/21/16 6:58 PM, Martin Buchholz wrote: We have a new webrev. Bug8146568.java now uses @ignore. readObject has a minor rewrite, only assigning to elementData once. (Yes, we can talk more about future improvements to ArrayList) (maybe MAX_ARRAY_SIZE could have a better name ...) We have some hopefully clearer internal comments: /** * The maximum size of array to allocate (unless necessary). * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 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) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } private Object[] grow() { return grow(size + 1); } /** * Returns a capacity at least as large as the given minimum capacity. * Returns the current capacity increased by 50% if that suffices. * Will not return a capacity greater than MAX_ARRAY_SIZE unless * the given minimum capacity is greater than MAX_ARRAY_SIZE. * * @param minCapacity the desired minimum capacity * @throws OutOfMemoryError if minCapacity is less than zero */ private int newCapacity(int minCapacity) { On Thu, Jan 21, 2016 at 2:36 PM, Stuart Markswrote: On 1/21/16 1:57 PM, Martin Buchholz wrote: One is that in list.addAll(other), the sizes of list and other exceeds Integer.MAX_VALUE, then grow(int) will be called with a negative value for minCapacity. The code *seems* to handle this ok, but the negative minCapacity value can get pretty deeply into the helper methods before being caught. Would it be better to check it at the top of grow(int) and throw an exception there? (Probably OOME.) I think it would make the subsequent code easier to follow. It's true that the code is rather tricky, "overflow-conscious code". But this is ArrayList, so it seems worth optimizing even for grow. The common case is that we grow by 50% and then if (newCapacity - MAX_ARRAY_SIZE <= 0) we can be sure that newCapacity is not negative. The code may be correct, but I'm concerned about maintenance. If things shift around, it might be easy to miss the possibility that negative minCapacity could be passed to grow() if overflow had occurred. So perhaps at least a comment would be warranted. It looks like there are a variety of ways for minCapacity that is positive but greater than MAX_ARRAY_SIZE to reach newCapacity(). If this occurs, and other conditions are right, it looks like the code will end up attempting to allocate an array greater than MAX_ARRAY_SIZE. If grow(n) is called with MAX_ARRAY_SIZE < n <= MAX_VALUE, then we no choice but to allocate an array of that size! It's only when we use the grow-by-50% strategy that we can change our minds by scaling back. I don't see a bug. Ah, MAX_ARRAY_SIZE applies only to grow-by-50%, not to all array allocations. Perhaps it was my mistake for having believed its comment, which is The maximum size of array to allocate. You know what they say about comments not matching the code :-) I do think this comment needs to be adjusted to say that MAX_ARRAY_SIZE applies only to the 50% growth policy. I was certainly misled by it. One style point I noticed (which might be an issue of me not being used to it) is the use of an elementData local variable to shadow the elementData field. This is more-or-less ok in places where elementData is initialized from this.elementData, but in readObject(), the local elementData is introduced in a nested scope. This means that elementData has different meanings in different parts of the method. Yeah, elementData is not great but I couldn't find anything better. "a" is
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
PIng. How about Alan, Chris, Xueming ? On Tue, Jan 19, 2016 at 9:24 AM, Martin Buchholzwrote: > Hi Stuart et al, > Please review my fix for this corner case bug, including more > importantly some performance improvements. > > https://bugs.openjdk.java.net/browse/JDK-8146568 > http://cr.openjdk.java.net/~martin/webrevs/openjdk9/ArrayList-grow/
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
Hi Martin, Thanks for digging into this. There are some subtle issues here. I have a few questions. One is that in list.addAll(other), the sizes of list and other exceeds Integer.MAX_VALUE, then grow(int) will be called with a negative value for minCapacity. The code *seems* to handle this ok, but the negative minCapacity value can get pretty deeply into the helper methods before being caught. Would it be better to check it at the top of grow(int) and throw an exception there? (Probably OOME.) I think it would make the subsequent code easier to follow. It looks like there are a variety of ways for minCapacity that is positive but greater than MAX_ARRAY_SIZE to reach newCapacity(). If this occurs, and other conditions are right, it looks like the code will end up attempting to allocate an array greater than MAX_ARRAY_SIZE. One style point I noticed (which might be an issue of me not being used to it) is the use of an elementData local variable to shadow the elementData field. This is more-or-less ok in places where elementData is initialized from this.elementData, but in readObject(), the local elementData is introduced in a nested scope. This means that elementData has different meanings in different parts of the method. For the test Bug8146568 I think the preferred way to disable a test with extreme memory requirements is to use @ignore; see jdk/test/java/math/BigInteger/SymmetricRangeTests.java for example. s'marks On 1/21/16 8:38 AM, Martin Buchholz wrote: PIng. How about Alan, Chris, Xueming ? On Tue, Jan 19, 2016 at 9:24 AM, Martin Buchholzwrote: Hi Stuart et al, Please review my fix for this corner case bug, including more importantly some performance improvements. https://bugs.openjdk.java.net/browse/JDK-8146568 http://cr.openjdk.java.net/~martin/webrevs/openjdk9/ArrayList-grow/
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
On Thu, Jan 21, 2016 at 11:39 AM, Stuart Markswrote: > Hi Martin, > > Thanks for digging into this. There are some subtle issues here. I have a > few questions. > > One is that in list.addAll(other), the sizes of list and other exceeds > Integer.MAX_VALUE, then grow(int) will be called with a negative value for > minCapacity. The code *seems* to handle this ok, but the negative > minCapacity value can get pretty deeply into the helper methods before being > caught. Would it be better to check it at the top of grow(int) and throw an > exception there? (Probably OOME.) I think it would make the subsequent code > easier to follow. It's true that the code is rather tricky, "overflow-conscious code". But this is ArrayList, so it seems worth optimizing even for grow. The common case is that we grow by 50% and then if (newCapacity - MAX_ARRAY_SIZE <= 0) we can be sure that newCapacity is not negative. > It looks like there are a variety of ways for minCapacity that is positive > but greater than MAX_ARRAY_SIZE to reach newCapacity(). If this occurs, and > other conditions are right, it looks like the code will end up attempting to > allocate an array greater than MAX_ARRAY_SIZE. If grow(n) is called with MAX_ARRAY_SIZE < n <= MAX_VALUE, then we no choice but to allocate an array of that size! It's only when we use the grow-by-50% strategy that we can change our minds by scaling back. I don't see a bug. > One style point I noticed (which might be an issue of me not being used to > it) is the use of an elementData local variable to shadow the elementData > field. This is more-or-less ok in places where elementData is initialized > from this.elementData, but in readObject(), the local elementData is > introduced in a nested scope. This means that elementData has different > meanings in different parts of the method. Yeah, elementData is not great but I couldn't find anything better. "a" is already taken. "snapshot" has the wrong connotations. If you prefer e.g. "elements" I will change it throughout, but in either case a reader needs to understand that "elements" and "elementData" are "almost" the same. > For the test Bug8146568 I think the preferred way to disable a test with > extreme memory requirements is to use @ignore; see I've never liked @ignore in practice, because jtreg is very noisy unless you also say -ignore:quiet (which I always do, but does everyone else?)
Re: RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
We have a new webrev. Bug8146568.java now uses @ignore. readObject has a minor rewrite, only assigning to elementData once. (Yes, we can talk more about future improvements to ArrayList) (maybe MAX_ARRAY_SIZE could have a better name ...) We have some hopefully clearer internal comments: /** * The maximum size of array to allocate (unless necessary). * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 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) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } private Object[] grow() { return grow(size + 1); } /** * Returns a capacity at least as large as the given minimum capacity. * Returns the current capacity increased by 50% if that suffices. * Will not return a capacity greater than MAX_ARRAY_SIZE unless * the given minimum capacity is greater than MAX_ARRAY_SIZE. * * @param minCapacity the desired minimum capacity * @throws OutOfMemoryError if minCapacity is less than zero */ private int newCapacity(int minCapacity) { On Thu, Jan 21, 2016 at 2:36 PM, Stuart Markswrote: > > > On 1/21/16 1:57 PM, Martin Buchholz wrote: >>> >>> One is that in list.addAll(other), the sizes of list and other exceeds >>> Integer.MAX_VALUE, then grow(int) will be called with a negative value >>> for >>> minCapacity. The code *seems* to handle this ok, but the negative >>> minCapacity value can get pretty deeply into the helper methods before >>> being >>> caught. Would it be better to check it at the top of grow(int) and throw >>> an >>> exception there? (Probably OOME.) I think it would make the subsequent >>> code >>> easier to follow. >> >> >> It's true that the code is rather tricky, "overflow-conscious code". >> But this is ArrayList, so it seems worth optimizing even for grow. >> >> The common case is that we grow by 50% and then if (newCapacity - >> MAX_ARRAY_SIZE <= 0) we can be sure that newCapacity is not negative. > > > The code may be correct, but I'm concerned about maintenance. If things > shift around, it might be easy to miss the possibility that negative > minCapacity could be passed to grow() if overflow had occurred. So perhaps > at least a comment would be warranted. > >>> It looks like there are a variety of ways for minCapacity that is >>> positive >>> but greater than MAX_ARRAY_SIZE to reach newCapacity(). If this occurs, >>> and >>> other conditions are right, it looks like the code will end up attempting >>> to >>> allocate an array greater than MAX_ARRAY_SIZE. >> >> >> If grow(n) is called with MAX_ARRAY_SIZE < n <= MAX_VALUE, then we no >> choice but to allocate an array of that size! It's only when we use >> the grow-by-50% strategy that we can change our minds by scaling back. >> I don't see a bug. > > > Ah, MAX_ARRAY_SIZE applies only to grow-by-50%, not to all array > allocations. Perhaps it was my mistake for having believed its comment, > which is > > The maximum size of array to allocate. > > You know what they say about comments not matching the code :-) > > I do think this comment needs to be adjusted to say that MAX_ARRAY_SIZE > applies only to the 50% growth policy. I was certainly misled by it. > >>> One style point I noticed (which might be an issue of me not being used >>> to >>> it) is the use of an elementData local variable to shadow the elementData >>> field. This is more-or-less ok in places where elementData is initialized >>> from this.elementData, but in readObject(), the local elementData is >>> introduced in a nested scope. This means that elementData has different >>> meanings in different parts of the method. >> >> >> Yeah, elementData is not great but I couldn't find anything better. >> "a" is already taken. "snapshot" has the wrong connotations. If you >> prefer e.g. "elements" I will change it throughout, but in either case >> a reader needs to understand that "elements" and "elementData" are >> "almost" the same. > > > I don't think a global change is necessary, as the prevailing style in this > file is to use the elementData field or to have a local elementData that's > an alias of the field. I think readObject() is the outlier for using both > the field and the local variable. But there are several other funny things > going on here in readObject()... well I won't insist that you address them > right now, as they're a distraction from this bugfix. So the change
RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)
Hi Stuart et al, Please review my fix for this corner case bug, including more importantly some performance improvements. https://bugs.openjdk.java.net/browse/JDK-8146568 http://cr.openjdk.java.net/~martin/webrevs/openjdk9/ArrayList-grow/