Skip to content

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

Closed
sweeneyde opened this issue Sep 3, 2022 · 2 comments
Closed

Take advantage of type uniformity in _bisect.bisect() #96538

sweeneyde opened this issue Sep 3, 2022 · 2 comments
Labels
performance Performance or resource usage type-feature A feature request or enhancement

Comments

@sweeneyde
Copy link
Member

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.

@sweeneyde sweeneyde added type-feature A feature request or enhancement performance Performance or resource usage labels Sep 3, 2022
@rhettinger
Copy link
Contributor

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

@rhettinger rhettinger changed the title Take advantage of type stability in _bisect.bisect() Take advantage of type uniformity in _bisect.bisect() Sep 4, 2022
@tim-one tim-one removed their assignment Sep 4, 2022
@tim-one
Copy link
Member

tim-one commented Sep 4, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Performance or resource usage type-feature A feature request or enhancement
Projects
None yet
Development

No branches or pull requests

3 participants