Circular references and python

Tim Peters tim_one at
Fri Feb 4 03:26:22 EST 2000

[posted & mailed]

[nascheme at]
> I have been looking at Toby Kelsey's code [a gc patch posted to
> a while ago].  It seems quite interesting.  Do you think
> something like it would have a chance to be accepted by Guido?

Yes.  I've studied the code (at Guido's suggestion, actually), and
corresponded with Toby about it.  Toby probably invented this approach on
his own, but Rafael Lins has published a great deal about it under the name
"lazy cyclic reference counting".  It has many attractions!  Like it's
(well, can be made) 100% portable in strictly std C, builds on the current
rc (which many people like) rather than replacing it, is theoretically
sound, and extension modules that don't play along can't cause incorrect
behavior (this is a real problem for Python! any scheme has to work well
with what's already out in the field).

Also one nasty drawback, alas:  despite all the effort Lins and colleagues
have put into refining "this kind of" scheme, they're (at least not as of
1996) sanguine about getting it to run really fast except in special
situations.  Toby actually has a nice twist on the idea that may be a real
help there.

> Perhaps you can also explain why splay trees are used.  There
> doesn't seem to be any need to keep things sorted.  I don't fully
> understand the code yet so perhaps I am missing something.

I dislike the splay trees myself -- it's just a way of representing a set of
objects (the ordering property of splay trees in particular is never used,
so all those hairy rotations don't really buy anything in return).  And the
pointer-chasing code needs to be distributed across object implementations
and dispatched to via a new slot in type objects.  And the patch as it was
posted doesn't actually find the most common cases of Python cycles, because
it never considers instance objects to be "suspicious".

Toby broadly agreed with all that, but it appears the son of a bitch went
and got himself a job <wink>, and dropped this.  I haven't been able to make
time to pursue it myself, and don't expect to be able to in the foreseeable
future.  I believe it would take about two weeks of work (mostly to slash
space and time use) to say for sure whether it's "good enough" for
production use.

Did you just volunteer <wink>?

BTW, in my eyes (and Guido's too, to the extent that he can't tell us
apart), it's the most promising approach currently on the table, and Toby
gets a lot of thanks for that!

> Thanks for your always entertaining posts in c.l.p.

stop-sucking-up-you're-embarrassing-us-both<wink>-ly y'rs  - tim

More information about the Python-list mailing list