To: Eric Backus <ericb AT lsid DOT hp DOT com>
Cc: djgpp AT sun DOT soe DOT clarkson DOT edu (djgpp)
Subject: Re: malloc/free broken?? 
Organization: Code Generation Technology, San Francisco, CA
Date: Sun, 09 May 93 11:28:07 -0700
From: "Thomas J. Merritt" <tjm AT netcom DOT com>

|<><><><><> Original message from ericb AT lsid DOT hp DOT com  <><><><><>
|In practice, on a unix machine I have supplied alternate versions of
|malloc() to a program, and everything worked fine.  I haven't tried
|with DJGPP, but I bet it would work fine.

I regularly link my programs on DJGPP with one of several versions of malloc
that I have written.  Everything works fine.  The prime problem with the BSD
malloc is that although it is fast for small programs it slows down large
programs.  The power of 2 allocation strategy causes a large amount of internal
fragmentation.  This fragmentation means that memory is wasted and your program
will start swapping sooner.  Fragmentation also means that more paging has to
occur to access a set of blocks.

A good alternative to a power of 2 allocator is a first fit with sorted
free list allocator.  In this senario a list of free blocks is maintained
sorted by address.  Blocks are allocated from the first free block on the list
large enough to satisfy the request.  This strategy has little internal 
fragmentation but can have more external fragmentation than the power of 2
strategy.  In general, I find it more efficient than the BSD malloc on my
4Mb laptop.  

Memory allocation algorithms often have a major impact on program performance.
Having a collection of allocators to choose from is very handy in tuning 
performance with out wasting a whole lot of time.  Experience has proven to
me that no single allocator is best for all programs, although it is easy
to write a universally bad allocator.

I seen very little written on memory allocation in general.  If anyone can
pass on references to papers on the subject I would appreciate it.

TJ Merritt
tjm AT netcom DOT com