malloc/free question

[Benjamin Zhu]

In article <15902 at phoenix.Princeton.EDU> pfalstad at phoenix.Princeton.EDU (Paul John Falstad) writes:
>In article <15873 at phoenix.Princeton.EDU> some idiot whose name
>coincidentally happens to resemble mine writes:
>>In article <14320 at levels.sait.edu.au> CCDN at levels.sait.edu.au (david newall) writes:
>>>peter at 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 at 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.
=========================================================================