gyro@kestrel.edu (Scott Layson Burson) (04/24/91)
In article <1991Apr22.165825.13552@cpsc.ucalgary.ca> gintera@fsd.cpsc.ucalgary.ca (Andrew Ginter) writes: >In article <DAVIS.91Apr22105508@barbes.ilog.fr> davis@barbes.ilog.fr (Harley Davis) writes: >>One of the most important problems with reference counting is that it >>doesn't collect all the garbage. In particular, circular data >>structures never get collected. > >This was true of reference counting schemes until 1986. An article >published in Software-Practice and Experience that year describes how >reference counting systems can reclaim circular lists fairly simply. >The exact name and author of the article escape me right now - they're >in my other office. Drop me a note if you're desperate and I can dig >them up for you. > >The circular list collection technique goes something like this: > >* Scan the collected heap. For each object in the heap, chase all > pointers in the object and decrement the refcount on the target > object. At the end of the scan, all of the contribution of internal > pointers to refcount fields has been eliminated. > >* Scan the heap again. Mark any object with a non-zero refcount > field. These are the objects which are referenced by "root > pointers" (pointers which reside outside of the heap and which refer > to collected objects). > >* Scan the heap again. Recursively mark any object with a non-zero > refcount, incrementing reference counts as you traverse pointers in > objects. > >* Scan the heap again. Any objects in the heap which still has a zero > reference count can be reclaimed - these are the objects which were > part of unreachable circular lists. This is, of course, a garbage collection algorithm. What you are essentially pointing out here is that garbage collection and reference counting are not mutually exclusive. There is a more subtle point as well. Garbage collection normally requires the ability to scan the stack, and to know (either exactly or by conservative approximation) what stack words contain pointers to heap objects, so that those objects may be marked as "live". This algorithm avoids the necessity to scan the stack by making use of the information already encoded in the reference counts. This is very clever and I may actually use it for something. Thank you for describing it! [BTW, seems to me the second and third steps can be combined in a single scan.] -- Scott Gyro@Reasoning.COM