dan@BBN-UNIX (12/10/82)
From: Dan Franklin <dan at BBN-UNIX>
Date: 6 Dec 1982 16:56:22 EST (Monday)
I agree; that code is highly implementation-dependent. It knows that the last
storage freed is always the first storage allocated (if it fits). This wouldn't
be so bad if that particular strategy weren't so awful in the general case. I
once wrote a program which used stdio to read a lot of files (never more than
three were open simultaneously) and also permanently allocated a series of small
chunks of space (for a linked list). It turns out that if you have a series of
such small allocations, interspersed with the malloc(512), free() statements
from stdio, that every 512-byte freed area gets at least one tiny chunk removed
from it, so EVERY TIME stdio reaches out for another buffer it causes an sbrk!
Essentially the program acted as though the free() simply weren't there!
It would be nice if we could fix malloc, and at the same time provide the
malloc_compact routine you suggest. It would mean breaking those programs--like
the one that fragment of code came from--that relied on its LIFO behavior, but
the statement in the manual is so opaque that there probably aren't very many
such programs--and I for one would never rely on being able to get back freed
data (which I think the manual is recommending) in any case!
Danthomas (12/13/82)
I have a version of malloc (which I got from somebody else) which we are using on our Vaxen now. It satisfies all memory requests by allocating a block which is the next power of 2 bigger than the request. This allows it to keep separate free lists for each size of request, making malloc() much faster on a paging machine (it only needs to keep 29 free lists, most of which are never used). Obviously it depends on the fact that memory is cheap on a Vax. We have a program which used to go into horrendous thrashing as soon as its data space size reached the amount of real memory on the system, do to the standard malloc's behaviour of searching all blocks to find a free one. Our malloc also has a little instrumentation built into it, so you can easily find "hardening of the arteries" if you are interested. I have permission from the author to distribute it, if anybody is interested, drop me a line. =Spencer (harpo!utah-cs!thomas, thomas@utah-20)
sch@MITRE-BEDFORD (12/15/82)
Date: Fri Dec 10 08:41:50 1982 The strategy used by malloc/free/realloc is a first fit method. You are suggesting using a best fit instead. I believe if you do a study of the literature (Knuth), you will find that there is a trade off here. If you use best fit (as you suggested) then the routine has to search all possible blocks (slower), and many small chunks get allocated and never can be reused. The whole allocation strategy of malloc does break down for large programs on virtual memory systems like a vax. Berkeley knows know about this I don't no what their future solutions will be. I agree with your general comment that one should not depend on the behaviour of malloc returning the previously freed block. Rather than changing malloc/free, a new set of subroutines which do allocation but also garbage collection would be handy. These routines would have to return a pointer to a pointer (char **) so the routine could move blocks around for garbage collection. Has anyone implemented such routines? Stephen Hemminger sch @ mitre-bedford
dan@BBN-UNIX (12/18/82)
From: Dan Franklin <dan at BBN-UNIX> Date: 16 Dec 1982 0:55:40 EST (Thursday) The algorithm used by malloc is a modified first fit (one that is probably not in the literature); the "classical" first fit, such as that in the kernel malloc, always starts searching from the beginning of the list. I certainly don't think best fit would be better; I am sorry if my remarks seemed to imply that. At the time I wrote the letter, I thought that changing to "classical" first fit--that is, always starting the search at the beginning of the list--would be good, since it would at least avoid anomalous behavior, even if it did make malloc more expensive (after a while, as Knuth points out, you get a bunch of relatively small free areas at the beginning of the list that you have to keep passing over). A better idea (Knuth V1, answer to exercise 6 in section 2.5) is to start each search after the last block allocated; randomizing the starting point randomizes the arrangement of free blocks, leading to lower average search time to satisfy a malloc request. The problem I had would not have happened with this algorithm.
laman (12/22/82)
You say that you feel that the modified first fit is a better idea. Why? You will have a variable pointer of where to start searching through your list, but you may start chopping up all your free blocks quicker since, if you are asked for some blocks say ~1/2 free block size, they will be allocated from the other blocks. After a while you had better hope you don't get some requests for some larger sized blocks after you have chopped up your free list blocks. At least the "classical" first fit is a little better suited to this. What this gets down to is that one must experiment some to find the method that best suits one's needs. It may be best if we save the net and battle this out between ourselves. Mike Laman ...!sdcsvax!laman
gwyn@Brl (12/28/82)
From: Doug Gwyn <gwyn@Brl> Date: 18 Dec 82 17:00:58-EST (Sat) Some years ago I implemented the first-fit allocation method using a "roving" search-start pointer as you mentioned, along with combining adjacent freed regions (identifiable because of "boundary tags") during allocation searching. The application was display processor real-time segment management, and it worked well. One drawback to the "boundary-tag" approach is that it assumes there is no memory in the pool other than that allocated through this package. This is NOT the case with the "malloc" scheme, whereby a user can increase the program break directly without breaking malloc's operation. I have tried to think of ways of permitting fake "busy block" boundary tags for uncontrolled heap space, but I couldn't think of anything reasonable to do about it. So malloc is still a sensible choice.