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

[Kevin L. Stern]

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/d8bc59bf/attachment.html>