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: <9576:Nov1523:11:0990@kramden.acf.nyu.edu>
Date: 15 Nov 90 23:11:09 GMT
References: <5494:Nov1519:06:3790@kramden.acf.nyu.edu> <6063@lanl.gov>
Organization: IR
Lines: 120

The saga continues: Jim pesters Dan for a *specific* example of code
that real optimizers can't handle. Dan is surprised. He thought that Jim
was reading the group while people showed specific examples that tripped
up Sun's optimizer. But just to be sure he gives an example that trips
up gcc. Life goes on.

In article <6063@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <5494:Nov1519:06:3790@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > Look, Jim. You were saying a few weeks ago that arrays (as in Fortran,
> > or Pascal, or Ada) [...]
> Actually, I said arrays as in _my_ suggested language.  I used Pascal,
> etc. as examples that would be familiar to the rest of the net in order
> to counter your weak attempts to make pointers look good.  You have
> yet to pose a _specific_ example of a case that even these languages
> couldn't optimize.

You want a specific example? Were you reading this group when somebody
pointed out how Sun's optimizer couldn't produce even near-optimal code
for a simple loop through an array? Matt pointed out that gcc did much
better. gcc, however, will produce suboptimal code for

  for (j = 0;j < 100;j++)
    a[i * j] = ...;

As you now understand, no optimizer will handle all cases. For any
optimizer you show me, there exists array code that it can't convert
into pointer code as well as possible. What matters in practice is that
real optimizers trip up on such simple code. Even good Fortran
optimizers don't do very well on moderately complex code.

> There is some loudmouth on the net who (in another thread) is making
> very insulting remarks about computing scientists being too theoretical
> an not being practical.  He is insisting on specific practical experience
> as a measure of a program's efficiency.

Yes, and I'm sure he will continue to do so. He is not a computer
scientist: he uses computers to get things done. He gets annoyed when
computer scientists make ridiculous assertions about real-world problems
just because their models aren't sufficiently accurate or because they
haven't bothered to think.

> In this discussion, _you_ are refusing to give a specific example on
> the grounds that no particular example can fool _all_ optimizers.
> Fair enough.

Thank you for saying so. So you *do* admit that you were wrong when you
said that arrays (as in Fortran) can always be made as efficient as
pointers (as in C)? Yes? You do? Stop beating around the bush. A week
ago you were saying that arrays were as efficient as pointers, and that
somewhat better compilers than we have today would suffice. Now we know
that you were wrong. Do you admit it?

By the way, I fully expect that you will chop up the above paragraph and
fail to quote the most important parts. That's your argument style.

> But if the ones that fool a specific optimizer are
> so _rare_ that you can't find one,

When did that ridiculous idea come out of the blue? I merely thought
that you had been paying attention to the examples already posted in
this group.

> > [...]                    There is *no* way that an automatic optimizer
> > can always produce the optimal pointer version of pointer-free code.
> There is (by _your_ own earlier statements) no automatic optimizer
> that can always produce the optimal pointer version of code that
> _has_ pointers either.

Where did that ridiculous idea come out of the blue? I don't know what
earlier statements you're referring to. I certainly don't agree with the
conclusion.

> >> I also pointed out that the _human_ is not in possession of important
> >> information about the algotithm that the _compiler_ does know
> > Sure, but that's irrelevant to this subthread.
> Why is every thing that doesn't support _your_ position suddenly
> not relevant to the thread?

Huh? It supports neither my position nor the opposite of my position in
this subthread. It's simply irrelevant. See below.

> Your entire claim here is that the
> human can _always_ beat the compiler at its own game.

Where did that ridiculous idea come out of the blue? I have never said
any such thing. I have said that it is *not* true that the compiler can
always beat the human at optimizations. Theory tells us that automatic
tools will never be good enough; in practice, programmers who put the
effort into hand optimization will get better results than optimizers.

As one specific case, Fortran arrays can't be shifted; machine language
arrays (pointers) can. Hence it is not true that the compiler can always
convert Fortran code into machine language code making the best use of
pointers. Hence the programmer should be given array shifting tools
himself---through, for instance, C pointers.

I certainly don't believe that the compiler is impotent; in fact, I said
a week ago in this group that I trust the compiler to do (low-level)
instruction scheduling. Herman disagreed; take it to him.

> Again, I don't oppose letting the programmer have the tools to
> _try_ to beat the compiler with.  I'm just pointing out that it
> _is_ relevant that the compiler has some hidden cards in its hands.

Why? I just don't see its relevance to this issue. All I've been trying
to do in this subthread is make it clear that C pointers, with their
``awful'' arithmetic, can make some code more efficient than in Fortran.
That's all.

> > Obviously you like hand optimization about as much as you like C. You
> > have the same amount of prejudice against each. Since you never bother
> > to learn how to optimize by hand or to program in C, you never believe
> > that either can be effective. The vicious cycle continues.
> I hand optimize in ASSEMBLY all the time.

Good to see you're awake. However, I think you'd find some rather
impressive gains from hand optimization in any language, if you just
took the time to practice.

---Dan