Dynamic Storage Allocator Pros and Cons

[Richard Harter]

I have been asked to post a summary of pros and cons of using the
storage allocation package I recently posted versus using malloc/free
directly.  In the following text G/R (getsp/retsp) is the posted
allocator [which is actually a wrapper around malloc/free] and M/F
is malloc/free.

Performance:

Speed:	Timing studies on a SUN 3 OS 3.4 gave roughly equivalent times
for G/R and M/F (getsp was faster than malloc and retsp was slower than
free.)  Performance on your machine may be quite different.

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%.

Summary -- it's probably a wash unless almost all requests are for very
small blocks.

Security and Error Checking:

This is the reason for using G/R, if it matters to you.  Specifically
the features are:

(A)	All invalid size requests (zero, negative, too large) are trapped.

(B)	All invalid 'free's are trapped.

(C)	Border overwrites are trapped.

(D)	Requests are identified so that storage allocation problems
	(bad size, overwrites, illegal returns) can be immediately
	tracked down to the offending statement.

(E)	You can print a storage allocation map with a time tag or
	equivalent for each allocated block.  The map can sorted to
	identify memory leaks or unusual allocation patterns.

(F)	Control information and allocated memory are physically
	separated, reducing the chance that control information is
	compromised by programming errors.

These features are particularly useful in large programs which make
heavy use of allocation and deallocation.  The utility of these features
probably depends strongly on the kinds of programs that you write and
on your preferred debugging style.

Along the line of some other threads, I customarily use a suite of 
pre packaged software instrumentation that I embed in all major
applications.  My experience is that this simplifies software development
and converts many errors which would otherwise be troublesome into
trivial problems.  This may be a matter of what works for one person
doesn't work for another.

Conclusion:

Use it if you want the features.
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.