Re: dynamic memory allocation

[jsa@alexandria.organon.com (Jon S Anthony)]

In article <33A55F1B.63FE@gsfc.nasa.gov> Stephen Leake <Stephen.Leake@gsfc.nasa.gov> writes:

> They are proposing a message passing scheme where sending tasks allocate
> buffers for each message from a heap, and receiving tasks deallocate. I
> have suggested that the heap could become fragmented (the buffers are
> NOT all the same size). They say "we'll just test it thoroughly".

Unless there is something "special" about the allocation vs. liveness
in this application, fragmentation is a certainty if deallocation does
not coalesce adjacent free space.


> Can anyone provide a reference to a book or study article that says this
> is bad?

Whether it's bad or not will really depend on the specifics of the
application and the memory manager.  If the MM coaleces or compacts, I
don't see how _fragmentation_ will be a problem.  However, the
_overhead_ of such capability could be a problem.


> and they don't even bother to mention dynamic allocation -
> unfortunately, that makes it hard to say "see, this book says it's
> bad".

Part of the problem is the meaning of "dynamic allocation".  Certainly
stack allocation is just as dynamic as heap allocation.  And you could
have "heap" style allocation from a preallocated pool.


> Or a book on designing dynamic memory allocation algorithms to avoid
> fragmentation?

I'm not sure there is any _book_ devoted to "memory management in
general", but it occurs in many books.  For example, Aho, Hopcroft and
Ullman's "classic" _Data Structures and Algorithms_ has a chapter on
MM and it discusses this stuff including "buddy" systems and
compaction.  Griswold & Griswold go over this is rather great detail
in _The Implementation of the Icon Programming Language_ (this is in
the context of GC).  And of course this is discussed in Knuth.
Fragmentation concerns are also discussed in various settings in
Jones' and Lins' _Garbage Collection_ (which also has a very extensive
bibliography).  On the Web you will find a lot of relevant information
(though mostly in the context of GC) at:

http://www.harlequin.com/mm/reference/bib/misc.html -- General bib
ftp://ftp.netcom.com/pub/hb/hbaker/home.html -- A lot of good stuff
ftp://ftp.cs.utexas.edu/pub/garbage/ -- All kinds of allocator stuff

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com