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

[Steve Heller - Sun Microsystems Labs BOS]

	From: leichter@smarts.com (Jerry Leichter)
	To: gclist@iecc.com
	Subject: Re: [gclist] Fast-allocating non-copying GC's
	
	|     [...] If you use fake copying (e.g., treadmill, or our variant)
	| Sure, but there is an enormous space overhead:  For the treadmill, it
	| takes two pointers per object to maintain the doubly-linked list,
	| which is a major lose if you have lots of small objects....

	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.

Maybe this what you mean by "doesn't solve the general problem", but
the XOR trick only helps when you are zooming around the ring one way
and then need to go the other way and stuff like that (connected
successive access).  As you imply, one cannot, however, given one
pointer, do much of anything.  But that's typically the case as I
understand it when you want to move an object from one set to another
(Baker referrs to unsnapping and such).

-steve