Re: Garbage Collection in Ada

[dewar@merv.cs.nyu.edu (Robert Dewar)]

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!