Warp wrote:

>   I assume that it frees all the objects, not just A, but how does it do
> it efficiently? (I assume this because else in a circular ownership
> situation it would never free any of the objects.)
>   Assume that this chain of objects is very large, consisting of thousands
> of objects.

The simplest (non-broken) GC implementation is the mark/sweep type.

That is, you mark all objects as "dead". Then, starting from a set of 
"roots" (typically what's referenced from the execution stack, global 
variables, etc.), you mark each object you touch as "alive", and then 
recurse over all the objects it references. (And if any of those are 
already marked as live, you've obviously "been here" before, so ignore 
that path this time around.)

When you've followed every reference in the system and marked everything 
as live, all objects not marked as live must in fact be dead. These can 
now be deleted.

(This is the theory. In practice, it's common for a compacting GC to 
actually *move* each object as it finds it live, and then simply 
deallocate the space used by the remaining objects. Various other 
optimisations are possible too.)

Therefore, if nobody references A, then A will never be marked live, and 
none of the objects it links to will be marked live either. So a single 
pass of the GC will elide them all.

Trouble with mark/sweep is that you have to stop the program executing 
while you do your sweep, or some object X might be unlinked from one 
place and then relinked from somewhere else, and the GC might scan past 
just as this happens, resulting in an object that's actually live being 
marked as dead and deallocated.

Obviously, stopping your entire program (all parallel threads!) so you 
can run the GC isn't a fantastic idea. So various more sophisticated 
schemes have been invented (e.g., generational GC). In any case, for 
most designs of GC, the entire chain of objects will be reclaimed in a 
single pass of the GC. (Although it might be the next "major" rather 
than "minor" pass or something, depending on the exact design details.)

[Note that I do not consider "reference counting" to be a valid GC 
algorithm, since it doesn't actually work properly...]

Post a reply to this message