3 ms·
It's been a little while, but as I remember, the Garbage Collection Handbook (an excellent read if you're into this sort of thing) outlines and cites some exter
by KMag 5y ago
It's been a little while, but as I remember, the Garbage Collection Handbook (an excellent read if you're into this sort of thing) outlines and cites some external work showing tracing garbage collection as a lazily evaluated form of reference counting (using a saturating 1-bit counter) taken to the limit. (Some reference counting systems use a small number of bits for a reference count, and if that reference count hits its max value, then never decrement a counter. Many reference counting systems also incorporate tracing major collections to avoid the cycle problem. If you're going to have a tracing collector, and you assume your high-reference-count objects are likely to be long-lived, then reserving only a small number of bits for the reference count makes sense. Your backup tracing major collector will handle both the cycle problem and the saturating counter problem at no extra cost.)
Eagerly updated single-bit reference counts are useful if you have a lot of code that allocates buffers, passes them to helper functions to get filled (potentially defeating static escape analysis), passes them to consuming functions, and then returns. A single bit to track if a reference to that buffer has ever been stored into another object will allow for early collection in the common case.
On a side note, the Garbage Collection handbook (and many practitioners) consider reference counting to be a form of garbage collection. What some people narrowly define as GC is tracing garbage collection.
- munificent 5y ago> cites some external work showing tracing garbage collection as a lazily evaluated form of reference counting (using a saturating 1-bit counter) taken to the limit. Yup. The paper you're thinking of is "A Unified Theory of Garbage Collection": https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...