Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!caen!uakari.primate.wisc.edu!samsung!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: Date: 1 Nov 90 17:12:10 GMT References: <2301@wn1.sci.kun.nl> <8960018@hpfcso.HP.COM> <1990Oct30.105241.9733@tkou02.enet.dec.com> <1849@exodus.Eng.Sun.COM> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 150 Nntp-Posting-Host: odin In-reply-to: chased@rbbb.Eng.Sun.COM's message of 30 Oct 90 21:22:38 GMT On 30 Oct 90 21:22:38 GMT, chased@rbbb.Eng.Sun.COM (David Chase) said: chased> diamond@tkou02.enet.dec.com (diamond@tkovoa) writes: diamond> C was invented in order to be that better assembler. If you diamond> want machine level, you're supposed to program in C. That is diamond> exactly the purpose for which C was created. If you want an diamond> HLL, use one; don't cripple C. chased> This may be true for (one dialect of) pre-ANSI C, but the chased> specification of ANSI C allows (if you don't say "volatile") a chased> large number of entertaining optimizing transformations, despite chased> assertions by you and other posters here that C is a "low level chased> language" and "low level languages ought not be aggressively chased> optimized". Haha. Never said that low level *languages* should not be optimized. We are saying that *programs* in low level languages (or indeed in any language) should not be optimized. I have decided to stick out my neck again and try to define better what is aggressive optimization. When you have a language it has a set of primitive operators (+,*,...) and of primitive operator combinators (if, ;, procedures, ...). The language definition prescribes the effect of the primitive operators and an algebra for such effects defined by the combinators. In a way or another this implies that each language implies a virtual machine. The task of the code generator is to map the virtual machine onto the real machine as well as it can, which means faithfully (semantics) and efficiently (pragmatics). Optimization is doing the mapping from the virtual machine defined by the language to the real machine in a clever (i.e. optimal for the target real machine) instead of a straightforward way. A program in some language, at any level of abstraction, defines an higher level virtual machine than that offered by the language. The primitives of the virtual machine defined by a program (most obviously, but only, its procedures and macros) are actually composed out of the primitives and combinators of the language, and their meaning is defined according to the algebra for these as given in the language definition. Aggressive optimization is mapping from the virtual machine defined by the program (not by the language!) to the real machine *in the code generator*. This is in way of principle possible, because the code generator can indeed recognize combinations of primitive operators and rewrite them to other combinations that supposedly map better onto the target real machine, as long as the two are equivalent under the algebra of the language definition, in that particular context. The problems are: Is this desirable? No, because the rewriting algebra of the language may be poorly defined, or poorly understood, and thus it may be difficult to rely on the ability of the code generator to rewrite combinations of language primitives in semantics preserving ways. This is particularly true for languages like C, where a clean algebra for rewriting was not a design goal. Ansi C have tried to do some poor fixup engineering on this. We are not amused. No, because even assuming that the underlying algebra is clean, rewriting combinations of primitives is a far more concpetually difficult task than mapping each of them to the real machine. In particular it requires careful analysis. Such analysis tends to result in more bugs in the compiler, and the compiler is the bottleneck of an entire system's reliability. No, because even if two combinations of primitives can actually be shown in the given context to be equivaltn according to the language's algebra, it ought to be assumed that the programmer intended to write the particular one he chose to write for some good reason. No, because the speed advantages are not that dramatic (or nonexistent), *if* the author is a clever programmer that knows which of the equivalent formaulations will be optimal on the given machine. Are there alternatives? Yes, rewriting the combinations of primitives not in the code generator, but at the source code level, either manually or automatically. Yes, using a language whose primitives are at the abstraction level desired, i.e. the primitives offered by the language are those needed for the application. In this case the optimization is not aggressive, because the generator is only doing optimal implementation of hopefully well defined language primitives, not supposedly optimal rewriting of pieces of a user program. Are the alternatives cost effective? Yes, because for *many* even if not all codes the time critical portion is small enough that careful automatic rewriting is feasible. Yes, because automatic rewriting can be to a higher level language, which can then be more easily and non aggressively optimized, and automatic rewriting gives long lasting benefits in portability and confidence in the program. Yes, because using a language whose primitives are at the level of the problem is known to reduce costs and improve quality via reuse of the language's implementation or libraries, where otherwise the implementation of thsoe primitives would have to be rewritten and re-aggressively optimized for every application. Yes, because it separates the compiler from the code rewriter, which are two modules with very different goals and very different reliability profiles. chased> C *is* a low level language, but the optimizations are 100% chased> legal, often tend to make the code go faster, and thus they are chased> applied. They are legal but dangerous and not cost effective, according to the above discussion. chased> The compiler-writer's claim is "I can prove that these chased> optimizations conform to the standard"; STOP THE PRESSES! Compiler writer proves that he can do program rewriting in a bug free way! Program synthethizers must be round the corner! Major software companies stocks collapse! chased> can you *prove* that they should not be done? How will it sell chased> more computers/compilers to NOT do the transformations? (Lest chased> you forget, dollars and cents is what it all comes to in the chased> end.) The argument is that it is not *cost effective* for *users* of compilers to pay for program rewriting in the code generator. They may require a little education to acknowledge this, just like smokers. In the mean time the tobacco industry has every incentive to educate the customers to the contrary... -- Piercarlo "Peter" Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk