Path: utzoo!attcan!uunet!wuarchive!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: <9239:Oct2003:53:1890@kramden.acf.nyu.edu>
Date: 20 Oct 90 03:53:18 GMT
References: <66071@lanl.gov> <29028:Oct1906:58:2890@kramden.acf.nyu.edu> <jdarcy.656338868@zelig>
Organization: IR
Lines: 67

Skip to the word ``opinion'' to see my main point.

In article <jdarcy.656338868@zelig> jdarcy@encore.com (Floating Exception) writes:
> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> > [convoluted example]
> >A less trivial example: In a heavily hand-optimized implementation of
> >Nussbaumer's convolution method
> Give us a break, Dan!  Both of the examples you've given represent changes
> of *algorithm* based on foreknowledge of possible input values,

First of all, neither change was based on any foreknowledge of possible
inputs; all constraints were expressed by actual tests in the programs.
More importantly, they weren't algorithm changes at all. See below for
further explanation.

> a type of
> optimization of which nobody expects compilers to be capable, at least not
> in this century.

Exactly. Compilers can't do this sort of simple optimization. See below.

> I think most people admit that your obviously high opinion of your own
> programming skills may not be entirely unjustified, but not everyone is
> so talented.

Wtf are you talking about? I was presenting the optimization the way a
very smart compiler might see it, step by step. Now here's how any
programmer would see it, especially after coding it in the first place:

--> Variable x is the number of bits of padding inside a byte, so it's
--> between 0 and 7. So we can compute f(x) more efficiently by
--> precomputing a table for 0 through 7. Done.

You call it ``convoluted''? No shit. The human brain works in very
convoluted ways. It can also do a lot of things infinitely better than
any existing computer. Simple hand optimizations like the one above are
well beyond the reach of current technology. The same comments apply to
the other optimization I talked about.

In any case, this optimization is in the class of optimizations that I
described: introducing new intermediate quantities (in this case, the
precomputed table) and using them to cut out redundant code (in this
case, the main computation). Jim says he has compilers that can do those
optimizations. I find that unbelievable.

> I would say that it's perfectly
> reasonable for compilers to optimize as aggressively as their creators
> can make them.  Obviously, this should be done without sacrificing any
> correctness,

Well, yes. This is the crux of the issue. I (and, I think, Piercarlo,
and lots of other programmers) see too many optimizer bugs to believe
that aggressive computer optimization is worthwhile. Other people may
think the balance swings in the opposite direction. It's just a matter
of where you draw the line.

By the way, I don't agree with one of your comments---namely, that
automatic optimization becomes less useful as hand optimization kicks
in. On the contrary: the compiler will always understand details of the
machine language that are purposefully hidden from the language used by
the programmer. The programmer and compiler optimize independently, in a
sense, as long as the compiler doesn't try to do optimizations that it
doesn't understand. So on a RISC machine I'll gladly have the compiler
give me its 2x instruction scheduling benefit, no matter how much hand
optimization time I put in.

---Dan