[gclist] ref-counting performance cost

[Bob Kerns]

You must be single-threaded, right?

Have you measured how many of your allocations are never upreffed, and the
amount of upref work that's done recursively?

-----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 are
constructed like this until a side effect occurs (e.g. binding to argument).
Then the ref counts are adjusted across the tree. So in my Lisp, (READ) can
return entire trees with zero refcounts. This does mean that referencing is
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 tree
containing every argument do no reffiing of their arguments. So for example
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 is
has a zero refcount. And functions which always return a subset of the cells
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 count
adjustments at all to its arguments or return.