Re: Justifying Optimization

bhurt@spnz.org (Brian Hurt) writes:
>As a side comment, I think a lot of programmers prefer to
>hand-optimize, even if the computer can do it faster and better for
>them. To be a programmer (and survive) you have to like complexity.
>Some code is just inately boring. I mean, consider:
> for (i = 0; i < len; ++i) {
> a[i] = f(b[i]);
> }


I used to think that it's ok to write code looking like this even in
performance-critical parts because the compiler would optimize it
anyway. In the example above this might be true, but in general it is
not. E.g., consider


    for (i=0; i<size; i++)
        if (a[i]==key)
            return i;
    return -1;


Neither gcc-3.2.1 -O3 nor Compaq C V6.4-005 -O5 eliminate the
induction variable i in this loop; so strength-reducing a[i] does not
really help. The reason for this becomes clear after a little
thinking, but in general such things are not obvious.


So for some time I thought that one should do the minimum changes
needed to get the optimizations I want. But over time I have come to
the conclusion that if you really want the optimization, you should do
it yourself; e.g., I just played around for some time trying to get
the optimization from gcc-3.2.1 while keeping it mostly in the
array-indexing-style, but did not succeed. And even if I succeeded,
this could change with the next compiler or compiler version.


So nowadays, if I care about performance in this example, I go
directly for a version that uses C pointer arithmetic to eliminate i:


    for (p=a; p<a+size; p++)
        if (*p==key)
            return p-a;
    return -1;


Maybe I would also move the loop-invariant code "a+size" out of the
loop, but I am pretty certain that most compilers manage that
themselves.


In this example, another thing that compilers do not do by themselves
is to change the interface of the function to return a pointer to the
found element (or NULL), eliminating the computation of "p-a" here (a
subtraction and a shift-right), and probably an indexing operation
into a in the user of this routine.


Discussion:


- You have to know compilers pretty well to know when you can rely on
the optimizer and when not; and even then it's pretty easy to be wrong
or introduce something blocking the optimization inadvertantly during
optimization.


- Abstraction costs: As we see in this very simple example, even
indexing, which compilers understood from the early days in the
mid-50s still has a performance penalty over pointer arithmetic in
some cases.


- OTOH, abstraction can also help: wrt alias analysis, using an
indexing programming style is much easier for the compiler than using
a style involving explicit pointers.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

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