[gclist] zillion objects and gc

Nick Barnes Nick.Barnes@pobox.com
Wed, 29 Aug 2001 10:26:47 +0100

At 2001-08-29 02:35:55+0000, "Richard A. O'Keefe" writes:
> "Boehm, Hans" <hans_boehm@hp.com> wrote about reference counting:
>       Also note that reference counting touches
>       objects that wouldn't otherwise be touched, especially when it deallocates a
>       large data structure that has just been dropped.
> What if the reference counts are stored somewhere else?
> Interlisp-D had a couple of hash tables (for objects with count = 0 and
> objects with count > 1); the effect was that counts were physically
> separated from the objects they guarded.

That only helps for known leaf objects.  When you drop the last
reference to an object, the refcounter must scan it to find all the
pointers, decrement all the associated reference counts, and recurse
if necessary.  If this object was the root of a large structure,
that's a lot of memory which a tracing collector would never have
touched.  Even if you have code to avoid traversing leaf objects, this
is still a big lose for reference counting.

> What if you use lazy freeing?

Then it's not so bad.  If you don't scan an object on the zero-count
queue until you want to allocate it, then you're about to touch it
again anyway.  But totally lazy freeing has its disadvantages.  For
instance, it doesn't play well with best-fit allocation.

Nick Barnes
Ravenbrook Limited