[gclist] reference counting

[Robert Virding]

Greg Morrisett <jgm@cs.cornell.edu> writes:
>A few things:
>(2) While reclamation *can* be immediate, if you have a large
>data structure (e.g., an abstract syntax tree) and the root 
>count goes to 0, then you may end up walking and freeing the
>whole tree.  To amortize the overhead of this, you may end up
>sacrificing "immediate" reclamation.  RC tends to work well
>for large, pointer-free objects.

A solution I remember reading about in a book many years ago, can't
remember where, was keeping a To Be Dereferenced (TBD) list.  Each time
an object is dereferenced it is just pushed on the the list, this means
an object can occur on the list many times.  At allocation time this
list is scanned until an object with only one reference, i.e. which is 
now free, is found and this object is used.  the other objects passed 
over just have their reference decremented.

If the found object has children then they are pushed onto the TBD list.

This algorithm has the benefit that you can make it as incremental as
you want, just by setting an upper limit on how many objects to traverse
before giving up and taking something from a free list.  It gives you
better control of when you do reclamation, e.g. it can be delayed until
when the system is idle or broken up into small incremental chunks.

One disadvantage of this system is that it makes it difficult to do 
optimisations which use that there is only one reference to an object.

I once did an Erlang implementation with this type of GC and the results
were very favourable.  The only real problems were that it was a little
slow and it was very "sensitive" to programming errors in the
implementation.

	Robert

-- 
Robert Virding                          Tel: +46 (0)8 545 55 017
Bluetail AB                             Email: rv@bluetail.com
S:t Eriksgatan 44                       WWW: http://www.bluetail.com/~rv
SE-112 32 Stockholm, SWEDEN
"Folk säger att jag inte bryr mig om någonting, men det skiter jag i".