# I thought that array bounds checking needed two comparisons; however, ...

Discussion in 'Java' started by Casey Hawthorne, Jun 4, 2004.

1. ### Casey HawthorneGuest

I thought that array bounds checking needed two comparisons; however,
I see bounds checking can be done with one comparison:

n - number of array items -- indexed from 0 to n-1

to see if 0 <= i < n do the following comparison

if (i < n) then inbounds;

where '<' is an unsigned '<'

from "Hacker's Delight" Henry S. Warren, Jr. page 51

--
Regards,
Casey

Casey Hawthorne, Jun 4, 2004

2. ### Thomas WeidenfellerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Casey Hawthorne wrote:
> I thought that array bounds checking needed two comparisons; however,
> I see bounds checking can be done with one comparison:
>
> n - number of array items -- indexed from 0 to n-1
>
> to see if 0 <= i < n do the following comparison
>
> if (i < n) then inbounds;
>
> where '<' is an unsigned '<'

Only that there are no unsigned integral types and no corresponding
operators in Java. Better luck next time.

/Thomas

Thomas Weidenfeller, Jun 4, 2004

3. ### Andy FishGuest

"Thomas Weidenfeller" <> wrote in message
news:c9pcoj\$l3s\$...
> Casey Hawthorne wrote:
> > I thought that array bounds checking needed two comparisons; however,
> > I see bounds checking can be done with one comparison:
> >
> > n - number of array items -- indexed from 0 to n-1
> >
> > to see if 0 <= i < n do the following comparison
> >
> > if (i < n) then inbounds;
> >
> > where '<' is an unsigned '<'

>
> Only that there are no unsigned integral types and no corresponding
> operators in Java. Better luck next time.
>

if the bounds of the array are H and L, simply check that

abs (i - ( (H+L)/2) ) <= (H-L)/2

;-))

n.b. I haven't tested it - it might not work for odd numbers or not even
numbers (or not either)

Andy

> /Thomas

Andy Fish, Jun 4, 2004
4. ### Michael BorgwardtGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Thomas Weidenfeller wrote:

> Only that there are no unsigned integral types and no corresponding
> operators in Java. Better luck next time.

Only that array bounds checking is done by the JVM, which is
*not* written in Java.

Michael Borgwardt, Jun 4, 2004
5. ### Thomas WeidenfellerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Michael Borgwardt wrote:
> Only that array bounds checking is done by the JVM, which is
> *not* written in Java.

Congratulations if you never ever had the need to check an index against
an array size in your own code. Oh, you use exceptions exclusively for
that? Ah well, ...

/Thomas

Thomas Weidenfeller, Jun 4, 2004
6. ### Roedy GreenGuest

On Fri, 04 Jun 2004 10:46:21 +0200, Thomas Weidenfeller
<> wrote or quoted :

>Only that there are no unsigned integral types and no corresponding
>operators in Java. Better luck next time.

But that does not mean a JVM cannot use the unsigned compares of the
underlying machine hardware to do the bounds checking.

The bounds checking is neither written in Java nor in byte code. It is
a side effect of various JVM instructions.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green, Jun 4, 2004
7. ### Roedy GreenGuest

On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
<> wrote or quoted :

>if the bounds of the array are H and L, simply check that

In Java L is always 0.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green, Jun 4, 2004
8. ### Michael BorgwardtGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Thomas Weidenfeller wrote:

> Congratulations if you never ever had the need to check an index against
> an array size in your own code. Oh, you use exceptions exclusively for
> that?

Indeed I cannot remember any code where such a condition would not have
resulted from a bug in the code.

Michael Borgwardt, Jun 4, 2004
9. ### Andy FishGuest

"Roedy Green" <> wrote in message
news:...
> On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
> <> wrote or quoted :
>
> >if the bounds of the array are H and L, simply check that

>
> In Java L is always 0.
>

But a good mathematician would never quote a result over a narrower range
than he new it to be true - that would be a waste of maths

> --
> Canadian Mind Products, Roedy Green.
> Coaching, problem solving, economical contract programming.
> See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Andy Fish, Jun 4, 2004
10. ### Roedy GreenGuest

On Fri, 04 Jun 2004 14:19:50 +0200, Thomas Weidenfeller
<> wrote or quoted :

>Congratulations if you never ever had the need to check an index against
>an array size in your own code. Oh, you use exceptions exclusively for
>that? Ah well, ...

In your own code you don't worry about the negative case. If that has
happened, something is REALLY wrong. Overflowing the other way is a
check, for example, that ArrayList does all the time explicitly.

The JVM of course has to worry about the negative case too since it
can't trust the programmer at all. There, it can use an unsigned
machine language compare to effectively pull off the lower and upper
bounds check in one go. Sometimes it might do it with a built in
hardware instruction that does the bounds check.

The important thing to understand is that the bounds checking that
triggers ArrayIndexOutOfBounds exceptions is not written in explicit
Java or byte codes, so it is not subject to those limitations.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green, Jun 4, 2004
11. ### Thomas WeidenfellerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Andy Fish wrote:
> if the bounds of the array are H and L, simply check that
>
> abs (i - ( (H+L)/2) ) <= (H-L)/2
>
> ;-))

Arrays.binarySearch(new int[] {L, H}, i) & 0x80000001

)

/Thomas

Thomas Weidenfeller, Jun 4, 2004
12. ### Andy FishGuest

Re: I thought that array bounds checking needed two comparisons; however, ...

"Michael Borgwardt" <> wrote in message
news:...
> Thomas Weidenfeller wrote:
>
> > Congratulations if you never ever had the need to check an index against
> > an array size in your own code. Oh, you use exceptions exclusively for
> > that?

>
> Indeed I cannot remember any code where such a condition would not have
> resulted from a bug in the code.

I so hate checking array bounds that I always iterate over arrays like this:

for (i=0; ; i++) {
try {
String name = myArray;
...
} catch (ArrayBoundsOutOfIndexException) {
break;
}
}

;-))

Andy Fish, Jun 4, 2004
13. ### Thomas WeidenfellerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Roedy Green wrote:
> In your own code you don't worry about the negative case.

> If that has
> happened, something is REALLY wrong.

Like the user mis-typed some input value? Like some size or offset value
you get in a networking protocol? There are a lot of good reasons to
check array indices for both the upper and lower bound, and provide some
graceful handling, instead of just catching the exception - if at all.

/Thomas

Thomas Weidenfeller, Jun 4, 2004
14. ### Thomas WeidenfellerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Roedy Green wrote:
> But that does not mean a JVM cannot use the unsigned compares of the
> underlying machine hardware to do the bounds checking.

This was not posted to a group about implementing a Java VM. This was
posted to a newsgroup about programming in Java.

The fact that it might be relevant somewhere still doesn't make this
hack relevant to programming in Java.

/Thomas

Thomas Weidenfeller, Jun 4, 2004
15. ### John C. BollingerGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

Andy Fish wrote:

> I so hate checking array bounds that I always iterate over arrays like this:
>
> for (i=0; ; i++) {
> try {
> String name = myArray;
> ...
> } catch (ArrayBoundsOutOfIndexException) {
> break;
> }
> }

Yuck. That violates my principle of not relying on exceptions to drive
program logic. (Yes, it's a fuzzy principle. Don't try to pin me
down.) It also doesn't work if you only want to iterate over part of
the array.

John Bollinger

John C. Bollinger, Jun 4, 2004
16. ### Andy FishGuest

Re: I thought that array bounds checking needed two comparisons; however, ...

"John C. Bollinger" <> wrote in message
news:c9q0hg\$ft0\$...
> Andy Fish wrote:
>
> > I so hate checking array bounds that I always iterate over arrays like

this:
> >
> > for (i=0; ; i++) {
> > try {
> > String name = myArray;
> > ...
> > } catch (ArrayBoundsOutOfIndexException) {
> > break;
> > }
> > }

>

sorry, my post was meant as a joke

I'm still not really sure how much of this whole thread is a joke

> Yuck. That violates my principle of not relying on exceptions to drive
> program logic. (Yes, it's a fuzzy principle. Don't try to pin me
> down.) It also doesn't work if you only want to iterate over part of
> the array.
>
>
> John Bollinger
>

Andy Fish, Jun 4, 2004
17. ### Timo KinnunenGuest

On Fri, 04 Jun 2004 15:07:15 +0200, Thomas Weidenfeller wrote:

> Like the user mis-typed some input value? Like some size or offset value
> you get in a networking protocol? There are a lot of good reasons to
> check array indices for both the upper and lower bound, and provide some
> graceful handling, instead of just catching the exception - if at all.

Checking input values and checking array bounds are two different things.
The first you expect to be broken, the latter you expect to be fine but
check anyway to make sure.

In the networking example I'd draw the line like this: if the receiver is a
prototype which receives handcrafted packets, I'd check them for validity,
packets from sources which I trust to know how to do the right thing, I'd
let the automatic array bounds checking and exception mechanism to take
care of checking.

Timo Kinnunen, Jun 4, 2004
18. ### Roedy GreenGuest

On Fri, 04 Jun 2004 12:43:51 GMT, "Andy Fish"
<> wrote or quoted :

>
>But a good mathematician would never quote a result over a narrower range
>than he knew it to be true - that would be a waste of maths

That reminds me of the old joke:

The Mathematician's recipe for making tea:

1. If the kettle is empty, fill it.

2. Boil the water.

3. Pour into a cup.

5. If the kettle contains water, empty it, which reduces the situation
to the first case.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green, Jun 4, 2004
19. ### Roedy GreenGuest

On Fri, 04 Jun 2004 15:07:15 +0200, Thomas Weidenfeller
<> wrote or quoted :

>Like the user mis-typed some input value? L

I think you are just trying to get a rise. Input validation has
nothing to do with subscript range checking.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green, Jun 4, 2004
20. ### PedroGuest

Re: I thought that array bounds checking needed two comparisons;however, ...

On 4-6-2004 14:44, Roedy Green wrote:
> On Fri, 04 Jun 2004 14:19:50 +0200, Thomas Weidenfeller
> <> wrote or quoted :
>
>
>>Congratulations if you never ever had the need to check an index against
>>an array size in your own code. Oh, you use exceptions exclusively for
>>that? Ah well, ...

>
>
> In your own code you don't worry about the negative case.

Well, you *should* when iterating over an array in reverse order.

The following code snippet fails with an ArrayIndexOutOfBoundsException

char[] msg = {'m', 'o', 'o', 'b'};
for(int i = msg.length - 1; i < msg.length; i--)
{
System.out.print(msg);
}

> If that has
> happened, something is REALLY wrong.

Not in the case above, it just indicates EOI [ End Of Iteration ;-) ]

Regards,
Pedro

Pedro, Jun 5, 2004