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: <5059:Nov1323:43:2290@kramden.acf.nyu.edu>
Date: 13 Nov 90 23:43:22 GMT
References: <7001:Nov1008:37:2690@kramden.acf.nyu.edu> <5810@lanl.gov>
Organization: IR
Lines: 32

In article <5810@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <7001:Nov1008:37:2690@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > Jim, you've made a blanket assertion that arrays are as efficient as
> > pointers. I've proven you wrong. Give up.
> You have not even posted _one_ counter-example.

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.

However, no counterexample can exist for *all* algorithms, just as no
single proof can exist that *all* computer programs will fail to find.
Surely you understand this.

> The point you seem to miss is that _all_ of you hand-optimizations
> apply to the array versions as well.

You're quite right.

It's also true that a computer program can read in a rigorous, formal
proof, and in linear time either say it's correct or exhibit the error.

That is irrelevant to *finding* the proof in the first place, just as
your statement is irrelevant to *finding* the hand optimizations in the
first place.

---Dan