🚀 go-pugleaf

The argument is whether hand optimizations are bad. My point is that
there are optimizations that current compilers can't do at all in
practice, even though there are no barriers in theory; if those must
be done by hand, what's wrong with doing simpler ones by hand? You
can't draw the line between trivial optimizations and so-called linear
programming (inductive generalization, trading space for time, or
whatever you want to call it).

I'm answering this article because the author was the only respondent
who realized that my example is, in principle, mechanically solvable.
Others tried to draw that line, saying (in essence) that only humans
could figure out Knuth's delta2 algorithm. But there's no reason that
compilers can't do linear programming---the necessary AI is old hat.
They can insert one temporary variable; why not allocate some memory
and insert n of them?

In article <1041@kunivv1.sci.kun.nl> root@kunivv1.sci.kun.nl (Privileged Account) writes:
> (Dan Bernstein) writes:
> >Can it figure out, say, Knuth's algorithm for computing the delta2 table
> >in Boyer-Moore string searching, starting from a dumb algorithm for the
> >same job?

> - first, Knuth's algorithm as published in [1] is *WRONG*.

I'm not talking about Knuth's delta2 algorithm as presented in his
addendum to the 1976 Knuth-Morris-Pratt paper on the subject. I'm
talking about Knuth's delta2 algorithm, the perfectly correct example
of a solution to a linear programming problem. Don't misinterpret.
(If you don't understand this, read Knuth's ACP historical comments on
Euclid's algorithm, and think about what we call Euclid's algorithm.)

> It is Norbert's feeling, however, that in the future compilers will be
> able to come up with the delta2 algorithm, since all that is involved in
> a derivation by hand is finite differencing (aka strength reduction).

Exactly! I agree completely with Volker. This all falls more generally
under linear programming. That's why I chose the example: Calculating
the delta2 table quickly is a (conceptually) simple job of inserting
appropriate temporary variables.

> My view of this whole issue is the following:
> - there are two kinds of optimisations:
>   routine ones and smart ones.

Volker just erased this line. Now you're turning around and redrawing it?

>   Smart optimisations are inventions of new algorithms, like the BM
>   pattern matching algorithm *itself*,

I'll bet that a few hundred years from now, compilers will be able to
figure this out. After all, the basic idea is just to sort a certain
three-dimensional comparison network into an efficient order. (Didn't
think of it that way, didja.) You can't make this distinction.

>   The only problem I don't know for sure how to place is register
>   allocation.

I place it at the very bottom: it's the only thing that can't be done
by hand, because the language has no support for it. (This is about the
only unarguable point in this discussion.) So the compiler had better
do a good job.

> I'm very sorry for you, mr. Bernstein, that you chose an example that
> proves my (and Nick Rothwell's) point.

Not at all. Have you lost track of what the point is? Read again.
Everything you say above ``my view is'' supports my argument; what
you say below ``my view is'' has nothing to do with my example.

---Dan