It seems that reference counting traces both the live and dead space, in the sense that refcounts have to be carefully maintained as the ownership sharing is propagated, and then the finalization of a refcounted object can trigger others dead ones to be identified.
Garbage collection culd also trace both spaces. After we have performed the mark phase of basic mark-and-sweep, we could again go back to the root pointers and traverse the object graph again in the asme way, this time looking for objects which are not marked reachable. Similarly to refcounting, we could do the finalization for each such object and then recursively look for others that are unreachable.
We don't do that for various reasons:
- the belief that it's faster to traverse the heaps, even though in doing so, we it may be necessary to skip numerous free objects.
- the use of a copying algorithm, whereby we moved the live objects to a new heap, so there is no need to trace or otherwise traverse the dead space in detail.
The belief is justified because there usually aren't any free objects when GC is spontaneously triggered. A recursive trace vists the entire graph of objects that were previously live, some of which are now dead. A sweep through the heaps visits all the same ones, plus also some entries marked free (of which there are none in a spontaneous GC pass).
But the recursive traversal involves inefficient dependent pointer loads, poor caching, and the visitation of of the same objecct multiple times. While in the case of dead objects, we can easily tell that we are visiting a dead object a second time (the first time we finalized it and marked it free), we have to account for multiple visits to the reachable ones; we have to paint each one a new color to indicate that it was visited in the second pass.
Garbage collection culd also trace both spaces. After we have performed the mark phase of basic mark-and-sweep, we could again go back to the root pointers and traverse the object graph again in the asme way, this time looking for objects which are not marked reachable. Similarly to refcounting, we could do the finalization for each such object and then recursively look for others that are unreachable.
We don't do that for various reasons:
- the belief that it's faster to traverse the heaps, even though in doing so, we it may be necessary to skip numerous free objects.
- the use of a copying algorithm, whereby we moved the live objects to a new heap, so there is no need to trace or otherwise traverse the dead space in detail.
The belief is justified because there usually aren't any free objects when GC is spontaneously triggered. A recursive trace vists the entire graph of objects that were previously live, some of which are now dead. A sweep through the heaps visits all the same ones, plus also some entries marked free (of which there are none in a spontaneous GC pass).
But the recursive traversal involves inefficient dependent pointer loads, poor caching, and the visitation of of the same objecct multiple times. While in the case of dead objects, we can easily tell that we are visiting a dead object a second time (the first time we finalized it and marked it free), we have to account for multiple visits to the reachable ones; we have to paint each one a new color to indicate that it was visited in the second pass.