Path: utzoo!attcan!uunet!cs.utexas.edu!rutgers!njin!princeton!phoenix!pfalstad From: pfalstad@phoenix.Princeton.EDU (Paul John Falstad) Newsgroups: comp.lang.c Subject: Re: malloc/free question Message-ID: <15902@phoenix.Princeton.EDU> Date: 2 May 90 05:19:52 GMT References: <2638831C.728C@telly.on.ca> <271@caslon.cs.arizona.edu> <14320@levels.sait.edu.au> <15873@phoenix.Princeton.EDU> Reply-To: pfalstad@phoenix.Princeton.EDU (Paul John Falstad) Organization: Princeton University, NJ Lines: 29 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. -- 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!"