Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!ames!elroy!cit-vax!mangler
From: mangler@cit-vax.Caltech.Edu (Don Speck)
Newsgroups: comp.unix.questions
Subject: Re: malloc(3) vs. malloc(3x)
Keywords: ultrix, 4.3-tahoe
Message-ID: <9316@cit-vax.Caltech.Edu>
Date: 28 Jan 89 08:47:17 GMT
References: <1418@leah.Albany.Edu> <1818@hp-sdd.HP.COM> <15365@mimsy.UUCP>
Reply-To: almes@rice.edu
Organization: California Institute of Technology
Lines: 31

In article <15365@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes:
> The new malloc was originally written by Chris Kingsley, then at Caltech.
> It is extremely fast, but rather wasteful of space.

He wrote it in 1982 for a VLSI layout langauge interpreter which
allocated hundreds of thousands of objects with an average size of
32 bytes with about 2/3 as many free's as malloc's, growing at a
rate of typically a megabyte per minute.  No attempt was made to
leave recently-freed blocks intact.  It was really quite simple.

When I diff'd the version we had against the 4.2 BSD one, it was
clear that major additions had been made to support the storage
compaction semantics documented in malloc(3).  I recall a scathing
critique of dead code, spurious comments, etc. in Unix-Wizards
years ago, none of which was Chris's fault.

This all fell in my lap, and as our chips grew to need more than
16 megabytes, I had to switch to something less wasteful of memory.
From University of Washington came a malloc that beat Chris's allocator
in CPU time, memory, and page faults.  Here's the identifying comments.
"whois" says that the author's current address is almes@rice.edu.  Don't
make me feel bad by asking me for the code.  Try asking the author.

/*  An implementation of malloc(3), free(3) using the QuickFit method.
 *  Guy Almes, May 1983.
 *
 *  Cf. MALLOC(3) in the Unix manual for external specifications.
 *
 *  Cf. Chuck Weinstock's PhD thesis for a discussion of the techniques
 *  used.  (Charles Weinstock, Dynamic Storage Allocation Techniques,
 *  April 1976, CMU)