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: <5494:Nov1519:06:3790@kramden.acf.nyu.edu>
Date: 15 Nov 90 19:06:37 GMT
References: <4857:Nov1405:39:3590@kramden.acf.nyu.edu> <5950@lanl.gov>
Organization: IR
Lines: 88

Look, Jim. You were saying a few weeks ago that arrays (as in Fortran,
or Pascal, or Ada) could always be made as efficient as pointers (as in
C, or, of course, in machine language). You didn't prove your claim, and
various people disagreed with you. Now I've shown that they were right
and your claim is wrong. There is *no* way that an automatic optimizer
can always produce the optimal pointer version of pointer-free code.
Give up.

The crucial property of pointers here is that they can express array
shifts. 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. But Fortran doesn't have them.
Neither does Pascal. Neither does Ada. Those languages are suboptimal.

Detailed responses follow.

In article <5950@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <4857:Nov1405:39:3590@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > 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.
> 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.

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

Huh? I defined what I meant by those terms pretty precisely in my proof.
Maybe your idea of ``arrays'' includes array shifting, or pointer
arithmetic, or whatever you want to call it. That has nothing to do with
arrays in Fortran, or Pascal, or Ada.

> 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.

> 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.

> >> The problem is,
> >> it's possible that the programmer will pick the wrong one to
> >> precompute.
> > That's true. People make mistakes. So what?  [...]
> Well, since you don't seem to know, I'll tell you so what.  In this
> particular case, even _very_ clever people will make mistakes at about
> a rate of 50%.

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.

> Further, who said anything about not allowing the user to make the
> choice?  I didn't.  I only said that the user should not be forced
> to the level of pointers to have this type of control.

So propose a different mechanism!

Q has a set of array slicing mechanisms more powerful than Fortran 90's.
I *think* they eliminate the need for pointer arithmetic. I've thought
so for months. But I'm not sure. I just haven't tried it on enough real
code to be absolutely sure that it does the job, and I haven't spent
enough time working it out on paper.

> If you were talking about
> precomputing &x[1] and saving it _instead_of_ &x[0], I would object
> that it's bad style to lose track of the base of the array.

Oh, great. We're talking about optimizations and now you introduce
``style.'' Gee, Jim, what do you think of the ``style'' of optimized
output from the Convex compiler? I must say it's so unfashionable.
Ultrix is much more hip.

Of course I was talking about saving &x[1] instead of &x[0]. If you had
read the proof you would understand this.

---Dan