This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Faster Reference Counting [was faster compilation speed]

Tim Hollebeek <tim at hollebeek dot com> wrote:


> 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

{       if (obj->rc >= 0)
{       if (obj->rc >= 0)
                if (--obj->rc == 0)

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

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).


Eliot Miranda              Smalltalk - Scene not herd

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]