Dynamic Storage Allocator Pros and Cons

[Phong Vo[drew]]

In article <241 at smds.UUCP>, rh at smds.UUCP (Richard Harter) writes:
:... 
: Storage utilization efficiency: G/R has a fixed overhead of 28 bytes/block.
: Overhead for M/F depends on the implementation; 8 bytes per block is
: representative.  Efficiency of storage utilization (ratio of storage
: allocated to total storage required) depends on the algorithm and the
: pattern of allocation block sizes requested.  Knuth cites the 2/3 rule
: (equilibrium is two allocated blocks versus one free block) for allocators
: which immediately merge returned blocks.  However his calcuation ignores
: the possibility of an exact fit.  Some years ago I did a study of 
: efficiency of allocation algorithms using the assumptions of (a) random
: request sizes and (b) total space large compared to request sizes.
: Under these conditions I found that best fit was indeed best and that
: storage efficiency was upwards of 90%.  Under the same conditions a
: binary buddy system has a storage efficiency of 67% (many malloc/free
: implementations use this algorithm.)  However the efficiency of the
: buddy system is strongly dependent on the request size distribution
: -- it can vary from 50% to 95%.
: 
There is a paper that Dave Korn and I presented in the Summer '85 USENIX conference,
In Search of a Better Malloc, that gave lots of data on different allocation
strategies in actual implementations. I just want to point out further that
any allocation strategy can be modified with a roving pointer (i.e., allocate
from the last freed block if possible). I've implemented the basic best-fit strategy
with this enhancement using a splay tree for the free blocks. This malloc has the space
efficiency of best-fit and, "in practice", performs about as good as BSD malloc
which is a buddy system. In fact, for graphical programs (f.e., X programs)
where malloc fragmentation can cause page thrashing, the programs do better with
the new malloc than with BSD malloc even though it costs a tiny bit more for
allocation. This malloc is now standardly distributed with SysVr4.

: Summary -- it's probably a wash unless almost all requests are for very
: small blocks.
: 
But this is not trivial since allocation of small blocks is a good part of
significant programs. For example, compilers tend to do lots of small mallocs
for identifiers, symbols, etc.

: Security and Error Checking:
: ... list of nice features ... 
:
I had the same features in my malloc. These features can be turned on by
a compile flag. They are invaluable for debugging memory faults.

	Phong Vo, att!ulysses!kpv