Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!snorkelwacker!usc!cs.utexas.edu!rice!titan!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.lang.misc
Subject: Re: Common subexpression optimization
Message-ID: <4818@brazos.Rice.edu>
Date: 8 Feb 90 23:24:09 GMT
References: <4561@scolex.sco.COM>
Sender: root@rice.edu
Organization: Rice University, Houston
Lines: 39

In article <5453:23:28:32@stealth.acf.nyu.edu> brnstnd@stealth.acf.nyu.edu (Dan Bernstein) writes:
>In article <2115@castle.ed.ac.uk> nick@lfcs.ed.ac.uk (Nick Rothwell) writes:
>> This is rubbish, check out the performance of New Jersey ML
>> (high-level functional language, efficient optimised native code
>> generation).

>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?
>
>Humans can optimize better than computers. This will be true for a long
>time. I chose the above example randomly, but it'll serve well enough as

You've made a big step from eliminating common subexpressions to
understanding Knuth (anything by Knuth).  
One is a trivial task; the other requires "thought."  
Computers are good at trivial tasks;
humans, on the other hand, tend to fumble trivial tasks.

Optimization in a compiler isn't finding a good algorithm.
"Optimization" is a misnomer.  It's transforming the program to run 
more quickly.  You never get asymptotic improvements.  
You don't see discovery of new algorithms.

On the other hand, optimiztion lets me avoid having to express 
tedious details that can be discovered automatically (trivially).  
It lets me write matrix multiply (or whatever) in a short time, 
with good performance, instead of trying to squeeze 
the last ounce out of the implementation.

Hopefully you can put the saved time to use discovering better algorithms.
Good old seperation of concerns -- the computer does what it's good at
and I do what I'm good at.

As to "optimizing better than compilers", have you started working on 
a version of matrix multiply that will beat our Fortran?  Good luck!

Preston Briggs
preston@titan.rice.edu