Re: Justifying Optimization (Anton Ertl)
21 Feb 2003 00:51:36 -0500

          From comp.compilers

Related articles
[19 earlier articles]
Re: Justifying Optimization (Joachim Durchholz) (2003-02-11)
Re: Justifying Optimization (Joachim Durchholz) (2003-02-11)
Re: Justifying Optimization (Joachim Durchholz) (2003-02-11)
Re: Justifying Optimization (2003-02-11)
Re: Justifying Optimization (2003-02-11)
Re: Justifying Optimization (2003-02-11)
Re: Justifying Optimization (2003-02-21)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 21 Feb 2003 00:51:36 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 03-01-088 03-01-110 03-01-137 03-02-055
Keywords: optimize, practice
Posted-Date: 21 Feb 2003 00:51:36 EST (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

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.


- 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

- 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

Post a followup to this message

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