[Tim]
Half of a shadow of an idea: at least in my code, it's common to have gazillions of tuples, and they almost always contain just strings and numbers. Since they're immutable, they'll never contain anything else. So they could get unlinked from cyclic gc entirely without ill effect (it's not possible that they could ever be in a cycle). Perhaps a gen2 collection could learn something about this and automagically untrack them.
[MvL]
That could happen in gen0 already: when traversing an object, watch whether it contains any tracked objects. If it doesn't, invoke tp_is_immutable, if that returns true, untrack it.
Unfortunately, the visit API doesn't make it easy to watch this; a tuple calls visit() on its items but learns nothing except whether it failed. (I've never seen a visit() implementation that could fail, so I'm not sure even why the return code exists.) --Guido van Rossum (home page: http://www.python.org/~guido/)