From: utzoo!decvax!duke!harpo!seismo!hao!hplabs!sri-unix!dan@BBN-UNIX
Newsgroups: net.unix-wizards
Title: Re: compaction using realloc
Article-I.D.: sri-unix.4906
Posted: Sat Dec 18 02:40:36 1982
Received: Fri Dec 24 03:00:40 1982

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.