Just rambling about optimization...

[Richard Harter]

In article <721 at taumet.com>, steve at taumet.com (Stephen Clamage) writes:

> I'm not surprised.  It is of very little use.  Gains in performance at
> the source code level are best achieved by choosing better algorithms.
> Reliable optimizations achievable by source code manipulation as you
> describe are done anyway by quality compilers....

Stephen's advice is good and generally sound.  I just want to add some
qualifiers.

One is that there are quite a few local optimizations that lots of
compilers don't seem to catch.  A key point is that quite often you
know more about the constraints than the compiler can assume.

A more general point is that the advice to "choose better algorithms"
is a bit misleading, although true if we take "algorithm" in its most
general sense.  When one thinks of algorithms one tends to think of
algorithms in the abstract, e.g. sort algorithms, search algorithms,
etc.  Stephen's advice can lead to one trying to pick optimal algorithms
which are then glued together.  However a major cost in many programs
is the glue, i.e. the data management and interfaces.  For example

fooby(...) {... p =malloc(n); ... free(p);}

calls malloc and free in each invocation.  If fooby is not recursive
(so that there is a stack of malloc calls) we gain with

static char *p = 0;
static int sizeof_p = 0;
fooby(...) {
	if (n>sizeof_p) {
		if (p) free(p);
		p = malloc(n);
		sizeof_p = n;
		}
	....
	}

This is a space/time tradeoff.  We keep a permanent array (using space
when not in fooby) and eliminate malloc/free calls in all but a few
calls to fooby.  There are lots of instances where well chosen data
structures let you avoid the cost of copying by setting pointers.
The point is that optimization of programs frequently involves better
design of the data management process.
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.