Re: Ada GC (was about Java VM)

dewar@cs.nyu.edu (Robert Dewar) writes:


>Garbage collection is a technique for automatic storage management
>that is pretty much language independent. It is a good idea for some
>environments, and not for others. In particular, embedded applications
>and hard real-time applications prefer to stay away from garbage
>collection.


As a non-expert in hard real-time systems, the last sentence strikes
me as very strange. There are well-known GC algorithms that guarantee
hard real-time bounds, as well as reasonable (linear) space bounds.
Henry is the inventor of one.


On the other hand, there is a well-known theorem that any allocator
that does not move objects requires at least OMEGA(N logN) space in
the worst case, where N is the maximum number of bytes live at one
point. Hence a standard allocator with explicit deallocation can't
give reasonable guaranteed space bounds. Most don't give reasonable
time bounds either. (Note that I'm talking about WORST-CASE
performance, since the subject is REAL-TIME and SAFETY-CRITICAL
applications. The expected case situation is very different.)


Hence it seems to me that any program that requires hard time and
space bounds together with a general purpose allocator, must use a
garbage collector (or a compacting allocator).


My impression was that in reality such programs tend to not really use
a general purpose allocator, in which case the whole issue is moot.


Hans-J. Boehm
(boehm@parc.xerox.com)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.