malloc/free question

Paul John Falstad pfalstad at phoenix.Princeton.EDU
Wed May 2 15:19:52 AEST 1990


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.

-- 
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!"



More information about the Comp.lang.c mailing list