Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!sun-barr!newstop!exodus!rbbb.Eng.Sun.COM!chased From: chased@rbbb.Eng.Sun.COM (David Chase) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: <1493@exodus.Eng.Sun.COM> Date: 18 Oct 90 18:27:29 GMT References: <65697@lanl.gov> <1458@exodus.Eng.Sun.COM> <13405:Oct1800:22:5690@kramden.acf.nyu.edu> Sender: news@exodus.Eng.Sun.COM Organization: Sun Microsystems, Mt. View, Ca. Lines: 58 In article <13405:Oct1800:22:5690@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >First releases of optimizers simply don't work; after they've spent a >few years on the market, their bugs are few and far between. Maybe one >bug per ten thousand lines of code, after a year of maturity. It goes >down quickly past that. Do you have documentation to back this figure up? I do not believe it; I've used beta-test compilers from more than one vendor, and they largely worked. When they didn't work, ALL the bugs I found were fixed before the compiler was released to customers. There's test suites in abundance for Fortran, C, and Ada -- it's elementary, though tedious, to be sure that a compiler passes everything in a test suite. > [ example of code: 30x faster from better algorithms, etc., in ] > [ several weeks, 1.7x faster from optimizer in a couple of minutes ] > >But I can usually get another 2x to 5x out of lots of ``picky'' hand >optimizations, having nothing to do with the algorithms. And I'm not >going to introduce subtle bugs in weird cases with unsafe program >transformations. You didn't read the posting clearly enough (or else I deleted the details for brevity). Better algorithms, high-level hand optimization (i.e., malloc, memoization), low-level hand-optimization (unrolling, inlining, stuff that optimizing compilers will do automatically for me today) all contributed to that speedup. (The grand total was a factor of 250, which has since been improved to about 400 because of other algorithmic improvements). Even so, there was still another factor of 1.6 to be had by the compiler's optimizations. In general, I find that my uncaught error rate for typing is higher than the bug rate for modern optimizing compilers. I think this is true for most people. Furthermore, even if I could do the transformations without thinking, it takes more time for me to type in the transformations than it does for the compiler to do the optimizations. And, it is not the intention that optimizing compilers do unsafe program transformations -- when they do, it is a bug. Hold that thought -- a transformation is not considered unless it is safe. People don't publish papers on "transformations that usually work". The wholesale rearrangements that expose parallelism and enhance locality are based on sound theory, are incredibly tedious to do by hand (the resulting program is often unrecognizeable), and can yield fabulous increases in speed. Other transformations are completely unavailable at the source level (can you schedule instructions between the fetch, increment, and store required to implement "x++" on a RISC machine?) and produce solid improvements in speed. Perhaps I'm missing something -- I claim, I believe correctly, that modern optimizing compilers improve code quality (at the *low level*) faster, more effectively, and with a lower error rate than I could ever hope to attain by hand (doing the *same* optimizations). What's wrong with using such an excellent tool? What awful property of optimizing compilers have I missed? David Chase Sun Microsystems