David Crayson is right to point out that "a decent compiler would have
unrolled the loop" in the specific five-element case he examines.
This is not, however, a tactic that is appropriate for n >> 5.
If one looks at what optimizing C compilers, the usual suspects, do
with the classical Kernighan-Ritchie function
/* binsearch: Find x in v[0] <= v[1] <= . . . <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n – 1;
while (low < high) {
mid = (low + high) / 2 ;
if (x < v[mid]) high = mid – 1;
else if (x > v[mid]) low = mid + 1;
else /* found match */
return mid;
}
return –1;
}
one finds them using two pairs of
ternary-comparison-followed-by-specializing-branch instructions and
not reordering the suboptimal sequence of these two tests that
Kernighan and Ritchie specified.
Optimizations are important, and loop unrolling is classical: Lowry
and Medlock did it in their Fortran H compiler.
That said, the notion that language differences and/or differences
between substandard and optimal algorithms can and will somehow be
washed away by "any decent compiler nowadays" is, at best, a dubious
one.
John Gilmore, Ashland, MA 01721 - USA
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: INFO IBM-MAIN
