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

[Casey Hawthorne]

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

 

[Thomas Weidenfeller]

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

 

[Andy Fish]

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

 

[Michael Borgwardt]

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.

 

[Thomas Weidenfeller]

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

 

[Roedy Green]

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.

 

[Roedy Green]

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

In Java L is always 0.

 

[Michael Borgwardt]

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.

 

[Andy Fish]

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

 

[Roedy Green]

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.

 

[Thomas Weidenfeller]

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

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

;-))

Two obvious What about

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

)

/Thomas

 

[Andy Fish]

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;
}
}

;-))

 

[Thomas Weidenfeller]

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

Maybe not in your code.

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]

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

 

[John C. Bollinger]

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
(e-mail address removed)

 

[Andy Fish]

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

 

[Timo Kinnunen]

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,
if the receiver is an exception-safe release version and it receives
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.

 

[Roedy Green]

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.

4. add tea.

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

 

[Roedy Green]

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.

 

[Pedro]

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