Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!zaphod.mps.ohio-state.edu!wuarchive!uunet!stealth.acf.nyu.edu!brnstnd From: brnstnd@stealth.acf.nyu.edu Newsgroups: comp.lang.misc Subject: Re: Common subexpression optimization Message-ID: <3668:04:34:52@stealth.acf.nyu.edu> Date: 14 Feb 90 04:34:52 GMT References: <4561@scolex.sco.COM> <14214@lambda.UUCP> <2217@sunset.MATH.UCLA.EDU> <838.18:06:33@stealth.acf.nyu.edu> <2115@castle.ed.ac.uk> <5453:23:28:32@stealth.acf.nyu.edu> <1041@kunivv1.sci.kun.nl> Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein) Distribution: usa Organization: IR Lines: 70 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