[comp.lang.c] malloc/free question

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