Take advantage of type uniformity in _bisect.bisect()

[sweeneyde]

We can make bisect.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 to PySequence_GetItem should use the same underlying tp->tp_as_sequence->sq_item
• We never call with i < 0, so no need to adjust indices
• Similar to the strategy employed in list.sort()'s unsafe_object_compare, we can keep a tp_richcompare function pointer around, then check types and use it, with less type-checking. We can always fall back to PyObject_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 happening lg(n) times, it only needs to happened once.

[rhettinger]

With sorting, which is potentially O(n log n), there is a large payoff for all this added complexity. With bisect, which is O(log n), the payoff is very low. The granularity is different. We call sorting on a full dataset while bisect calls are one per lookup. You would get a better payoff by type specializing min() and max() than for the handful of comparisons made in a typical call to bisect().

I recognize that there has been a shift in the core developer attitudes towards complexity and that many things we would have never considered now are fair game if some clock cycles can be saved. With the interpreter, there was a high payoff that compensated for fewer people being able to understand and maintain the code. There is less of case to be made for complexifying code on the periphery. It would be nice if some simple things remained simple. At one time, the whole module was basically just this code:

        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1

[tim-one]

As I noted on the pull request (#96539), I think the cost/benefit ratio of this is attractive.