> I don't want guaranteed O(1) behaviour, just O(1) for the common case
> of creating a class, or a few classes, and then removing them.

Then just make sure you call remove_subclass() before PyObject_ClearWeakRefs()
in type_dealloc().

Really, this thing should be demonstrably correct. Performance of dynamic
class creation is not critical enough to take shortcuts.