Date: Fri, 7 May 93 17:05:07 CST
From: (csaba AT vuse DOT vanderbilt DOT edu) <csaba AT vuse DOT vanderbilt DOT edu>
To: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: Re: malloc/free broken??

On Fri, 7 May 93 16:24:06 EDT,
  DJ Delorie writes:

>> > The malloc that djgpp uses is the original BSD freed malloc sources.
>> > I cannot use the GNU malloc because of the GPL.  The current malloc
>> > will only reuse a block if |log2(size+4)| is the same.
>
>> Well, actually anybody could use GNU malloc.  It would just mean that
>> the resulting program would be covered by the GPL.
>
>Correct.  What I meant was that I cannot include gnu's malloc in
>libc.a, since the modules in libc.a cannot be GPL.  I decided long ago
>to avoid GPL in the required parts of the development kit (crt0, libc,
>go32, etc) to avoid automatically GPLing every application.

As far as I remember the GNU malloc uses the same algorithm as the BSD one. 
They both add the block header size to the requested block size then round 
up the result to the next power of two. They maintain separate free lists 
for each of these 2^N block sizes. Once a page is obtained from the 
operating system it is permanently committed to a given free list. 
(Sometimes a free block may be split in half and migrate downwards.) The 
advantage of this scheme is that malloc and free calls are very fast 
because there is no need to search the free lists. Also there is less 
memory fragmentation. The disadvantage is that it uses more memory than the 
"traditional" linked list of random sized free blocks approach.

I guess that the original poster's example (few very big blocks) is the 
counter example when the "tradional" approach works better. The GNU or BSD 
method is far superior when a large number of varying size but relatively 
small structures are allocated/freed in random order.

Hope this helps

Csaba Biegl
csaba AT vuse DOT vanderbilt DOT edu