Re: eliminating array bounds checking overhead

"Matt Timmermans" <mtimmerm@opentext.nospam-remove.com>
12 May 2000 22:34:04 -0400

          From comp.compilers

Related articles
[16 earlier articles]
Re: eliminating array bounds checking overhead monnier+comp/compilers/news/@flint.cs.yale.edu (Stefan Monnier) (2000-05-01)
Re: eliminating array bounds checking overhead r_c_chapman@my-deja.com (2000-05-01)
Re: eliminating array bounds checking overhead markw65@my-deja.com (Mark Williams) (2000-05-04)
Re: eliminating array bounds checking overhead world!bobduff@uunet.uu.net (Robert A Duff) (2000-05-04)
Re: eliminating array bounds checking overhead paule@martex.gen.oh.us (Paul Evans) (2000-05-04)
Re: eliminating array bounds checking overhead d95josef@dtek.chalmers.se (Josef Sveningsson) (2000-05-12)
Re: eliminating array bounds checking overhead mtimmerm@opentext.nospam-remove.com (Matt Timmermans) (2000-05-12)
| List of all articles for this month |
From: "Matt Timmermans" <mtimmerm@opentext.nospam-remove.com>
Newsgroups: comp.compilers
Date: 12 May 2000 22:34:04 -0400
Organization: http://extra.newsguy.com
References: 00-04-194 00-04-208
Keywords: performance, architecture
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3

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.





Post a followup to this message

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