[gclist] Fast-allocating non-copying GC's

Charles Fiterman cef@geode.geodesic.com
Wed, 6 Mar 1996 07:12:57 -0600


----- Begin Included Message -----

>From maki!iecc.com!owner-gclist Tue Mar  5 15:02 CST 1996
>Received: from miso.wwa.com by maki.wwa.com with smtp
	(Smail3.1.29.1 #3) id m0tu2sL-000rcia; Tue, 5 Mar 96 13:58 CST
Date: Tue, 5 Mar 1996 14:25:58 -0500
From: leichter@smarts.com (Jerry Leichter)


> While it doesn't solve the general problem, you can easily cut the overhead in 
> half, using an old trick:  Use just a single pointer field, and store the XOR of 
> the forward and backward pointers.  Given actual pointers to any two consecutive 
> entries, you can step either forward or backward one link by XOR'ing the 
> appropriate link field with the address of the "other" object.  The added cost, 
> on modern machines, should be minimal, well below the likely amortized memory 
> access costs that you'll have to pay anyway as you walk around the treadmill.

Not only doesn't it solve the general problem it doesn't solve the specific one.
The reason for the doubly linked list is so items picked by pointers outside the
list can be moved from one list to another.

In creating a wrapped pointer class for C++ the problems become even worse. To
support object composition we keep the collector info separate. The object points
to it, and it points back. In the case of object composition there will be multi
pointers to the same info. But not only do we allow object composition and
inheritance we allow instances of collectible classes to be static, stack or
inside non collectible objects.