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.st...@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_she...@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: marti...@google.com
>> > To: kevin.l.st...@gmail.com; christopher.hega...@sun.com;
>> alan.bate...@sun.com
>> > CC: core-libs-dev@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>
>>
>
>
