Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[kevinw@whistler.com (Kevin Warne)]

In article <3bii2g$kn2@news.parc.xerox.com>, boehm@parc.xerox.com (Hans Boehm) says:
>beckwb@ois.com (R. William Beckwith) writes:
>>Paul Wilson's RT, generational, incremental GC'tor causes work
>>when the graph of objects is changed (write barrier).  Surely,
>>the color changes required with a graph change can be as fast
>>as a simple incr/decr operation.
>
>You do need at least a write barrier on the heap for incremental collection.
>(In the best case, the dirty bits in the MMU are a sufficient
>write barrier, though not for that algorithm.  But using them is likely

Can you think of a realistic incremental collection algorithm 
that uses MMU dirty bits?  At best I suppose a collector could perform
a collection and then freeze the application while it rescanned
pointers in areas covered by dirty bits.

>to increase collector latency, though probably not above the simple RC scheme.
>And your machine may not have hardware dirty bits, though the Intel
>architecture does.  And your OS may already need those bits for other
>things, adding a bit of overhead.)

And don't forget all those OSs who keep the dirty bits to themselves.
Just imagine the hell involved to access those bits under the likes
of Windows NT and OS/2 (and other operating systems).

Still, it would turn card-marking into a win, wouldn't it...

>The crucial issue in my mind is whether you can safely avoid counting
>pointers from the stack.

Any incremental collector (RC or tracing) is going to need a stack
barrier unless either A) stacks are scanned atomically at the end of a 
collection period along with the objects that they reference or B) 
stack objects have restrictions during collection about what kind of
heap objects they may point to.  Otherwise stack-based references can 
circumvent heap barriers.

Kevin

____
Kevin Warne / kevinw@whistler.com / DDD +1 604 932 0606 / FAX +1 604 598 9546
Suite 204, 1200 Alpha Lake Road, Whistler, BC, CANADA  V0N 1B0
Warne's Garbage Collector (WGC) = The best way to allocate memory in C++