> it could also be done at instantiation time (the attached patch
> uses __init_subclass__ for that purpose 

FWIW, a 10-25% speedup is only possible because the remaining code is already somewhat fast.  All that is being proposed is removing couple of lines that elsewhere would be considered somewhat thin:

        random = self.random
        if type(random) is BuiltinMethod \
           or type(getrandbits) is Method:

Overall, the idea of doing the check only once at instantiation time seems promising.  That said, I have unspecific general worries about using __init_subclass__ and patching the subclass.  Perhaps Serhiy, Tim, or Mark will have thoughts on whether this sort of self-patching is something we want to be doing in the standard library, whether it would benefit PyPy, and whether it has risks to existing code, to debugging and testing, and to future maintenance.

If I were the one to go the route of making a single pre-check, my instinct would be to just set a flag in __init__, so that the above code would simplify to:

        if self._valid_getrandbits:
            ...