Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!think.com!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Aggressive optimization
Message-ID: <6063@lanl.gov>
Date: 15 Nov 90 21:05:07 GMT
References: <5494:Nov1519:06:3790@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 124

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.

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.

In this discussion, _you_ are refusing to give a specific example on
the grounds that no particular example can fool _all_ optimizers.
Fair enough.  But if the ones that fool a specific optimizer are
so _rare_ that you can't find one, the for _practical_ purposes, the
problem doesn't exist.

> [...]                    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.  You have been consistently pointing out that
the optimizations you are referring to must be carried out by hand.
Fine.  I prefer to make _specific_ statements to the optimizer about
what it should do.  That way, no one (like the programmer himself
at a later date) will get confused about why the code is stated in
the way it is.  So, an explicit directive to the compiler that a
path through the code is more common than another path will be
specific (and easier to verify later).  An implicit statement
of that same fact (like, by reording the computation of pointer
expressions) will lead the later readers of the code to ask "why
did he/I do that?"

> [...]   I am perfectly willing to accept that C's pointer arithmetic may
> not be the best way to express array shifts, and I'm interested in your
> views on better ways to express them. [...]

Finally.  [...]

> [...]                                 But Fortran doesn't have them.
> Neither does Pascal. Neither does Ada. Those languages are suboptimal.

Yet, all these languages can handle the _specific_ examples that you've
posted.  Frequency assertions to the compiler would solve the rest of
the ones that you claim are "theoretically" out there.

> [...]
>> I admitted nothing of the sort.  I admitted that there were
>> optimizations the _humans_ could find that compilers couldn't.
> 
> Somehow I don't see the difference, but you said it better. There are
> optimizations of array code into pointer code that humans can find and
> that compilers can't. Glad we agree.

We don't.  The following statement is part of the same paragraph and
thought as the preceding.

>> I
>> _don't_ admit that pointers are in any way superior to arrays in
>> allowing humans to express those optimizations to the compiler.

This is what _I_ said.

> [...]
>> 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?  Your entire claim here is that the
human can _always_ beat the compiler at its own game.  This is
only true when the human has perfect knowledge of what the compiler's
game is.

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.

>> Which is why it is better to let the programmer give assertions.
> 
> Again, I don't care how you let the programmer do his work. However, you
> are abusing the word ``assertions'' in the same way that you are abusing
> ``array'' above. Assertions in existing languages (and compilers) simply
> don't have the power to express the level of decisionmaking that has to
> go on here.

Again, you are restricting the argument to a subset of the original
subject.  In your f77 vs. cc thread about interprocess aliasing, the
thread was begun by _you_ and was restricted to _existing_ languages.
This thread has _no_ such restrictions.

So, the fact that assertions in existing languages don't do a this
particular thing (express the expected frequency of a decision
point), is _not_ an argument against using this solution.  What
_is_ an argument against using this is that there are, as yet,
no _specific_ examples which require it.

> [...]
> 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.  I can pipeline and do
register allocation better than the compilers I have (which, by the
way are _really_ good: most people _can't_ beat them - I'm bragging,
but it's really true:  I wouldn't bother to use assembly if I
couldn't beat the compiler :-).  I don't hand optimize C because the
compiler usually re-pessimizes the code.

As to whether C coding is effective, I can only judge from
experience.  Every code that I've ever recoded from C to some other
language runs _faster_ in the other language.  This is a _uniform_
observation with no exceptions _at_all_.  This _may_ be that the C
code available to me is abnormally bad.  But, it seems unlikely.  It
seems more likely that the C code I've seen is typical.

J. Giles