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: <4857:Nov1405:39:3590@kramden.acf.nyu.edu>
Date: 14 Nov 90 05:39:35 GMT
References: <5059:Nov1323:43:2290@kramden.acf.nyu.edu> <5839@lanl.gov>
Organization: IR
Lines: 90

In article <5839@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <5059:Nov1323:43:2290@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > As part of my proof I have posted the general form that a counterexample
> > would take. Namely, if you show me an algorithm that can supposedly
> > shift arrays optimally, I'll find a program for which you cannot detect
> > which of two branches is taken (independently of the input). I'll then
> > use x[0] (or x[a + b], or whatever) in one branch, and x[1] (or
> > whatever) in the other branch. You won't be able to figure out whether
> > it's better to precompute &x[0] or to precompute &x[1]. Such a program
> > must exist.
> Fine.  The compiler won't be able to determine this one.

Thank you for admitting it! I'm glad we agree that you were wrong when
you said that the computer can make arrays as efficient as pointers in
all cases.

> Neither will
> the human programmer.

Bullshit. You removed all my analogies to theorem-proving: the analogy
here is ``Fine. The computer won't be able to figure out proofs for this
one. Neither will the mathematician.'' Just because no single algorithm
will handle every case doesn't mean people can't!

> If the programmer knows a priori which branch
> will be taken, why is there a branch?

Maybe he didn't realize at first. But I know what you're saying, and in
the proof (which you apparently haven't read) I pointed out why that's
irrelevant: all you need is for one branch to be taken with much higher
probability than another. As I'm sure Herman will instantly agree, this
is an extremely common case in real numerical code.

> And, if he doesn't know a priori
> which branch will be taken, then he doesn't know which pointer to
> precompute.  And, since he doesn't know which to precompute, he must
> guess:

No. This is like saying ``And, since he doesn't know a priori how to
prove the theorem, he won't be able to find a proof.'' All the best
efforts of AI aside, we must assume that, for any given program, *some*
programmer will be able to optimize better than the compiler. We must
not take away his tools for doing so.

  [ a reasonable summary of programmer-versus-compiler in general ]
> The best solution is
> probably to let the compiler choose and give the programmer the
> ability to assert information about the frequency of each branch.

Some people would argue for a third solution, namely profiling; but
there are many cases when basing optimizations on profiling can be very
dangerous. (You kill your worst case in favor of your average case.)

Anyway, I don't care whether you let the programmer specify array shifts
imperatively or functionally. Just let him do it.

> In any case, this contrived example

``Simplified example.'' Since you refused to think through real
examples to come to the same conclusion.

> only saves a fractional add at
> best (an add is saved each time you take the branch that you
> precomputed for, one is lost each time you take the other branch,
> the average "savings" is a fraction of an add).

Cripes. What if there are several pointers (arrays) being dealt with?
What if this is in a loop that will be executed a trillion times? We are
talking about optimizations here, so I don't understand your attitude.

> The problem is,
> it's possible that the programmer will pick the wrong one to
> precompute.

That's true. People make mistakes. So what? Why do you keep bringing up
these points that we all accept? Lots of things are possible. Saying
that the programmer shouldn't be *allowed* to make this choice because
he might make a mistake is like saying that people shouldn't program in
the first place because they might make a mistake. Who cares?

> On most compilers, it
> will probably decide to precompute _both_ anyway - even when you use
> explicit pointers.

Sometimes this isn't possible. Remember that space optimization is
important too: if the less-executed branch is only executed one
millionth of the time, the code and data space for the extra computation
is not worthwhile.

---Dan