malloc(3) vs. malloc(3x)

[Don Speck]

In article <15365 at mimsy.UUCP>, chris at 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 at 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)