We can makebisect.bisect(seq, i) get roughly 1.3x faster by taking advantage of type stability, of both the sequence and the keys.

Possible opportunities:

• All calls toPySequence_GetItem should use the same underlyingtp->tp_as_sequence->sq_item
• We never call withi < 0, so no need to adjust indices
• Similar to the strategy employed inlist.sort()'sunsafe_object_compare, we can keep atp_richcompare function pointer around, then check types and use it, with less type-checking. We can always fall back toPyObject_RichCompareBool in case some assumption fails.
• Recursion checks only need to happen once per bisect call.

Much of this work can be moved outside the loop, so that instead of happeninglg(n) times, it only needs to happened once.