A couple more observations:

1. I think you're missing the final multiplication by Py_SIZE(b) in the fast_mod code. Which is odd, because your tests should catch that. So either you didn't run the tests, or that code path isn't being used somehow.

2. Talking of tests, it would be good to have tests (for both // and %) for the case where the dividend is an exact multiple of the divisor.

3. Negative divisors almost never come up in real life, so you might also consider restricting the optimisations to the case Py_SIZE(b) == 1 (rather than ABS(Py_SIZE(b)) == 1). If that makes any speed difference at all for the case of positive divisors, then it's probably worth it. If not, then don't worry about it.