Precise GC (was Re: cannot build libjava/gnu/gcj/xlib/natClip.cc)

Wed Jan 3 12:01:00 GMT 2001

The problem here is that you really need a lot more than a precise GC to
guarantee space bounds. You need the language or the implementation to
define object reachability, or at least some bound on object reachability.
I believe Java doesn't. And you need to ensure that you don't perform any
optimizations that violate those space bounds, e.g. by extending the
lifetime of a pointer to perform common subexpression elimination, or by
delaying an assignment to a pointer that would release a large data
structure. Does gcc do common subexpression elimination on calls to
side-effect free functions that may allocate? It probably can move
assignments to locals across function calls?
I believe there have actually been very few garbage-collected systems that
guarantee hard space bounds. SML of NJ (Andrew Appel et al) went through a
fair amount of work to guarantee that asymptotic space bounds were defined
and preserved, but even they only guaranteed space usage up to a constant
factor, which is less than what you need here. (Reasonable space bounds on
malloc/free programs arguably aren't any easier, but that's a different
story.)
Hans
> -----Original Message-----
> From: Cedric Berger [ mailto:cedric@wireless-networks.com ]
> Sent: Wednesday, January 03, 2001 11:21 AM
> To: tromey@redhat.com
> Cc: Bryce McKinlay; Per Bothner; java-discuss@sources.redhat.com
> Subject: Precise GC (was Re: cannot build
> libjava/gnu/gcj/xlib/natClip.cc)
>>> > Bryce> The collector is mostly precise already, thanks to the bitmap
> > Bryce> marking descriptors etc. I don't see how making it completely
> > Bryce> precise (such that even data on the stack and in 
> registers were
> > Bryce> scanned precisely) could be achieved without significant
> > Bryce> runtime overhead in either the collector or the generated
> > Bryce> object code.
> > 
> > There's definitely an overhead. I have a paper here describing work
> > people (Rick Hudson, I think) did to make gcc emit tables so that
> > precise, copying GC can work. For some applications this 
> overhead is
> > attractive, though, I think.
>> Form embedded systems, a precise GC would often be a requirement.
> (it was one of the main factor why we (unfortunately) cannot use GCJ
> for our current project)
>> When you have 256K of RAM, and your device must run 24h/24, you
> don't want to take any change to leak memory and run out of heap
> because of a conservative GC mistake.
>> In embedded systems, predictability it the top requirement. And I 
> don't see how to get predictable results without a precise GC.
>> Cedric
>