GC strategies

Date view Thread view Subject view Author view

From: Archie Cobbs (archie@whistle.com)
Date: Fri Oct 30 1998 - 14:23:07 EST

Godmar & Tim,

Since you're the local GC experts, I'd like to query you on an idea
that has occurred to me. Maybe this have been discussed in various
papers.. I'm curious what the general concensus is, if any, and
your personal take on it.. (I'm not an expert on GC algorithms,
so be gentle :-)

Idea 

----

  The idea is to combine an imprecise but fast reference counting
  with the existing mark-sweep algorithm, in hopes that a "substantial"
  number of objects can be free'd in "real time" solely by their
  reference count.

  We'd add pseudo-reference counts to each object. The pseudo-reference
  count would have the property that it was equal to or greater than
  the actual reference count.

  When the pseudo-reference count goes to zero, immediately claim
  the object.

  Over time, make the pseudo-reference count more precise by adding
  code to decrement it when..

   - Exiting a block: for all local reference variables (including
     parameters), decrement the pseudo-reference count of the object
     they point to.

   - Assigning (ie, changing) any reference variable's value.

   - Etc.. ?

  Which situations we pay attention to could be optimized according
  to which situations give the most payoff.

  This would mainly benefit code that uses a lot of transient local
  variables, for example..

    ...
    int y = method(new String("abc"));
    ...

    public int method(Object x) {
      String s = table.get(x);
      return new Integer(s).intValue();
    }

  Here all of x, s, and the anonymous Integer could be immediately
  collected when method() exits.

  Another big win is when doing a lot of string manipulation with
  StringBuffer's.

The main question is: would the benefit be worth the cost? Probably
depends mainly on what percentage of objects are transient vs. what
percent are semi-permanent.

* * *

Another question: how far are we from making the incremental GC work?
What are the obstacles? Is it just a matter of combing through the code
to find all instances where a write barrier is needed? I would be willing
to do this if it would help get us there.

Any web references for any of this stuff are appreciated too.

Thanks,
-Archie

___________________________________________________________________________
Archie Cobbs   *   Whistle Communications, Inc.  *   http://www.whistle.com

Date view Thread view Subject view Author view

This archive was generated by hypermail 2b29 : Sat Sep 23 2000 - 19:57:02 EDT