Xref: utzoo comp.arch:17061 comp.lang.misc:5144
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!ballen
From: ballen@csd4.csd.uwm.edu (Bruce Allen)
Newsgroups: comp.arch,comp.lang.misc
Subject: Re: Compiler Costs
Message-ID: <4986@uwm.edu>
Date: 11 Jul 90 22:15:36 GMT
References: <1797@apctrc.UUCP> <1990Jul6.185248.12191@cl.cam.ac.uk>
Sender: news@uwm.edu
Reply-To: ballen@csd4.csd.uwm.edu (Bruce Allen)
Followup-To: comp.arch
Organization: University of Wisconsin-Milwaukee
Lines: 21

There is a nice discussion of the relative speedups that can be obtained
by various kinds of optimization in "Writing efficient programs"
by Jon Bentley (Prentice-Hall Software Series, 1982).

In two examples, discussed in detail by Bentley (pgs 26-28 and 130)
the speedup obtained in hand-coding in machine-language was a factor
of 2 in one case and a factor of 5 in the other case.  The latter
case was one in which the machine had a particularly well-suited
instruction, the former case is more typical.

The major lesson that one gets from Bentley's book is that almost
all the significant speedups are obtained in designing data
structures, algorithms, and general good coding.  In this book
many examples are given of "typical" code being speeded up by
factors of ten or more just by careful rewriting of high-level
code.

I think this is an excellent, fun-to-read book. Anyone who has not
looked at this book should peruse it the next time they're in a 
good bookstore (if you don't get distracted by "Programming Pearls",
by the same author, just next to it!).