malloc(3) vs. malloc(3x)

[Chris Torek]

In article <1818 at hp-sdd.HP.COM> tony at hp-sdd.hp.com (Tony Parkhurst)
writes a nice explanation of why there are Too Many Mallocs (with
apologies to ... to ... well, I know I stole% the phrase from somewhere!).
But it does not quite tell why Robert Seals got the results he did.

-----
% `Lesser artists borrow.  Great artists steal.'  (And I have forgotton
who said that, too!  This is not my night....)
-----

>So, to implement new versions of malloc(), BSD has one that someone put
>much effort into preserving the compatibility and has a higher performance
>(relative since this is in user context anyway), and is more efficient with
>usage of smaller blocks.  It is bucket pool type of implementation.

The new malloc was originally written by Chris Kingsley, then at Caltech.
It is extremely fast, but rather wasteful of space.  It has one notable
`feature': it never coalesces small blocks, and it never breaks up
large blocks.  Since it rounds up each request to the nearest power of two,
a sequence like:

	for (i = 10000;; i <<= 1) {
		if ((p = malloc(i)) == NULL)
			break;
		free(p);
	}

winds up allocating one 16384-byte block (for malloc(10000)), one
32768-byte block (for malloc(20000)), one 65536-byte block (40000), one
131072-byte block (80000), and so forth.  After these first four
allocations, your process has consumed not 80000 bytes of its limit (as
shown by the csh `limit' built-in), but rather (32+64+128)*1024 =
229376 bytes.  But it has done so very efficiently: only three
pages have actually been touched, so only three pages have really
been created.  The rest is all merely virtual space (swap backing)
and PTEs.

Various people have submitted modified versions of the Caltech malloc
to Berkeley, some of which can scavenge some of the space currently
wasted.  John Linderman (allegra!jpl) probably did the most thorough
of these.  For whatever reasons, the changes have never been installed.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris