-
-
Notifications
You must be signed in to change notification settings - Fork 31.8k
Take advantage of type uniformity in _bisect.bisect() #96538
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Comments
With sorting, which is potentially 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:
|
As I noted on the pull request (#96539), I think the cost/benefit ratio of this is attractive. |
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:
tp->tp_as_sequence->sq_item
i < 0
, so no need to adjust indiceslist.sort()
's unsafe_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.Much of this work can be moved outside the loop, so that instead of happening
lg(n)
times, it only needs to happened once.The text was updated successfully, but these errors were encountered: