[Python-Dev] Re: [Patches] Reference cycle collection for Python

[Jeremy Hylton]

>>>>> "VM" == Vladimir Marangozov <marangoz@python.inrialpes.fr> writes:

  [">>" == Guido explaining Eric Tiedemann's GC design]
  >>  Next, we make another pass over the list to collect the internal
  >> references.  Internal references are (just like in Neil's
  >> version) references from other container types.  In Neil's
  >> version, this was recursive; in Eric's version, we don't need
  >> recursion, since the list already contains all containers.  So we
  >> simple visit the containers in the list in turn, and for each one
  >> we go over all the objects it references and subtract one from
  >> *its* gc_refs field.  (Eric left out the little detail that we
  >> ened to be able to distinguish between container and
  >> non-container objects amongst those references; this can be a
  >> flag bit in the type field.)

  VM> Step 2: c->gc_refs = c->gc_refs -
  VM> Nb_referenced_containers_from_c

  VM> I guess that you realize that after this step, gc_refs can be
  VM> zero or negative.

I think Guido's explanation is slightly ambiguous.  When he says,
"subtract one from *its" gc_refs field" he means subtract one from the
_contained_ object's gc_refs field.  

  VM> I'm not sure that you collect "internal" references here
  VM> (references from other container types). A list referencing 20
  VM> containers, being itself referenced by one container + one
  VM> static variable + two times from the runtime stack, has an
  VM> initial refcount == 4, so we'll end up with gc_refs == -16.

The strategy is not that the container's gc_refs is decremented once
for each object it contains.  Rather, the container decrements each
contained object's gc_refs by one.  So you should never end of with
gc_refs < 0.

  >> During the meeting, I proposed to set the back pointer to NULL;
  >> that might work too but I think the gc_refs field is more
  >> elegant. We could even just test for a non-zero gc_refs field;
  >> the roots moved to the second list initially all have a non-zero
  >> gc_refs field already, and for the objects with a zero gc_refs
  >> field we could indeed set it to something arbitrary.)

I believe we discussed this further and concluded that setting the
back pointer to NULL would not work.  If we make the second list
doubly-linked (like the first one), it is trivial to end GC by
swapping the first and second lists.  If we've zapped the NULL
pointer, then we have to go back and re-set them all.

Jeremy