Skip to content

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

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.

Sign up for GitHub

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
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
Loading

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

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

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 reviewed changes
mdickinson
mdickinson commented Dec 27, 2021
View reviewed changes
mdickinson
mdickinson commented Dec 28, 2021
View reviewed changes
@mdickinson
Copy link
Member Author

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 reviewed changes
@mdickinson mdickinson added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jan 9, 2022
@bedevere-bot
Copy link

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

If you want to schedule another build, you need to add the ":hammer: 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

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

If you want to schedule another build, you need to add the ":hammer: 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 reviewed changes
Copy link
Member

@markshannon markshannon left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@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

@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

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

If you want to schedule another build, you need to add the ":hammer: 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

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

@markshannon markshannon merged commit 0ed91a2 into python:main May 2, 2022
@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 markshannon left review comments

@serhiy-storchaka serhiy-storchaka Awaiting requested review from 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