Skip to content
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

Optimise x%N == M for constant divisors #2846

Open
scoder opened this Issue Feb 15, 2019 · 0 comments

Comments

Projects
None yet
1 participant
@scoder
Copy link
Contributor

scoder commented Feb 15, 2019

There is templated special-casing code in Optimize.c (look for PyIntBinop, used in Optimize.py) which implements several binary integer operations with constant numbers on one side. In a similar way, the Python expression x%N == 0, or, more generally, x%N == M (with N and M constant) could be folded into a single C helper function, which would avoid the intermediate creation of a Python integer object just for the modulus.

In the case where the expression is used directly in an if-statement (and thus coerced to a bint), it could even return a plain C int 0 or 1 instead of True or False as Python objects, thus avoiding object creations and refcounting entirely.

As a bonus, this blog post by Daniel Lemire describes ways to speed up modulo calculations. While most of them seem best left to the C compiler, the divisibility check for the common case of unsigned 32bit integers seems appealing for an optimisation in Cython. It uses only a single multiplication instead of division. See the implementations in https://github.com/lemire/fastmod/blob/master/include/fastmod.h

And it looks like the opposite (N%x == 0) can also be evaluated more efficiently with multiplication instead of division.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.