I had a different ideas to solve this performance problem and perhaps others. It's only half baked, but I thought it was at least worth mentioning in an e-mail. The premise is that the garbage collector tracks a lot of objects that will never participate in cycles and can never participate in cycles. The idea is to avoid tracking objects until it becomes possible for them to participate in a collectible cycle.
For example, an object referenced from a local variable will never be collected until after the frame releases its reference. So what if we did not track objects that were stored in local variables? To make this work, we would need to change the SETLOCAL macro in ceval to track the object that it was DECREFing. There are a lot of little details that would make this complicated unfortunately. All new container objects are tracked, so we would need to untrack ones that are stored in local variables. To track objects on DECREF, we would also need to ask if the object type was GC-enabled.
Another kind of object that is never going to participate in a cycle, I think, is an object that lives only temporarily on the ceval stack. For example, a bound method object created on the stack in order to be called. If it's never bound to another object as an attribute or stored in local variable, it can never participate in the cycle.
How hard would it be to add logic that avoided tracking objects until it was plausible that they would participate in a cycle?