Re: Ada GC (was about Java VM) (Hans Boehm)
30 Jan 1996 18:21:57 -0500

          From comp.compilers

Related articles
Possible to write compiler to Java VM? (I volunteer to summarize) (Peter Seibel) (1996-01-17)
Re: Possible to write compiler to Java VM? (1996-01-29)
Re: Ada GC (was about Java VM) (1996-01-29)
Re: Ada GC (was about Java VM) (1996-01-30)
Re: Ada GC (was about Java VM) (1996-01-30)
Re: Ada GC (was about Java VM) (1996-01-31)
Re: Ada GC (was about Java VM) (1996-01-31)
Re: Ada GC (was about Java VM) (1996-01-31)
Re: Ada GC (was about Java VM) (1996-01-31)
Re: Ada GC (was about Java VM) (1996-01-31)
[15 later articles]
| List of all articles for this month |

From: (Hans Boehm)
Date: 30 Jan 1996 18:21:57 -0500
Organization: Xerox Palo Alto Research Center
References: 96-01-037 96-01-100 96-01-118
Keywords: translator, Ada, GC (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

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

Post a followup to this message

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