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

[hbaker@netcom.com (Henry G. Baker)]

In article <3bo43b$61v@news.parc.xerox.com> boehm@parc.xerox.com (Hans Boehm) writes:
>beckwb@ois.com (R. William Beckwith) writes:
>>You and Henry (et al) are the wizzards here.  Do the stack based
>>references really cause most of the incr/decr operations?

References from the registers and the stack are the most volatile, and
therefore cause the most updating of reference counts.  This is by
definition, since it is impossible to change a reference count in any
other way.

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

The GC for my Ada83 Lisp implementation maintains an explicit list of
stack resident roots using a 'limited private' type.  See my ftp/www
page for how to get the Ada Letters paper which describes the stack
roots scheme.

-----

I just wanted to point out again that objects whose reference counts
are always one, and the programmer/compiler knows this, avoid the
usual overheads of reference counting.  For example, one cannot have
contention on such objects, and therefore locking isn't necessary, and
one need never _check_ the count on such an object when recycling,
since one already knows that it is =1, and therefore the object can
always be recycled immediately.  Such objects are called 'linear', and
there are several papers in my ftp/www directory that discuss them.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^
(It _is_ accessible, but Netcom is loaded; keep trying.)