Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!ulysses!kpv
From: kpv@ulysses.homer.nj.att.com (Phong Vo[drew])
Newsgroups: comp.lang.c
Subject: Re: Memory Allocation (was Re: binary data files)
Summary: a good malloc does exist
Message-ID: <11486@ulysses.homer.nj.att.com>
Date: 4 May 89 15:39:34 GMT
References: <10946@bloom-beacon.MIT.EDU> <12546@ut-emx.UUCP> <10202@smoke.BRL.MIL>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 27

In article <10202@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes:
> In article <1989May3.201118.10221@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes:
> >In article <17252@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes:
> >>I get the feeling that some future BSD will have six different malloc
> >>library routines. . . .
> >It would be too much to ask for one *good* one!  :-) :-(
> 
> Most applications that really care about malloc() efficiency have already
> given up and implemented their own technique, using malloc() simply as an
> sbrk() surrogate.

The old malloc was based on a simple first-fit strategy with a roving pointer.
It is intolerably slow when a process needs to to many mallocs (say thousands
or tens of thousands). The recent BSD malloc is based on a power of 2 buddy
system. It is fast but wastes lots of space. The effect of wasting space is
that in many systems (like bitmap graphics programs) where many mallocs is
typical, you can run out of space even with virtual memory. Worse than that
is wasted time due to the number of page faults when data are accessed frequently.
This is a subtlety that is frequently missed when people run tests on malloc.
There is a paper that Dave Korn and I presented at the 85 Summer Usenix in
Portland Oregon that gave comparative testing results of many versions of malloc.
Sad to say, we also missed the above subtlety in the paper.
However, one can go a long way toward making a compromise between having good
time behavior and good space behavior. Locally, we've been having good
success with a modified version of the best-fit based algorithm presented
in that paper.
	Phong Vo, ulysses!kpv