Re: eliminating array bounds checking overhead

Norman Ramsey wrote in message 00-04-208...
>Bonus trick, which I learned from Andrew Appel:
>
> ((unsigned)(i-(lo+1)) < hi)
>
>Beware fencepost errors.
>--




Uh oh... I think your programs are exploding.


To replace (i > lo && i < hi), you need ((unsigned)(i-(lo+1)) <
(hi-(lo+1))).


Note to the original poster: This isn't too useful as written, but that's
because of the way you phrased your check. When this trick is used, you
store the first valid index (lo) and the number of valid indeces (size), so
your check would be (i>=lo && i<(lo+size)). The trick is then
((unsigned)(i-lo)) < size), which is certainly faster than the two
comparisons.


Often, lo is known to be zero, because you are indexing from a pointer to
the first element in the array, and so the quick check is just (unsigned)lo
< size, and the cast is free.

Return to the comp.compilers page.
Search the comp.compilers archives again.