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: dewar@merv.cs.nyu.edu (Robert Dewar) Subject: Re: Garbage Collection in Ada Date: 1996/10/16 Message-ID: #1/1 X-Deja-AN: 189966266 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610132138291604607@dialup101-6-14.swipnet.se> <19961014115513529729@dialup105-2-16.swipnet.se> <32652A7C.41C6@mti.sgi.com> organization: New York University newsgroups: comp.lang.ada Date: 1996-10-16T00:00:00+00:00 List-Id: Hans-Juergen said "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. " No, there are general purpose allocators with much better performance. Just consider a simple binary allocator, at worst you waste half the space, i.e. a factor of 2. But perhaps I don't understand your point. Also, there are many programs which use storage only of a certain limited range of sizes, and it is quite easy to make general purpose allocators that handle this situation MUCH more efficiently. In the limiting case consider the case where a program uses ONLY blocks of a fixed size. You have zero fragmentation there, but a conservative GC can still hold on to an arbitrary number of blocks, so you cannot put a bound on the effective overuse of storage. It is quite easy to bound the fragmentation effect for a given application. It is almost impossible to bound the accidental holding-onto-storage effect of a conservative allocator, since for example, the particular floating-point values in use can result in holding onto storage one day, and not the next day, depending on where your program loads in memory. Finally, there is one disadvantage of a conservative collector that you did not mention, namely the possibility that it will unexpectedly collect blocks that are in use. This can result from either compiler optimizations, or code that cheats with poitners (code which may exist in practice, and which in particular typically exists in the conservative allocator itself!