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

[boehm@parc.xerox.com (Hans Boehm)]

beckwb@ois.com (R. William Beckwith) writes:

>Kevin Warne (kevinw@whistler.com) wrote:

>: Depending on the number of inc/decs, the cost of RCing can be very
>: significant.  A single inc + dec that hits on-chip cache would 
>: take 6 cycles.  Multiply by the avg. number of inc/decs taken
>: per object and the cost and percentage of cache misses and I think
>: you'll find the incrementing and decrementing operations are 
>: consequential after all.

>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.)

>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
>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.)

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

>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.  It also doesn't
help with local variables that are updated.

>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.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...