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

[Boehm, Hans]

> From: Cedric Berger [ mailto:cedric@wireless-networks.com ]
> > > Fragmentation append with C code too, but you can workaround it by
> > > 1) preallocating/recycling most of the big objects.
> > > 2) keeping for example a 20% margin on the heap, and testing
> > > extensively.
> > It seems to me that with anything like a 20% margin, you're 
> clearly relying
> > on statistics.
> 
> Yes, I rely on statistics, but I do extensive testing. Testing for
> fragmentation is easier than testing for pointer misidentification.
Why?  Bad fragmentation often occurs in repsonse to certain unexpectedly
regular allocation pattern, which are likely to be generated only in
response to certain unusual inputs ... 
> 
> > Assuming you avoid certain brittle data structures (see
> > http://www.hpl.hp.com/personal/Hans_Boehm/gc/bounds.html ), a false
> > reference costs you one copy of your largest data 
> structure, in the worst
> > case, i.e. up to a factor of 2.  Since you can get multiple false
> This is really difficult to avoid theses data structures.
The problem are things like queues implemented as singly linked lists, or
lazily evaluated lists.  I almost never use either, and there is a trivial
variant of a queue that doesn't share the problems.

Intuitively, you risk unbounded retention when adding back pointers
everywhere would make much more data reachable.  Thus circular data
structures are not only fine, they're optimal in this sense.  (They may
admittedly increase the average amount of data retained by a false
reference.  But they're not a problem for the factor of 2 bound.)
> 
> I really like the collections API, and use it extensively, like many
> java2 programs. I just read today that Tomcat use HashMap of ArraySet
> to store its parameters. what will append if the HashMap get falsely
> referenced when I reload the parametres?
I don't understand the issue.  At most you will retain the HashMap when it
should have been inaccessible, potentially doubling the space requirements.
> 
> What makes that even worse is that Java use a lot of cyclic references
> all over the place:
> Examples: 
> AWT/Swing: each component track both its parent and children.
>    When you destroy a frame, *any* false reference on any component
>    or part of component will prevent the entire stuff to be garbage
>    collected.
> Classloaders:
>    Classloader load classes and keep track of them, and each class
>    has a references back to its classloader. 
>    if, at some point, you want to unload a module (say a Web 
>    Application with tomcat), you get rid of the classloader and its
>    live object. But *any* false reference on either the classloader or
>    any class will prevent the whole tree to be garbage collected.
> And so on...
Cycles are fine.
> 
> This is *much* worse than what you suggest.
> Sure, this will mainly affect long-running applications like
> servers or embedded systems.
> 
I haven't seen any evidence of that.

Hans