Dynamic Storage Allocator Pros and Cons

[Richard Harter]

In article <14016 at ulysses.att.com>, kpv at ulysses.att.com (Phong Vo[drew]) writes:
> In article <241 at smds.UUCP>, rh at smds.UUCP (Richard Harter) writes:

	[... I don't need to repeat it; I've already posted it once.]

: 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 have heard good things about this paper -- unfortunately I
	don't have a copy.

: 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 is a very good point.  I haven't studied the matter but I suspect
that the allocator I posted should be fairly good in this regard because
each there is a lifo list for each size so that either exact fit or split
comes from the most recently returned.

One of the things that I have thought about but have never found the time
to implement (There is more to life than dynamic storage allocators) is a
strategy of dealing with the very common situation of allocating sundry
blocks during a routine and then deallocating them at the end (alloca, if
you will). 

: This malloc is now standardly distributed with SysVr4.

Hurrah!  This brings up something that I didn't mention in the posting.
If you are running on a wide variety of platforms it is very useful to
have reliable portable utilities, either as wrappers or as replacements.
While it is true that many platforms have excellent utilities (quite
often subtly incompatible) it is also true that there are some real
lemons out there.

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

Well this is clearly an application dependent matter.  The impact of the
overhead cost depends on the average block size.  However the "right"
approach is to have separate pools for the short blocks with bit maps
for "free lists".

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

	Thank you for the kind words.  I sort of take the view that
that error checking should be turned on all of the time.  My view is that
if an error crops up in production software then I want to know about it
immediately and I want all of the information I can get.
-- 
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.