kdq@demott.COM (Kevin D. Quitt) (05/02/90)
In article <15873@phoenix.Princeton.EDU> pfalstad@phoenix.Princeton.EDU (Paul John Falstad) 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 Actually, best fit generally fragments the freelist more than any other technique. About the "best" (simple) way is to do a perfect fit if it's there, and a first fit if there's no perfect fit. kdq -- _ Kevin D. Quitt Manager, Software Development DeMott Electronics Co. VOICE (818) 988-4975 14707 Keswick St. FAX (818) 997-1190 Van Nuys, CA 91405-1266 MODEM (818) 997-4496 Telebit PEP last 34 12 N 118 27 W srhqla!demott!kdq kdq@demott.com 96.37% of the people who use statistics in arguments make them up.
pfalstad@phoenix.Princeton.EDU (Paul John Falstad) (05/02/90)
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!"
zhu@crabcake.cs.jhu.edu (Benjamin Zhu) (05/02/90)
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. =========================================================================
darcy@druid.uucp (D'Arcy J.M. Cain) (05/03/90)
In article <6822@jarthur.Claremont.EDU> dfoster@jarthur.Claremont.EDU (Derek R. Foster) writes: >In article <1990Apr28.020711.8639@druid.uucp> darcy@druid.UUCP (D'Arcy J.M. Cain) writes: >>Well I have never seen the source for a malloc and I don't know how it is >>normally done but a moment's thought will suggest that the above can't work. >>Consider the following: >> char *ptr = malloc(64); >> strcpy(ptr, "Stomp on the malloc structure"); >> free(ptr); > >Wellllll.... not necessarily. >Remember, malloc usually allocates a few more bytes than you ask it to. >The extra info could be stored at the beginning of the structure Here is the original suggestion I was responding to: <I suggested that malloc probably returns a pointer to a structure that has <a pointer to the "allocated" memory and also the number of bytes that were <allocated, so, when the free function is called using the pointer to the <structure, free uses the bytes allocate member of that structure to <"de-allocate" the memory. And all I tried to say was that that couldn't work. Any implementation *MUST* return a pointer to actual memory that the caller can write to. If, as the first poster suggested, malloc returned "a pointer to a structure that has a pointer to the allocated memory ..." then the above strcpy would be impossible. So if everyone would please stop sending me mail explaining how malloc works? -- D'Arcy J.M. Cain (darcy@druid) | Government: D'Arcy Cain Consulting | Organized crime with an attitude West Hill, Ontario, Canada | (416) 281-6094 |
CCDN@levels.sait.edu.au (david newall) (05/04/90)
pfalstad@phoenix.Princeton.EDU (Paul John Falstad) writes: > They do say that their allocator looks for the "first fit," and not the > "best fit;" I believe their algorithm would be best described as "next fit" and not "first fit". Their algorithm allocates the next fit from the last block allocated or deallocated. A "first fit" allocater, IMHO, should allocate from the "start" every time. This might not be very time efficient, but I observe that it doesn't suffer from too much fragmentation. At least, it doesn't for me. David Newall Phone: +61 8 343 3160 Unix Systems Programmer Fax: +61 8 349 6939 Academic Computing Service E-mail: ccdn@levels.sait.oz.au SA Institute of Technology Post: The Levels, South Australia, 5095