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

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

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

>Hans Boehm (boehm@parc.xerox.com) wrote:
>: You do need at least a write barrier on the heap for incremental collection.
>:...

>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 cost of the write barrier clearly depends on the algorithm.  But in
a number of cases all you need to do is to remember that a write to that
location occurred.  This may require a very small number of instructions
(I vaguely remember 4 or 5 from some talks on software write barriers)
or none (in the case of VM support).  Of course the cheaper implementations
may have other costs.

>: 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?

The details obviously depend on the application.  But that's certainly
what I would expect for the vast majority of applications.  (I intended
to include register assignments with stack assignments.)  Heap assignments
tend to be rare in most code.  But things like list traversals are very
common, and usually involve many updates to a local variable.

Manual or compiler optimizations can significantly improve matters.
But those are generally risky or not possible with smart pointer
style implementations.

As was mentioned earlier, there are several fast RC implementations
(various older Xerox systems and DEC Modula-2+) that explicitly
avoided counting stack references and instead used a conservative
stack scan.

>: 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?

Maintaining an explicit list of stack resident roots is
expensive.  I would guess that most such schemes are comparable to
reference counting.  One alternative is to conservatively
scan the stack.  (This is done by many systems other than ours,
e.g. the above reference counted systems, SRC Modula-3, gcl or AKCL,
Bartlett's C++ and Scheme collectors, scm, and probably others.)
Another alternative is to generate stack frame descriptors, and
to have the collector walk the stack, mapping return addresses
to pointer locations.  This involves no overhead outside the collector,
but substantial compiler support.  A third alternative, commonly used in
dynamically typed languages, is to use some combination of a
register usage convention and tagged pointers.  That's probably
cheaper than explicit root lists, but has some overhead and some other
problems.

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