Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > I thought that array bounds checking needed two comparisons; however, ...

Reply
Thread Tools

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

 
 
Casey Hawthorne
Guest
Posts: n/a
 
      06-04-2004
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
 
Reply With Quote
 
 
 
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      06-04-2004
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
 
Reply With Quote
 
 
 
 
Andy Fish
Guest
Posts: n/a
 
      06-04-2004

"Thomas Weidenfeller" <(E-Mail Removed)> wrote in message
news:c9pcoj$l3s$(E-Mail Removed)...
> 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




 
Reply With Quote
 
Michael Borgwardt
Guest
Posts: n/a
 
      06-04-2004
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.
 
Reply With Quote
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      06-04-2004
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
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      06-04-2004
On Fri, 04 Jun 2004 10:46:21 +0200, Thomas Weidenfeller
<(E-Mail Removed)> 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.

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      06-04-2004
On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
<(E-Mail Removed)> wrote or quoted :

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


In Java L is always 0.

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
Michael Borgwardt
Guest
Posts: n/a
 
      06-04-2004
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.
 
Reply With Quote
 
Andy Fish
Guest
Posts: n/a
 
      06-04-2004

"Roedy Green" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
> <(E-Mail Removed)> 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.



 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      06-04-2004
On Fri, 04 Jun 2004 14:19:50 +0200, Thomas Weidenfeller
<(E-Mail Removed)> 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.


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

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Changing the meaning of the array indexing brackets "[ ]" to do bounds checking and then ... Casey Hawthorne C Programming 15 11-04-2009 03:42 PM
To increase speed on manipulating big arrays in Java with minimal bounds checking, ... Casey Hawthorne Java 16 09-01-2005 06:33 AM
Array bounds checking Chris Java 5 07-06-2005 07:23 AM
Bounds Checking? Julian Zhang C Programming 3 01-20-2004 11:56 PM
Macro argument bounds checking? Jim Cook C Programming 7 09-22-2003 02:50 AM



Advertisments