Bugs in java.util.ArrayList, java.util.Hashtable and java.io.ByteArrayOutputStream

[Kevin L. Stern]

Please excuse me - Martin is saving an 'if' statement in the vast majority
of scenarios since, presumably, the overflow scenario occurs very
infrequently (given that the bug has been in place for quite awhile).

On Tue, Mar 9, 2010 at 5:02 AM, Kevin L. Stern <kevin.l.stern at gmail.com>wrote:

> I did a quick search and it appears that Java is indeed two's complement
> based.  Nonetheless, please allow me to point out that, in general, this
> type of code worries me since I fully expect that at some point someone will
> come along and do exactly what Dmytro suggested; that is, someone will
> change:
>
> if (a - b > 0)
>
> to
>
> if (a > b)
>
> and the entire ship will sink.  I, personally, like to avoid obscurities
> such as making integer overflow an essential basis for my algorithm unless
> there is a good reason to do so.  I would, in general, prefer to avoid
> overflow altogether and to make the overflow scenario more explicit:
>
> if (oldCapacity > RESIZE_OVERFLOW_THRESHOLD) {
>    // do something
> } else {
>   // do something else
> }
>
> Of course, these are simply my coding preferences and I may very well be
> missing the 'good reason' to take the current approach.
>
> Regards,
>
> Kevin
>
>
> On Tue, Mar 9, 2010 at 4:38 AM, Kevin L. Stern <kevin.l.stern at gmail.com>wrote:
>
>> These comparisons are essential to the working of Martin's algorithm.  I
>> found them interesting as well, but notice that when the capacity overflows
>> these comparisons will always be false.  That is to say:
>>
>> oldCapacity < minCapacity (given, otherwise we would not be resizing)
>> therefore oldCapacity + (0.5 for ArrayList, else 1) * oldCapacity -
>> minCapacity < oldCapacity
>>
>> So if oldCapacity + (0.5 for ArrayList, else 1) * oldCapacity >
>> Integer.MAX_VALUE, subtracting minCapacity re-overflows back into the
>> positive number realm.
>>
>> That being said, and this is a question/comment to all, I want to point
>> out that this type of code assumes a particular class of orderly overflow
>> behavior.  Is this specified in the Java spec, or will this break on an
>> obscure machine that does not use, say, two's complement arithmetic?
>>
>> Regards,
>>
>> Kevin
>>
>> 2010/3/9 Dmytro Sheyko <dmytro_sheyko at hotmail.com>
>>
>>  Is there any reason to use comparison like this
>>>
>>> if (newCapacity - minCapacity < 0)
>>>
>>> if (newCapacity - MAX_ARRAY_SIZE > 0) {
>>>
>>> instead of
>>>
>>> if (newCapacity < minCapacity)
>>>
>>> if (newCapacity > MAX_ARRAY_SIZE) {
>>>
>>> Thanks,
>>> Dmytro
>>>
>>> > Date: Mon, 8 Mar 2010 18:10:37 -0800
>>> > Subject: Re: Bugs in java.util.ArrayList, java.util.Hashtable and
>>> java.io.ByteArrayOutputStream
>>> > From: martinrb at google.com
>>> > To: kevin.l.stern at gmail.com; christopher.hegarty at sun.com;
>>> alan.bateman at sun.com
>>> > CC: core-libs-dev at openjdk.java.net
>>>
>>> >
>>> > [Chris or Alan, please review and file a bug]
>>> >
>>> > OK, guys,
>>> >
>>> > Here's a patch:
>>> >
>>> > http://cr.openjdk.java.net/~martin/webrevs/openjdk7/ArrayResize/<http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk7/ArrayResize/>
>>> >
>>> > Martin
>>>
>>>
>>> ------------------------------
>>> Hotmail: Trusted email with powerful SPAM protection. Sign up now.<https://signup.live.com/signup.aspx?id=60969>
>>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100309/e9e3b8a9/attachment.html>