Memory Allocation (was Re: binary data files)

[Phong Vo[drew]]

In article <10202 at smoke.BRL.MIL>, gwyn at smoke.BRL.MIL (Doug Gwyn) writes:
> In article <1989May3.201118.10221 at utzoo.uucp> henry at utzoo.uucp (Henry Spencer) writes:
> >In article <17252 at mimsy.UUCP> chris at 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