X Tutup
The Wayback Machine - https://web.archive.org/web/20221223135728/https://github.com/python/cpython/pull/30277
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

Jump to bottom

gh-90213: Speed up right shifts of negative integers #30277

Merged
merged 15 commits into from May 2, 2022
Merged

gh-90213: Speed up right shifts of negative integers #30277

merged 15 commits into from May 2, 2022

Conversation

mdickinson
Copy link
Member

@mdickinson mdickinson commented Dec 27, 2021 •
edited

Taking some ideas from the work of @xuxinhang in #30044, this PR makes right shift of negative integers more efficient, by avoiding the need for temporary intermediate results.

Closes #90213

https://bugs.python.org/issue46055

@mdickinson
Copy link
Member Author

mdickinson commented Dec 27, 2021

One example timing: evaluating -7**100 >> 123 is approximately twice as fast on this branch as on main:

lovelace:cpython mdickinson$ git rev-parse main
3581c7abbe15bad6ae08fc38887e5948f8f39e08
lovelace:cpython mdickinson$ git rev-parse faster-rshift-of-negative
9bf9dcdd3342e9e770de23439065d46e07401a5c
lovelace:cpython mdickinson$ git checkout -q faster-rshift-of-negative && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -7**100; b=123" "a>>b"
5000000 loops, best of 5: 44.8 nsec per loop
lovelace:cpython mdickinson$ git checkout -q main && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -7**100; b=123" "a>>b"
5000000 loops, best of 5: 95 nsec per loop

@mdickinson
Copy link
Member Author

mdickinson commented Dec 27, 2021

Smaller and larger examples also benefit on my machine: -1234567890 >> 8 is approximately 1.9 times faster; -7**100000 >> 12345 is approximately 2.8 times faster:

lovelace:cpython mdickinson$ git checkout -q main && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -1234567890; b=8" "a>>b"
5000000 loops, best of 5: 81.5 nsec per loop
lovelace:cpython mdickinson$ git checkout -q faster-rshift-of-negative && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -1234567890; b=8" "a>>b"
5000000 loops, best of 5: 42.6 nsec per loop
lovelace:cpython mdickinson$ git checkout -q main && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -7**100000; b=12345" "a>>b"
20000 loops, best of 5: 19.3 usec per loop
lovelace:cpython mdickinson$ git checkout -q faster-rshift-of-negative && make >/dev/null 2>&1 && ./python.exe -m timeit -s "a = -7**100000; b=12345" "a>>b"
50000 loops, best of 5: 6.82 usec per loop

mdickinson
mdickinson commented Dec 27, 2021
View changes
Objects/longobject.c Outdated Show resolved Hide resolved
mdickinson
mdickinson commented Dec 27, 2021
View changes
Objects/longobject.c Outdated Show resolved Hide resolved
mdickinson
mdickinson commented Dec 28, 2021
View changes
Objects/longobject.c Outdated Show resolved Hide resolved
@mdickinson
Copy link
Member Author

mdickinson commented Dec 28, 2021

I've reworked to remove the duplication between the positive and negative branches, and to move the shift==0 check earlier.

@mdickinson mdickinson added performance Performance or resource usage and removed skip news labels Dec 28, 2021
mdickinson
mdickinson commented Dec 28, 2021
View changes
Objects/longobject.c Outdated Show resolved Hide resolved
@mdickinson mdickinson added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jan 9, 2022
@bedevere-bot
Copy link

bedevere-bot commented Jan 9, 2022

🤖 New build scheduled with the buildbot fleet by @mdickinson for commit b3a1a8f 🤖

If you want to schedule another build, you need to add the "🔨 test-with-buildbots" label again.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jan 9, 2022
@mdickinson mdickinson added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jan 9, 2022
@bedevere-bot
Copy link

bedevere-bot commented Jan 9, 2022

🤖 New build scheduled with the buildbot fleet by @mdickinson for commit fd4ce81 🤖

If you want to schedule another build, you need to add the "🔨 test-with-buildbots" label again.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jan 9, 2022
@github-actions
Copy link

github-actions bot commented Feb 9, 2022

This PR is stale because it has been open for 30 days with no activity.

@github-actions github-actions bot added the stale Stale PR or inactive for long period of time. label Feb 9, 2022
@markshannon markshannon self-assigned this Feb 28, 2022
markshannon
markshannon reviewed Mar 1, 2022
View changes
Copy link
Member

@markshannon markshannon left a comment

I'm not sure that I understand 100%, but I think it is correct and it does pass the tests.

A few of the variables could have their scope narrowed.

Objects/longobject.c Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
Objects/longobject.c Outdated Show resolved Hide resolved
@mdickinson mdickinson removed the stale Stale PR or inactive for long period of time. label Apr 12, 2022
@mdickinson mdickinson changed the title bpo-46055: Speed up right shifts of negative integers gh-90213: Speed up right shifts of negative integers Apr 12, 2022
@mdickinson
Copy link
Member Author

mdickinson commented Apr 12, 2022

@markshannon Thanks for the review! I've addressed your comments, and I think this should be ready for re-review.

@mdickinson mdickinson added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Apr 12, 2022
@bedevere-bot
Copy link

bedevere-bot commented Apr 12, 2022

🤖 New build scheduled with the buildbot fleet by @mdickinson for commit c5e3f81 🤖

If you want to schedule another build, you need to add the "🔨 test-with-buildbots" label again.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Apr 12, 2022
@markshannon
Copy link
Member

markshannon commented May 2, 2022

AFAICT this looks good, and all the buildbots are happy.

@markshannon markshannon merged commit 0ed91a2 into python:main May 2, 2022
13 checks passed
@xuxinhang xuxinhang mannequin mentioned this pull request Apr 10, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@markshannon markshannon

@serhiy-storchaka serhiy-storchaka

Assignees

@markshannon markshannon

Labels
performance Performance or resource usage
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Speed up binary shifting operators
5 participants
@mdickinson @bedevere-bot @markshannon @serhiy-storchaka @the-knights-who-say-ni
X Tutup