Path: utzoo!attcan!uunet!tank!uxc!uwmcsd1!ig!bionet!apple!rutgers!att!ihnp4!poseidon!psrc
From: psrc@poseidon.UUCP (Paul S. R. Chisholm)
Newsgroups: comp.lang.c
Subject: Re: memory allocation
Summary: optimize for common structures
Message-ID: <499@poseidon.UUCP>
Date: 13 Sep 88 14:33:41 GMT
References: <1262@micomvax.UUCP>
Distribution: comp.lang.c,comp.os.misc
Organization: AT&T Bell Laboratories
Lines: 64

< "NO toon can resist the old shave-and-a-haircut gag!" >

In article <1262@micomvax.UUCP>, belanger@micomvax.UUCP (Robert Belanger) writes:
> We are in the process of speeding up memory allocation. . . .  What
> we want to do is avoid any system in order to speed up memory
> allocation and also reduce the overhead associated with memory
> allocation. . . .
>Rober L. Belanger, philabs!micomvax!belanger

Consider this war story (private communication from Chris Van Wyk to
Jon Louis Bentley, and quoted in the latter's WRITING EFFICIENT
PROGRAMS, p. 37):

	My interpreter for IDEAL seemed to be awfully slow and to take
	a lot of space, so I profiled its execution.  It turned out
	that over a sample of ten test cases that exercise every part
	of the code, it was spending almost seventy percent of its time
	in the system's memory allocator!

	Further investigation revealed that most of this was used in
	allocating one particular kind of node (more than 68,000 times,
	with the next most particular node being allocated around 2,000
	times).  I added the minimal bookkeeping necessary to keep my
	own queue of free nodes of this particular kind, and reduced
	the memory allocator's share of the time to about thirty
	percent.

	There were three benefits of this change:

	1.  less time in the allocator (it's a circular list with a
	roving pointer,

	2.  less memory fragmentation (our allocator doesn't compact),
	and

	3.  now that the statistics aren't overwhelmed by the
	allocator's share, I can find places that need to be sped up
	with sophisticated algorithms or data structures.

	On the other hand, it would not be worth my time to provide my
	own bookkeeping for every kind of node I allocate, so I save
	programming effort on another front.

The key point here is that Van Wyk measured his program (with a
non-trivial test input), found where the program spent its time, and
*then* optimized it.

(Bentley gives another example, a Fortran compiler that had an
extremely slow routine.  The programmer spent a week speeding that one
routine up.  Ten years later, someone reported a bug; guess where?
Looking back at the code, the programmer realized that this routine
*never* worked, and must never have been called previously in ten
years of use!)

Bentley, Jon Louis, WRITING EFFICIENT PROGRAMS, Prentice-Hall,
Englewood Cliffs, NJ, 1982.  ISBN 0-13-970251-2, 0-13-970244-X (pbk).
A nice collection of ways of making software faster, smaller, or both,
with examples and real-world "war stories".  There may not be anything
you've never heard, but they're collected in one volume, and easy to
read.

Paul S. R. Chisholm, psrc@poseidon.att.com (formerly psc@lznv.att.com)
AT&T Bell Laboratories, att!poseidon!psrc, AT&T Mail !psrchisholm
I'm not speaking for the company, I'm just speaking my mind.