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

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

  1. 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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Casey Hawthorne

    Andy Fish Guest

    "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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Casey Hawthorne

    Roedy Green Guest

    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.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 4, 2004
    #6
  7. Casey Hawthorne

    Roedy Green Guest

    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.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 4, 2004
    #7
  8. 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
    #8
  9. Casey Hawthorne

    Andy Fish Guest

    "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
    #9
  10. Casey Hawthorne

    Roedy Green Guest

    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.


    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 4, 2004
    #10
  11. 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
    >
    > ;-))


    Two obvious :) What about

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

    :))

    /Thomas
    Thomas Weidenfeller, Jun 4, 2004
    #11
  12. Casey Hawthorne

    Andy Fish Guest

    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
    #12
  13. 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.


    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, Jun 4, 2004
    #13
  14. 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
    #14
  15. 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
    #15
  16. Casey Hawthorne

    Andy Fish Guest

    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
    #16
  17. 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,
    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.
    Timo Kinnunen, Jun 4, 2004
    #17
  18. Casey Hawthorne

    Roedy Green Guest

    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.

    4. add tea.

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

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 4, 2004
    #18
  19. Casey Hawthorne

    Roedy Green Guest

    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.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 4, 2004
    #19
  20. Casey Hawthorne

    Pedro Guest

    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
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris

    Array bounds checking

    Chris, Jul 5, 2005, in forum: Java
    Replies:
    5
    Views:
    784
  2. Frederick Gotham

    Extremely pedantic, but however...

    Frederick Gotham, Oct 21, 2006, in forum: C Programming
    Replies:
    22
    Views:
    638
    Frederick Gotham
    Oct 23, 2006
  3. r.z.
    Replies:
    7
    Views:
    297
    Mirek Fidler
    Dec 19, 2006
  4. Replies:
    4
    Views:
    262
    Roland Dick
    Nov 9, 2007
  5. Casey Hawthorne
    Replies:
    15
    Views:
    783
Loading...

Share This Page