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, what are your thoughts?

Note that sort()'s type specialization is much more involved, writing its own comparison functions for a number of common types. This, in contrast, is more just applying strength reduction to the single "don't know what the type is and don't care - only care whether comparands are the same type, in which case the type-specific comparison function doesn't need to be deduced again" case. This is done on the fly, as needed; no pre-scan required, so no change to O() behavior.

The code seems pretty straightforward to me, and Dennis's timing results do show significant speedups for typical type-homogeneous cases, even for short lists. I think it would help if comments were added to point out which parts are logically necessary, and which just to speed typical cases.

Tim, thanks for looking at this. It is not aways clear how far we should go.

It is not always clear how far we should go.

No argument here! IMO, "too many" changes go in that add too much complexity for too little gain. The changes here are conceptually simple, though, and the "1.31x faster" overall result looks credible, well-motivated, and more robust than the kinds of changes that make seemingly random changes to C spellings that yield seeming random "1.04x faster" results on some platforms, but also minor slowdowns on others 😉. We're actually taking code off critical paths in this one.

Thanks for the reviews!