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

[Jerry Leichter]

|     [...] If you use fake copying (e.g., treadmill, or our variant) you
|     can allocate almost as fast as with a copying GC, as well as getting
|     back free memory in constant time.
| 
| 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.

							-- Jerry