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

bpo-44376 - reduce pow() overhead for small exponents #26662

Merged
merged 10 commits into from Jun 12, 2021
Merged

Conversation

@tim-one
Copy link
Member

@tim-one tim-one commented Jun 11, 2021

BPO-44376
Reduce pow() overhead for small exponents.
Incidentally fixed a refcount oversight for
negative exponents.

https://bugs.python.org/issue44376

Reduce pow() overhead for small exponents.
Incidentally fixed a refcount oversight for
negative exponents.
@tim-one tim-one changed the title First stab. BPO-44376: reduce pow() overhead for small exponents Jun 11, 2021
@tim-one tim-one changed the title BPO-44376: reduce pow() overhead for small exponents BPO 44376: reduce pow() overhead for small exponents Jun 11, 2021
@tim-one tim-one changed the title BPO 44376: reduce pow() overhead for small exponents #44376: reduce pow() overhead for small exponents Jun 11, 2021
@tim-one tim-one changed the title #44376: reduce pow() overhead for small exponents BOP 44376 - reduce pow() overhead for small exponents Jun 11, 2021
@tim-one tim-one changed the title BOP 44376 - reduce pow() overhead for small exponents BPO 44376 - reduce pow() overhead for small exponents Jun 11, 2021
@JelleZijlstra
Copy link
Member

@JelleZijlstra JelleZijlstra commented Jun 11, 2021

@tim-one I think to get this linked to the bpo issue the PR title needs to be of the form "bpo-44376: reduce pow() overhead for small exponents".

It's annoying, but I don't want to fight about it ;-)
@tim-one tim-one changed the title BPO 44376 - reduce pow() overhead for small exponents bpo-44376 - reduce pow() overhead for small exponents Jun 11, 2021
@tim-one
Copy link
Member Author

@tim-one tim-one commented Jun 11, 2021

the PR title needs to be of the form "bpo-44376: ...."

Wow - that appeared to do the trick! Thank you 😄.

Objects/longobject.c Outdated Show resolved Hide resolved
tim-one and others added 5 commits Jun 11, 2021
instead of left-to-right. This cuts the time for exponent 2
by another 10%. Does that slow things for, e.g., an exponent
like 1 << 20? Sure, by a little.  But that exponent will go
on to do 20 squarings, and the extra native 32-bit shift-
and-tests in the loop are insignificant in comparison. For
a tiny exponent (like 2), the loop's shift-and-tests can
consume a significant part of the total time.

Also reverted the change I made to repair refcounting in
modular inverse code. Mark will make the change in a
distinct PR, and backport it. Without this change, the
"negative refcount" glitch stopped showing up in this PR's
code after I changed it to never return `a` directly.
until the exponent is at least 4. Saves approaching another 10%
for exponent 2.
insteads works OK, but was always a conceptual mess.
Copy link
Member

@mdickinson mdickinson left a comment

LGTM

@tim-one tim-one merged commit 9d8dd8f into python:main Jun 12, 2021
13 checks passed
13 checks passed
@github-actions
Docs
Details
@github-actions
Check for source changes
Details
@github-actions
Check if generated files are up to date
Details
@github-actions
Windows (x86)
Details
@github-actions
Windows (x64)
Details
@github-actions
macOS
Details
@github-actions
Ubuntu
Details
@github-actions
Ubuntu SSL tests with OpenSSL
Details
@github-actions
Address sanitizer Address sanitizer
Details
Azure Pipelines PR #20210612.21 succeeded
Details
@travis-ci
Travis CI - Pull Request Build Passed
Details
@bedevere-bot
bedevere/issue-number Issue number 44376 found
Details
@bedevere-bot
bedevere/news News entry found in Misc/NEWS.d
@tim-one tim-one deleted the tim-one:powdig branch Jun 12, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants