Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[beckwb@ois.com (R. William Beckwith)]

Hans Boehm (boehm@parc.xerox.com) wrote:
: beckwb@ois.com (R. William Beckwith) writes:

: >An incr/decr only occurs when there is a change to the graph of
: >objects.  If the graph does not change, then there is not need
: >to incr/decr the counts.

: To reiterate Henry Baker's reply, this isn't always sufficient.
: You either need to count references from local and global variables as well,
: or you need to be very careful when you write your code.  My experience
: is that you're usually tempted to do the latter and end up spending
: lots of time debugging.  (My experience stems from a 50K-line
: C program.  I'm unconvinced that either C++ or Ada facilities
: would help, though they do make dumb/slow reference counting much easier.)

Good point.  If you know you have other strong references to an
object, you can use weak pointers for interators and such.  That
helps a little.  I would recommend using weak pointers for any object
that doesn't have a strong pointer to it declared in the immediate
or enclosing scope.

: >Paul Wilson's RT, generational, incremental GC'tor causes work
: >when the graph of objects is changed (write barrier).  Surely,
: >the color changes required with a graph change can be as fast
I meant:					  can't
: >as a simple incr/decr operation.

: You do need at least a write barrier on the heap for incremental collection.
: (In the best case, the dirty bits in the MMU are a sufficient
: write barrier, though not for that algorithm.  But using them is likely
: to increase collector latency, though probably not above the simple RC scheme.
: And your machine may not have hardware dirty bits, though the Intel
: architecture does.  And your OS may already need those bits for other
: things, adding a bit of overhead.)

Hmmm.  The code that gets executed on processing the write barrier seems
like it would take alot longer than incr/decr the reference count.  I've
never seen the code, so I just going on hunch here.

: The crucial issue in my mind is whether you can safely avoid counting
: pointers from the stack.

You and Henry (et al) are the wizzards here.  Do the stack based
references really cause most of the incr/decr operations?

: >Maybe my perspective is skewed because I have been RC'ing in Ada 9X.
: >I realize that C++ calls a copy constructor if you pass an object
: >as an argument by value.  But I was under the assumption that every
: >C++ RC'ing implementation worth its salt would require that the
: >reference objects are passed by reference (&).

: This no doubt helps, but isn't without cost.  At the implementation
: level, instead of passing a pointer to a heap location and adjusting the
: reference count, you're passing a pointer to a (stack allocated) indirect
: location which points to the heap.  You're likely to introduce
: additional memory references in accessing the result, and you may force
: the actual parameter into memory, out of a register.

Interesting question.  I'll have to check with my neighborhood Ada 9X
compiler implementor to find out what parameters qualify for register
passing.

: It also doesn't help with local variables that are updated.

Updating local (stack) variables doesn't modify the object graph,
but doesn't it change to roots?  Don't non-conservative GC'tion
mechanisms have to update some root symbol list?

: >The other trick about RC'ing is that you don't have to keep the
: >counts in the objects, you can keep them all in the same data
: >structure so that you pages are unnecessarily dirtied.

: Yes, but that isn't free either.

You're right.  You have to make a speed or space choice.  Either you
add a second pointer to the pointer object for the reference count
(fast, doubles pointer object size) or you add data to the object
that points to the reference count (indirect reference is slower,
causes page with object to be moved into memory, smaller pointer
object).

I like the first approach because the memory overhead of RCing in a
compiled langauge is so much less than what is required for GCing
anyway that the extra four or eight bytes per pointer doesn't seem
like much.

... Bill

------------------------------------------------------
e-mail: Bill.Beckwith@ois.com        |    Team Ada
Objective Interface Systems, Inc.    | dist, full O-O
1895 Preston White Drive, Suite 250  | multithreading
Reston, VA  22091-5448  U.S.A.       |    built in