brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/19/90)
[Copied from comp.lang.misc -John] In article <2301@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes: [ after my description of the most general optimization technique ] > A useful technique, indeed (called "strength reduction" in optimising > compilers, "finite differencing" in transformational programming). Huh? The strength reduction and finite differencing that CS majors learn is absolutely trivial compared to what anyone can do by hand. As I said, walking through an array is only the simplest example. Does anyone have a compiler that can introduce a non-linear intermediate expression and reduce around it? If so, I'm impressed. How advanced is the symbolic algebra system included in the compiler? Can it take advantage of range constraints, so that if it knows that x is between 0 and 7, it might set up a table to calculate ((1<<(x+2))-1)/10 quickly? Can it manipulate floor and ceiling expressions? Can it introduce invariants to figure out range constraints? These are all part of that single, fundamental optimization technique. I know, compilers are improving. Some optimizers fully automate the dullest, most machine-dependent part of optimization---viz., figuring out how often loops or branches are executed in practice, seeing how long machine instructions take, and deciding on that basis whether a given optimization is worthwhile. I really appreciate that. I won't stop hand optimization because of it. > >And I'm not going to introduce subtle bugs in weird cases with unsafe > >program transformations. > Tell me, what do you mean by unsafe program transformations? > Hand optimisations? ``Neither -O3 nor -O4 should be used when compiling either device drivers, or programs that modify external variables from within signal handlers.'' > Of course, finite differencing is relatively safe > since you introduce redundant information most of the time. It's exactly this attitude of ``finite differencing is the only optimization in the world'' that leads people to think that hand optimization is useless. Both the attitude and the conclusion are wrong. > By the way, there *are* systems that help you in > applying source-level optimisations. I'm perfectly willing to use whatever's out there. I'm not willing to pretend that current compilers can figure out any reasonable level of optimization for me. ---Dan -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
eerke@cs.kun.nl (Eerke Boiten) (10/19/90)
In article <18662:Oct1817:18:0090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <2301@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes: > [ after my description of the most general optimization technique ] >> A useful technique, indeed (called "strength reduction" in optimising >> compilers, "finite differencing" in transformational programming). > >Huh? The strength reduction and finite differencing that CS majors learn >is absolutely trivial compared to what anyone can do by hand. As I said, >walking through an array is only the simplest example. It's my experience that CS majors learn *principles*. Of course, principles often seem trivialities to experts. And "what *anyone* can do by hand" is trivial by definition. >Does anyone have a compiler that can introduce a non-linear intermediate >expression and reduce around it? [More examples of sophisticated optimisations deleted] Frankly, I don't know. >> Of course, finite differencing is relatively safe >> since you introduce redundant information most of the time. > >It's exactly this attitude of ``finite differencing is the only >optimization in the world'' that leads people to think that hand >optimization is useless. Both the attitude and the conclusion are wrong. That's not what I said. You called "finite differencing" *the most general* optimisation technique. IMO, it's one of the few general techniques that can usually be safely applied by hand. Things like loop jamming (fusion, merging, etc) are much more error prone. Same goes for code motion. Just to mention a few techniques that compilers can and do apply. I'd be the last to argue that human intelligence is no longer necessary for program optimisation. Some people consider program transformation an AI subject ... Eerke Boiten Department of Informatics (STOP Project), K.U.Nijmegen Toernooiveld, 6525 AD Nijmegen, The Netherlands Tel. +31-80-612236. Email: eerke@cs.kun.nl -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
burley@world.std.com (James C Burley) (10/20/90)
In article <1990Oct18.223231.22315@esegue.segue.boston.ma.us> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
Does anyone have a compiler that can introduce a non-linear intermediate
expression and reduce around it? If so, I'm impressed. How advanced is
the symbolic algebra system included in the compiler? Can it take
advantage of range constraints, so that if it knows that x is between 0
and 7, it might set up a table to calculate ((1<<(x+2))-1)/10 quickly?
Can it manipulate floor and ceiling expressions? Can it introduce
invariants to figure out range constraints? These are all part of that
single, fundamental optimization technique.
I know, compilers are improving. Some optimizers fully automate the
dullest, most machine-dependent part of optimization---viz., figuring
out how often loops or branches are executed in practice, seeing how
long machine instructions take, and deciding on that basis whether a
given optimization is worthwhile. I really appreciate that. I won't stop
hand optimization because of it.
I'm glad to see someone remind us of these issues. Machine-implemented
optimizations are desirable for handling cases we've decided are not only
straightforward to implement via a set of rules (however complicated the code
might get), but (and this point often is overlooked) take all their "inputs"
from the source code ALONE (though some aggressive optimizations also take
"input" from the "omniscient", and sometimes incorrect, person who wrote the
optimization, as in "assume this particular case never happens, even though
it is valid in the language", and which typically can be selectively disabled
via compiler switches).
For example, as Dan suggests above, a compiler that performs range analysis
on data sets (not even just variables, but things like "X never exceeds Y by
more than 50 and is never less than Y" by looking at the source code) is a
desirable thing indeed, but even if it existed it wouldn't be enough. Why?
Because in a case where X and Y are input from the outside (a file or the
user), there may be constraints on them that are not expressed in the source
code (and for which such expression is difficult or impossible in the source
language -- C's "assert" might be an example of how to do it). (Whether the
code should check for violations of the constraints and produce error
messages, however, is entirely a "user interface" issue, ultimately: consider
reading a file produced by a companion program, for example, where the
constraints may already have been checked. When compiling the program
reading the file, one cannot assume the compiler could also read the program
writing the file to derive the constraints: not only is it hard, but in the
real world, that program's source code may not be available! And it's
executable image may be unreadable also, so forget about disassembling!)
What I think is really needed is not only a compiler (here I refer to the
total package of translating, including linking and debugging) that can
recognize and deal with the kinds of optimizations Dan talks about, but that
is easy to interact with, converse with, and to which the programmer can
easily explain other constraints and point out other optimizations worth
trying.
I've been imagining such a beast for many years and hope to start actually
building one, so I've done some thinking about it. It would be very
important to make such interaction easy, so I think the interface would have
to be as much easier to deal with compare to, say, the Macintosh GUI as that
GUI is compared to JCL. That is, the interface must be capable of
understanding the concepts behind presenting information -- avoiding
overloading, having a variety of methods of presentation (graphical, text,
combinations, and refinements thereof) available and some ability to choose
the appropriate method for displaying a given set of data, and so on.
Some of the data it might display would include that traditionally thought
of, i.e. sample input data for the program and/or the various incarnations it
has as it goes through transformations within the program. But the compiler
would also need to be able to display various interpretations of the program
itself: a representation of the data flow through a given portion of code, a
picture of where various key data sets are kept in memory (global, local,
register; virtual memory, wired/locked memory, or fast static RAM for a
system that can exploit such differences; whatever), which implementation
model is chosen for the optimized version of a given module, and so on.
Various views of the same code/data could be selected by the programmer, but
more importantly, the programmer would be able to interact with these views
to refine or annotate the information.
Refining the information might be useful when the optimizer picks a general
optimization but has at its disposal several refined versions of that
optimization, each of which goes faster than the general version. The
programmer could provide a direct suggestion that a particular refinement is
or should be valid, and the system, without having had to search all the
possible refinements itself, could verify (or trust) that the chosen
refinement is indeed correct.
Annotating the information is useful when the programmer wants to note that,
for example, "WORKARRAY should not be in global virtual memory" while working
through the allocation views of the data of the program, and this annotation
is forwarded to other views (such as the source code) so, later, the
programmer can easily find operations on the pertinent item that might
explain how it ended up that way. The annotation might even be active (vs.
a passive "comment") in that it might "yell" at the programmer when a change
he/she makes satisfies its constraint: for example, after making a change, a
message might be sent saying "Congratulations! WORKARRAY is now in fast
static RAM".
Further, this system would keep information on the program in a persistent
fashion so the information would not have to be entered again and again. To
do that, it would be best for the system to serve as the "source editor", and
be capable of recognizing when its current categorizations of a given chunk
of code (at whatever level of granularity) were no longer applicable due to
changes in the code, and forwarding information on changes to other chunks of
code that held a "vested interest" in the changed code.
Finally, this system would not spring forward whole from someone's forehead;
it would have to have an underlying kernel language on which the system as a
whole could be incrementally built. In fact, I don't envision the kernel as
a compiler or anything in particular; it would more resemble something like a
hybrid of EMACS and Smalltalk, but very stripped down and carefully planned.
A library of often-used components involving compilation, optimization,
editing, and such would become ubiquitous just as has happened with those two
systems, and this library would grow. But many programmers would wish to,
and could easily, extend the system as desired to take into account their own
special needs (target hardware, programming languages, and so on). All of
the source code of the system should thus be made available to anyone who
wants it (a la the Free Software Foundation's GNU Public License).
The output of the system? Whatever is needed: assembly, C, C++, are
examples, but I don't see any limitations here. In fact, one could possibly
output final executables when doing global compilation and optimization,
meaning that some pretty neat optimizations some of us wish we could stick in
the linker we're using would be doable, given that we'd "rewritten" the
linker to run under this proposed system.
I think this approach may be one of the more fundamental changes in
optimization technology over the next decade or so: not because it introduces
any sexy new optimizations per se, but because it permits programmers to
easily pick apart their own creations and put them back together, without
having to rewrite the source code if desired. Such a system might allow the
industry to move back to powerful languages that "hide" potent but often
expensive operations in innocuous-looking constructs (a problem with
lanaguges like PL/I that C lovers like to point out, and which is valid on a
practical level), since the expense would be easily discoverable during the
"optimization discovery" process offered by the proposed system.
I won't get into how such a system might also provide an easier means for
debugging systems (even in "optimized" mode), writing source code (harking
back to the "what if we had a language of languages?" thread we had earlier),
or improving verifiability. As with optimization, the system itself would
break no new ground in these areas, but should provide a more fertile field
for implementing and discovering improvements in them.
After I get through with GNU Fortran, I'd like to start trying to build such
a system, so I hope that if anyone knows why it can't work, they'll let me
know before then! (-: (Seriously, either this is a great idea that I have to
do someday, or there's something for me to learn from its failure, either way
I decided pursuing this and other ideas was more important than drawing a
full-time paycheck and working on the same old thing, which is why I left my
job over a year ago...so is this idea worth pursuing as one of my next
projects? After watching the newsgroups for a while, this seems to be a good
one to ask!)
James Craig Burley, Software Craftsperson burley@world.std.com
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.baxter@zola.ICS.UCI.EDU (Ira Baxter) (10/24/90)
There has been considerable discussion of optimization using "symbolic algebra" techniques: >In article <1990Oct18.223231.22315@esegue.segue.boston.ma.us> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > Does anyone have a compiler that can introduce a non-linear intermediate > expression and reduce around it? If so, I'm impressed. How advanced is > the symbolic algebra system included in the compiler? Can it take > advantage of range constraints, so that if it knows that x is between 0 > and 7, it might set up a table to calculate ((1<<(x+2))-1)/10 quickly? > Can it manipulate floor and ceiling expressions? Can it introduce > invariants to figure out range constraints? These are all part of that > single, fundamental optimization technique. > I know, compilers are improving. Some optimizers fully automate the > dullest, most machine-dependent part of optimization---viz., figuring > out how often loops or branches are executed in practice, seeing how > long machine instructions take, and deciding on that basis whether a > given optimization is worthwhile. I really appreciate that. I won't stop > hand optimization because of it. An approach to "optimizing" is that of transformation systems: Use a tool based solely on "symbolic algebra", usually called a set of correctness-preserving transformations (cpts), to modify the source or to refine it to more-machine like representations. This process is intended to be semi-automatic; a very good overview article can be found in Balzer85a:TI-perspective. The semi- part comes about because people will always know more about their problem than any fixed set of cpts will, and so interaction is necessary to tell the system that certian optimizations are legal for this program. Recent transformation systems are in fact founded on the notion that the software engineer, as part of his duties, should in fact formally define such algebras as a basis for the transformations used. Check out the CIP (Bauer:CIP-volume) and PROSPECTRA (Krieg-Bruckner88a:PROSPECTRA-overview) systems. In these systems, the SE can actually compose algebraic facts to make transformations specific to his purposes. Hand-optimizations are nice, but mean that the original abstract program gets lost (come, now, you didn't *really* keep the original source did you?) and later modifications become that much more difficult. The transformational approach to this is to generate some sequence of transformations, some automatically, some by hand, and to keep the sequence for later replay when the specification is modified. This is currently a hot research topic. Playing the perfect shill <BURLEY.90Oct20081629@world.std.com> burley@world.std.com (James C Burley) writes: >[...visions about an interactive compiler...] >Further, this system would keep information on the program in a persistent >fashion so the information would not have to be entered again and again. To >do that, it would be best for the system to serve as the "source editor", and >be capable of recognizing when its current categorizations of a given chunk >of code (at whatever level of granularity) were no longer applicable due to >changes in the code, and forwarding information on changes to other chunks of >code that held a "vested interest" in the changed code. >I think this approach may be one of the more fundamental changes in >optimization technology over the next decade or so: not because it introduces >any sexy new optimizations per se, but because it permits programmers to >easily pick apart their own creations and put them back together, without >having to rewrite the source code if desired. Such a system might allow the >industry to move back to powerful languages that "hide" potent but often >expensive operations in innocuous-looking constructs (a problem with >lanaguges like PL/I that C lovers like to point out, and which is valid on a >practical level), since the expense would be easily discoverable during the >"optimization discovery" process offered by the proposed system. With that modest :-} :-} introduction, I introduce my own work, which effectively does just this; see Baxter90a. In particular, it takes specifcation deltas (source changes), and determines how those changes affect the set of optimizations already applied, retaining those that it can, dropping those that conflict. Now, having raised your hopes enormously, I must also dash them a bit. This is research; I have pursued the ideas and demonstrated that they work on *very* small examples. It will take several years to seriously scale up. @phdthesis(Baxter90a:thesis-transformational-maintenance, title = "Transformational Maintenance by Reuse of Design Histories", author = "Ira D. Baxter", department = "Information and Computer Science Department", school = "University of California at Irvine", month = nov, <<<< note this year = 1990, @article(Balzer85a:TI-perspective, title = "{A 15 Year Perspective on Automatic Programming}", author = "Robert Balzer", journal = "IEEE Transactions on Software Engineering", volume = "SE-11", number = "11", month = nov, year = 1985, pages = "1257-1268", @book(Bauer87a:CIP-volume, author = "F. L. Bauer and H. Ehler and A. Horsch and B. Moller and H. Partsch and O. Paukner and P. Pepper", title = "{The Munich Project CIP}", publisher = "Springer-Verlag", year = 1987, note = "Lecture Notes in Computer Science 292", @inproceedings(Krieg-Bruckner88a:PROSPECTRA-overview, author = "Bernd Krieg-Bruckner", title = "{The {PROSPECTRA} Methodology of Program Development}", booktitle = "{IFIP/IFAC Working Conference on Hardware and Software for Real Time Process Control}", publisher = "North-Holland, New York", address = "Warsaw, Poland", pages = "1-15", year = 1988, -- Ira Baxter -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
daveg@near.cs.caltech.edu (Dave Gillespie) (10/24/90)
>>>>> On 20 Oct 90 07:16:29 GMT, burley@world.std.com (James C Burley) said: > What I think is really needed is not only a compiler (here I refer to the > total package of translating, including linking and debugging) that can > recognize and deal with the kinds of optimizations Dan talks about, but that > is easy to interact with, converse with, and to which the programmer can > easily explain other constraints and point out other optimizations worth > trying. One way to start toward your grand plan would be to have the compiler output a file of "I wish I had the following asserts/pragmas" notes correlated with line numbers. A smart editor, maybe a major mode in GNU Emacs, could go back and filter these into the original code in the form of comments. The user would then know that, if he/she uncommented one of these pragmas (after checking that it was safe to do so, of course), the optimizer would be able to improve the code significantly. Most of the things a good optimizer would like to know can be phrased as assertions, or can probably be described in a suitable language of pragmas. The advantage here is that these assertions are likely to remain meaningful even as the code later evolves. If the compiler sees an assertion that no longer makes any sense (say, because parsing it produces an error of some kind) it can tell the editor to flag it for the programmer's attention. It should also be possible to format these notes in a way that causes the editor to treat them as invisible. (GNU Emacs has facilities for this right now.) If the compiler puts up a "sure would be nice if X were nonnegative" note and I determine that, in fact, X *won't* always be nonnegative, I'd like to hide the note rather than deleting it so that it won't keep popping up again. It's important to get rid of it *somehow* so that there won't be pressure on the compiler not to generate as many notes as it can think of. I only have to hide them once and forget about them. Some day if I need to squeeze a certain routine some more I can go back and unhide its note to see if any of them can be made to apply by massaging the rest of the program. Other notes that I'd like to be able to give to a compiler are "please optimize this function to death", "this `if' condition is rarely true", and so on. The former note would, among other things, trigger the generation of lots more "I wish" notes from the compiler. -- Dave -- Dave Gillespie 256-80 Caltech Pasadena CA USA 91125 daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.