Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!udel!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Aggressive optimization
Message-ID: <5950@lanl.gov>
Date: 14 Nov 90 20:39:06 GMT
References: <4857:Nov1405:39:3590@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 84

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.  I
_don't_ admit that pointers are in any way superior to arrays in
allowing humans to express those optimizations to the compiler.

I also pointed out that the _human_ is not in possession of important
information about the algotithm that the _compiler_ does know (like
pipelining, instruction selection, and register allocation - which
the compiler makes the final judgement about even in languages which
allow programmers to hint about things like this).  Since the human
doesn't know this stuff, his choice of which to optimize in the case
you gave is usually pure guesswork.

> [...]
>   [ 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.)

Which is why it is better to let the programmer give assertions.  The
human is then free to decide whether the worst case is important enough
to optimize or not.

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

Quite.  When did I say otherwise?

> [...]
>> 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%.  The only language type which allow programmers to
make this decision with a better batting average is assembly (where
the programmer does _all_ register allocation and instruction
selection).

> [...]                                                         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?

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.

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

Oh, your example implied that space wasn't an issue.  You wrote
glibly about having a choice of saving &x[0] or &x[1].  Clearly, in
all programming languages I know of, &x[0] is _automatically_ saved
for the whole lifespan of the array.  Only in C is it even _possible_
to lose the base address of an array (without losing the _whole_
array at the same time).  So, if you're talking about precomputing
&x[1] and saving it _in_addition_ to &x[0], you obviously didn't
think saving space was meaningful.  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.

J. Giles