From: utzoo!decvax!harpo!seismo!hao!hplabs!sri-unix!sch@MITRE-BEDFORD
Newsgroups: net.unix-wizards
Title: Re: compaction using realloc
Article-I.D.: sri-unix.4829
Posted: Wed Dec 15 00:18:10 1982
Received: Sat Dec 18 22:27:26 1982

Date: Fri Dec 10 08:41:50 1982
The strategy used by malloc/free/realloc is a first fit method.  You are
suggesting using a best fit instead.  I believe if you do a study of the
literature (Knuth), you will find that there is a trade off here.  If you
use best fit (as you suggested) then the routine has to search all possible
blocks (slower), and many small chunks get allocated and never can be reused.

The whole allocation strategy of malloc does break down for large programs
on virtual memory systems like a vax.  Berkeley knows know about this I don't
no what their future solutions will be.

I agree with your general comment that one should not depend on the behaviour
of malloc returning the previously freed block.   Rather than changing
malloc/free, a new set of subroutines which do allocation but also garbage
collection would be handy.  These routines would have to return a pointer
to a pointer (char **) so the routine could move blocks around for garbage
collection.  Has anyone implemented such routines?

			Stephen Hemminger
			sch @ mitre-bedford