Faster Reference Counting [was faster compilation speed]

[Eliot Miranda <eliotm at pacbell dot net>]

Tim Hollebeek <tim at hollebeek dot com> wrote:

[deletia]

> A simpler strategy is to just make every object with RC >= 2^n
> immortal.  Something like:

> add: if (rc) rc++;

> subtract: if (rc) if (!--rc) delete;

> For a program like gcc that doesn't have to absolutely guarantee it
> leaks no memory, this can be an acceptable tradeoff.

> (for belt and suspenders people, run a infrequent lazy gc to clean up
> the scraps)

> -Tim

I chanced upon the gcc compilation speed thread through gclist (a
GC-specific mailing list).  Peter Deutsch invented a nice trick
for cheaper immortality using byte arithmetic.  The idea is for a
count operation to add or subtract two and mark an overflowing count
odd so that it can never go to zero.  This saves a test in decrement.

e.g. If add/subtract 1 with sign bit for immortality you get

incrc(obj)
{       if (obj->rc >= 0)
                ++obj->rc;
}
decrc(obj)
{       if (obj->rc >= 0)
                if (--obj->rc == 0)
                        reclain(obj);
}

but with add/subtract 2 you get
incrc(obj)
{       if ((obj->rc += 2) == 0)
                obj->rc = 1;
}
decrc(obj)
{       if ((obj->rc -= 2) == 0)
                reclaim(obj);
}

which saves a test on decrement, or about 25% of your ref counting cost
(and note that recursive freeing in reclaim is all decrements).

Also, recursive freeing can be made tail-recursive and hence written
as a loop (this from Glenn Krasner).

HTH...

-- 
_______________,,,^..^,,,____________________________
Eliot Miranda              Smalltalk - Scene not herd