From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c70f02b79bc3d231 X-Google-Attributes: gid103376,public From: jsa@alexandria.organon.com (Jon S Anthony) Subject: Re: dynamic memory allocation Date: 1997/06/17 Message-ID: #1/1 X-Deja-AN: 249177397 Distribution: world References: <33A55F1B.63FE@gsfc.nasa.gov> Organization: PSI Public Usenet Link Newsgroups: comp.lang.ada Date: 1997-06-17T00:00:00+00:00 List-Id: In article <33A55F1B.63FE@gsfc.nasa.gov> Stephen Leake 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