[gclist] ref-counting performance cost

Bill Birch birchb@ozemail.com.au
Wed, 13 Sep 2000 20:54:12 +1000

----- Original Message -----
From: "Bob Kerns" <Bob.Kerns@brightware.com>
To: "'Bill Birch'" <birchb@ozemail.com.au>; "Manoj Plakal"
<plakal@cs.wisc.edu>; <gclist@iecc.com>
Sent: Thursday, September 07, 2000 12:45 AM
Subject: RE: RE: [gclist] ref-counting performance cost

> You must be single-threaded, right?
Yup. MT would be difficult.

> Have you measured how many of your allocations are never upreffed, and the
> amount of upref work that's done recursively?
I have a counter on all ref operations, and can compare the 'optimised' with
the traditional versions of functions.

> -----Original Message-----
> From: Bill Birch [mailto:birchb@ozemail.com.au]
> Sent: Thursday, September 07, 2000 6:40 AM
> To: Manoj Plakal; gclist@iecc.com
> Subject: Re: RE: [gclist] ref-counting performance cost
> >     - A friend who implements tracing collectors asks why bother
> >       reclaiming garbage "all the time" by checking counts at
> >       every pointer store when one can just use a tracing collector
> >       and trigger it occasionally at allocation points only ......
> I never understood why there is a need in traditional RC to adjust the
> refcount on every pointer value change. So I don't, I always assume that a
> memory cell is garbage so the default state is refcount = 0. Whole trees
> constructed like this until a side effect occurs (e.g. binding to
> Then the ref counts are adjusted across the tree. So in my Lisp, (READ)
> return entire trees with zero refcounts. This does mean that referencing
> a recursive operation, however it only recurses on zero count nodes. This
> gives me complete freedom to manipulate pointers without reffing and
> dereffing everywhere.
> As a further 'optimisation', functions which are guaranteed to return a
> containing every argument do no reffiing of their arguments. So for
> CONS, LIST do NO reference increment of their arguments on entry nor deref
> on exit.
> There are two other classifications of functions which have slightly
> different 'optimisations'. Functions which return a new value (e.g +) in a
> new cell or tree just get their arguments checked for garbage. The return
> has a zero refcount. And functions which always return a subset of the
> referenced in their arguments (eg. CAR) get their arguments checked for
> garbage except the return value.{Quite a dubious 'optimisation'!}
> Details aside, the point is that by deferring reference counting away from
> the physical act of assigning a pointer, the application (in this case a
> LISP interpreter) can actually _choose_when to mark cells to keep and
> _choose_ when to look for garbage. In general terms this is like a locally
> scoped mark-sweep. This opens the door to many potential short cuts.
> I believe a compiler could analyse code and deduce that a function like
> (DEFUN FOO (X Y) (CONS X (LIST X Y (CONS X Y)))) requires no reference
> adjustments at all to its arguments or return.