Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!sci.kun.nl!cs.kun.nl!eerke From: eerke@cs.kun.nl (Eerke Boiten) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: <2301@wn1.sci.kun.nl> Date: 18 Oct 90 09:38:29 GMT References: <65697@lanl.gov> <1458@exodus.Eng.Sun.COM> <13405:Oct1800:22:5690@kramden.acf.nyu.edu> Sender: root@sci.kun.nl Organization: University of Nijmegen, The Netherlands Lines: 36 In article <13405:Oct1800:22:5690@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I do not remember ever making a mistake in hand optimization by the most >fundamental standard technique: adding variable x to keep track of some >intermediate quantity, and eliminating redundant variables given x. What >optimizer can do this for any but the most primitive intermediate >expressions? (Introducing a pointer to traverse an array, and >eliminating the index that it replaces, is the simplest example.) A useful technique, indeed (called "strength reduction" in optimising compilers, "finite differencing" in transformational programming). Surprisingly :-), it's one of the first things I learned in the course on optimising compilers I followed as a masters student. Of course, *the* example is going through a (multi-dimensional) array. >Somehow I don't think we have the technology yet. Somehow I can't imagine this has never been implemented, considering how long it's been known. >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? Of course, finite differencing is relatively safe since you introduce redundant information most of the time. It's the process of *removing* (supposedly) redundant information that might very well cause many bugs. By the way, there *are* systems that help you in applying source-level optimisations. Just make sure that your transformations are correct (only once!), and they preserve the set of bugs in your program, when applied. 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