I think it would be helpful to have something as troubleshooting information on the garbage collector. If you've got a bug in your C module, it's obvious that you shouldn't be doing something egregiously wrong, but it's not obvious what you might have done wrong in order to cause that particular failure.

It wouldn't be useful to promise that, if you have a particular sort of bug, you'll get a particular sort of failure, or keep it the same from version to version, but it would be nice to be told, if you're getting tp_clear called on objects that aren't garbage in this particular version of Python, look for cases where you're calling py_VISIT on it more times than you called Py_INCREF. Alternatively, it would be helpful for the API documentation to say, "If you are having some strange problem with garbage collection, here's documentation (Developer Guide link) on what's really going on in the garbage collector, which might help explain what you could be doing wrong to get that effect."

For that matter, the documentation for tp_traverse doesn't mention that you have to call Py_VISIT on each object exactly as many times as references you hold to it; the phrasing sounds like it's fine so long as you call it at least once on any object you hold a reference to.