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,3498dd887729ed19 X-Google-Attributes: gid103376,public From: Hans-Juergen Boehm Subject: Re: Garbage Collection in Ada Date: 1996/10/16 Message-ID: <32652A7C.41C6@mti.sgi.com>#1/1 X-Deja-AN: 189874060 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610132138291604607@dialup101-6-14.swipnet.se> <19961014115513529729@dialup105-2-16.swipnet.se> cc: boehm content-type: text/plain; charset=us-ascii organization: Silicon Graphics Inc., Mountain View, CA mime-version: 1.0 newsgroups: comp.lang.ada x-mailer: Mozilla 2.0S (X11; I; IRIX 6.2 IP22) Date: 1996-10-16T00:00:00+00:00 List-Id: Robert Dewar wrote: > Personally, although these kind of conservative collectors are a partial > solution useful in some circumstances, I don't find them acceptable for > serious solution of the GC problem. If you count on a conservative > collector to free storage, you have a very unreliable program, since > you could find on some particular run that you were just unlucky and > a junk integer value held a critical large block in memory, causing > the program to crash and burn. > > If you don't mind a program with this kind of unreliability, then this > approach may work, but for me, the only really viable approach, and the > only one worth putting real effort into in the Ada context is a proper > full GC that know what is a pointer and what is not. > Let's compare the options here: 1. Traditional manual memory management - No guarantees about space usage, since the language definition makes no guarantees. - Space usage may be unexpectedly large on certain inputs due to fragmentation effects. The worst-case space usage of any general purpose allocator is at least N logN, where N is the amount of live heap data. If this occurred in practice, the customer would probably be unhappy. And many commonly used allocators have much worse worst-case performance than that. 2. Conservative garbage collection - No guarantees about space usage, since the language definition makes no guarantees. - Space usage may be unexpectedly large on certain inputs due to fragmentation effects or due to misidentified pointers. 3. Nonconservative garbage collection - No guarantees about space usage, since the language definition makes no guarantees. - If you use a compacting collector, you can bound heap size to a constant factor times live data size (which is not true for either of the above), but you'll pay for it in other ways. Thus I would claim that if you really need hard space bounds your options are severely limited (e.g. no general purpose dynamic memory allocation or perhaps a compacting collector + platform specific tools to bound stack use, etc.) -- Standard disclaimer ... Hans-Juergen Boehm boehm@mti.sgi.com