Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!tut.cis.ohio-state.edu!purdue!haven!umd5!crabcake!zhu
From: zhu@crabcake.cs.jhu.edu (Benjamin Zhu)
Newsgroups: comp.lang.c
Subject: Re: malloc/free question
Message-ID: <1322@crabcake>
Date: 2 May 90 16:04:11 GMT
References: <2638831C.728C@telly.on.ca> <271@caslon.cs.arizona.edu> <ZR33D0Cggpc2@ficc.uu.net> <14320@levels.sait.edu.au> <15873@phoenix.Princeton.EDU> <15902@phoenix.Princeton.EDU>
Reply-To: zhu@crabcake.cs.jhu.edu (Benjamin Zhu)
Followup-To: comp.lang.c
Organization: Johns Hopkins University CS Dept. -- Town of Solitude
Lines: 46

In article <15902@phoenix.Princeton.EDU> pfalstad@phoenix.Princeton.EDU (Paul John Falstad) writes:
>In article <15873@phoenix.Princeton.EDU> some idiot whose name
>coincidentally happens to resemble mine writes:
>>In article <14320@levels.sait.edu.au> CCDN@levels.sait.edu.au (david newall) writes:
>>>peter@ficc.uu.net (Peter da Silva) writes:
>>They do say that their allocator looks for the "first fit," and not the
>>"best fit;" that is, it looks for the first block instead of the
>>smallest block in the freelist that will satisfy the request.  The
>>former tends to fragment the list, I suppose, although it may be
>>faster...
>
>OK, OK.  Some people pointed out by email that best fit actually
>fragments the list MORE than first fit.  For instance, if you have a
>request for 10K, and there are two blocks available, one with 50K and
>one with 11K, best fit will pick the one with 11K, leaving a 1K fragment
>left over.  First fit will pick the 50K one, leaving a useful block of
>40K.
>
>Well, "best fit" certainly SOUNDS better than "first fit."  At least the
>name does.  Perhaps I should have actually thought about it before posting...
>Naahh...
>
>So what algorithm is best for keeping the list unfragmented?  "Worst
>fit?"  One emailer mentioned "next fit"... Please elaborate.
	
	It varies as I know. In general, first fit performs better when
	there is a high freqency of requests (free/malloc) with length
	longer than average size, whereas best fit works better the other
	way around. I do not bother to tell what is the average size;
	it's there in most systems or architecture texts. There was some
	reseach done in this field in 70's. However, I do not have the
	references at hand. I know most computer systems work one way or
	the other, but I am not sure if a few blend the two techniques
	together. Sounds too complicated, ugh?

>-- 
>Paul Falstad      INTERNET: pfalstad@phoenix.princeton.edu
>PLink: HYPNOS     GEnie: P.FALSTAD  CIS:70016,1355
>Disclaimer: Everything I said is false, including this sentence
>"I'd like to leave the army, sir."  "Why is that?"  "It's DANGEROUS!"

Benjamin Zhu
=========================================================================
Disclaimer: I do not represent Johns Hopkins,
	    neither does Johns Hopkins represent me.
=========================================================================