Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!zaphod.mps.ohio-state.edu!think!snorkelwacker!bloom-beacon!eru!luth!sunic!mcsun!ukc!dcl-cs!aber-cs!rupert!pcg From: pcg@rupert.cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: Common subexpression optimization Message-ID: Date: 5 Feb 90 18:34:07 GMT References: <4561@scolex.sco.COM> <14214@lambda.UUCP> <2217@sunset.MATH.UCLA.EDU> <4466@brazos.Rice.edu> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 122 In-reply-to: preston@titan.rice.edu's message of 2 Feb 90 01:14:48 GMT In article <4466@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: In article pcg@rupert.cs.aber.ac.uk (Piercarlo Grandi) writes: He also gives some examples of how we might notate matrix multiplication so that a comparitively simple compiler can generate good code. Here is the keyword: *simple*. I don't like complex compilers that second guess me. I like *simple*, obedient, compilers. Simplicity is the path to reliability and economy. These seem to be lost esoteric arts :-(. My impression has been that the generality of Algol-68 prohibits efficient code. Nevertheless, the example is interesting. Algol68 is difficult to *parse*, but it has been carefully designed to make efficient code possible, and indeed even easy. Array slicing, for example, is there for this reason, as are other things. Too bad that something like 'fast' is missing (but 'ronly' is there). Note that we'd also like to see m*4 in a register (assuming row major array ordering and 4 bytes/word) and k itself eliminated. The point being that the "fast" hint has some perhaps unexpected side-effects. In C this is done by stepping a pointer thru an array. Well, I was assuming a more conventional language. The idea that C pointer arithmetic is automatically scaled is another win. If you'd throw out the "ronly" and "fast" hints, I'd say these forms aren't too bad. Why do you need to say "ronly" when it's fairly obvious to the compiler that h and h_i are not assigned? These hints seem like non-abstract intrusions into the middle of otherwise fairly declarative code. I like them because they document assumptions by the programmer both to human and compiler reader. Both can check them and exploit them. A program should also document such assumptions, not just the algorithm. This is the major problem I have for example with Dijkstra; his books are really about algorithm design, thinly veiled as programs, not programming. Programming is a hands on job. Economics *are* important. A "programmer" will carefully shape an SQL query (and SQL as a language is quite non procedural and pure) so that it will be the most efficient of those with equivalent results, taking into account the query optimization strategies of the fron tend and the performance characterization of the DB engine and of the configuration of the machine. The query optimizer will tend to do a good job done, but for *important* large queries, the programmer will know better, having more information and insight (hopefully!). The theme is where the point of diminishing returns is, not whether the compiler can extract a further X% speedup from a source that the programmer has not described carefully as to pragmatics. If a *simple* compiler can get 90% of source lines fast enough, and there is a steep cost in compiler complexity to have it optimize an extra 5%, and the remaining 5% requires real intelligence, the tradeoff is clear. [ ... about compiling a high level notation into a lower level one and applying optimizations to this ... ] Note the seperation of concerns. Enforcing the language in the front end, improvement (without changing the meaning of the program) in the middle, and concern for the machine details in the back end. Not bad. In outline I tend to agree. So what happened to the "fast" hints (and register declarations in C)? They get thrown out. It's easier, more effective, and more complete to Let me disagree. "more effective" is a strong statement. Armchair evidence tends to point out that current highly optimizing compilers get better results with "register" declarations (some flimsy data points: dhrystones, the matrix multiplication example recoded in C, etc...). This tallies with the expectation that most of the hairy optimization is about irrelevant pieces of code anyhow, and that current widely available optimizer technology does not take into account *dynamic* usage, and thus does not know which are the hot spots. There are heuristics or profiler feedback optimizers around already, but I tend to delude myself that programmers can do the same job more intelligently and reliably, in the few spots where it is necessary. discover opportunities for optimization during the latter stages of compilation. On this let me disagree too. The hints should not get thrown out; they are valuable, *quality* information. The compiler writer should not believe that it can (reliably!) second guess the author as to the semantic/pragmatic properties of the program. The author should describe them as clearly as possible, and the compiler should treasure such information. Of course the author should be spared (not always! if it is *really* important, machine dependent considerations should enter into the design of a program) the work of machine dependent optimization (which is actually just competent code generation), because there the compiler is in charge. In other words, this means that most compiler optimizations should be about space, because this is what a code generator has direct control on and knowledge of, and instruction reordering, and other architecture dependent details. I'd cleaim that this approach results in clearer programs, and in simpler, faster, more reliable compilers, and object speed need not suffer, quite the opposite. -- Piercarlo "Peter" Grandi | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcvax!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk