Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Aggressive optimization
Message-ID: <20683:Oct1819:44:1490@kramden.acf.nyu.edu>
Date: 18 Oct 90 19:44:14 GMT
References: <1458@exodus.Eng.Sun.COM> <13405:Oct1800:22:5690@kramden.acf.nyu.edu> <1493@exodus.Eng.Sun.COM>
Organization: IR
Lines: 76

In article <1493@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes:
> In article <13405:Oct1800:22:5690@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> >First releases of optimizers simply don't work; after they've spent a
> >few years on the market, their bugs are few and far between. Maybe one
> >bug per ten thousand lines of code, after a year of maturity. It goes
> >down quickly past that.
> Do you have documentation to back this figure up?

No, just my experience backed by what others tell me. (A '60s programmer
says that for years Fortran compilers were built around the same
optimizer, which produced incorrect results on very long stretches of
code. The workaround? Stick a random label in to split up the code.
Many Fortran programs today still have unnecessary labels in strange
places. Funny thing: I had to work around a similar bug, in exactly the
same way, under an optimizer on a three-year-old machine.)

> You didn't read the posting clearly enough (or else I deleted the
> details for brevity).  Better algorithms, high-level hand optimization
> (i.e., malloc, memoization), low-level hand-optimization (unrolling,
> inlining, stuff that optimizing compilers will do automatically for me
> today) all contributed to that speedup.

Okay, I didn't realize that you were including unrolling and inlining in
your 30x figure. But I do a lot more than unroll and inline when I
optimize by hand.

> And, it is not the intention that optimizing compilers do unsafe
> program transformations -- when they do, it is a bug.

Then I don't understand the warning in your company's cc(1) about -O3
and -O4. Is the compiler buggy?

> The wholesale rearrangements that expose parallelism and enhance
> locality are based on sound theory, are incredibly tedious to do by
> hand (the resulting program is often unrecognizeable), and can yield
> fabulous increases in speed. 

Most programs do not manipulate matrices. I agree, it's fine for the
compiler to do what it can. However, the most I have ever seen an
optimizer get is 3x, and *it* has all the low levels of the hardware to
use.

> Other transformations are completely
> unavailable at the source level (can you schedule instructions between
> the fetch, increment, and store required to implement "x++" on a RISC
> machine?) and produce solid improvements in speed.

I agree entirely. In fact, the most impressive optimizer I've seen gets
2x on practically any code. The underlying hardware is extremely
pipelined (much more than a Cray); there are even separate instruction
streams for integer and floating point operations. (And it takes two
instructions to read or write memory.) I don't expect the language to
support this level of instruction scheduling, so the compiler had
better do a good job. 

Note that the optimizer gets relatively little speedup out of anything
other than scheduling and trivial peephole optimizations.

> Perhaps I'm missing something -- I claim, I believe correctly, that
> modern optimizing compilers improve code quality (at the *low level*)
> faster, more effectively, and with a lower error rate than I could
> ever hope to attain by hand (doing the *same* optimizations).

Doing the *same* optimizations, yes; but there are infinitely more
optimizations that you can do by hand, because computers are still
pretty stupid. Except on hugely parallel code, current optimizers get
almost nothing out of ``intelligent'' transformations.

> What's
> wrong with using such an excellent tool?  What awful property of
> optimizing compilers have I missed?

Unsafe transformations and other optimizer bugs. As in sun% cc -O4. Not
to pick on your compiler, which is otherwise rather nice.

---Dan