This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Speed up binary shifting operators
Type: performance Stage: patch review
Components: Interpreter Core Versions: Python 3.11
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: mark.dickinson, serhiy.storchaka, xuxinhang
Priority: normal Keywords: patch

Created on 2021-12-12 05:33 by xuxinhang, last changed 2022-04-11 14:59 by admin.

Pull Requests
URL Status Linked Edit
PR 30044 merged xuxinhang, 2021-12-12 05:33
PR 30243 merged mark.dickinson, 2021-12-23 14:29
PR 30277 open mark.dickinson, 2021-12-27 22:15
Messages (6)
msg408362 - (view) Author: Xinhang Xu (xuxinhang) * Date: 2021-12-12 05:33
See its PR.

---------

Inspired by [bpo-44946](https://bugs.python.org/issue44946), I found there were no special shortcuts for shifting operation applied to "medium value" long object. So I modified CPython's VM to accelerate my python project where there is plenty of binary shifting operation. I guess somebody else might also need it.
msg408372 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2021-12-12 09:58
Could you please show any microbenchmarking results?
msg408385 - (view) Author: Xinhang Xu (xuxinhang) * Date: 2021-12-12 13:26
I post a comment to the PR showing its performance improvement. I paste it below. I think the result not bad.

-------------

I use timeit to measure time costs and any other operators or calls are excluded. For each testcase, the former is dcd2796 and the latter is this PR's base 036bbb1.

64-bit Release building. Run in Windows 10 1709 (64-bit)

python -m timeit " i = 1; i <<= 3; i >>= 3"  # small value (cost down by 36%)
5000000 loops, best of 5: 92.7 nsec per loop
2000000 loops, best of 5: 145 nsec per loop

python -m timeit " i = 1; i <<= 10; i >>= 10"  # medium value (-25%)
2000000 loops, best of 5: 114 nsec per loop
2000000 loops, best of 5: 151 nsec per loop

python -m timeit " i = 1; i <<= 100; i >>= 100"  # big value  (-12%)
1000000 loops, best of 5: 209 nsec per loop
1000000 loops, best of 5: 238 nsec per loop
msg409237 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-12-27 18:04
New changeset 360fedc2d2ce6ccb0dab554ef45fe83f7aea1862 by Mark Dickinson in branch 'main':
bpo-46055: Streamline inner loop for right shifts (#30243)
https://github.com/python/cpython/commit/360fedc2d2ce6ccb0dab554ef45fe83f7aea1862
msg409239 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-12-27 18:37
New changeset 3581c7abbe15bad6ae08fc38887e5948f8f39e08 by Xinhang Xu in branch 'main':
bpo-46055: Speed up binary shifting operators (GH-30044)
https://github.com/python/cpython/commit/3581c7abbe15bad6ae08fc38887e5948f8f39e08
msg409240 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-12-27 18:40
Two separate significant improvements have been pushed: thanks, Xinhang Xu!

The original PR also contained a reworking of the general case for right-shifting a negative integer. The current code (in main) for that case does involve some extra allocations, and it ought to be possible to write something that doesn't need to allocate temporary PyLongs.
History
Date User Action Args
2022-04-11 14:59:53adminsetgithub: 90213
2021-12-27 22:15:42mark.dickinsonsetpull_requests: + pull_request28493
2021-12-27 18:40:50mark.dickinsonsetmessages: + msg409240
2021-12-27 18:37:01mark.dickinsonsetmessages: + msg409239
2021-12-27 18:04:56mark.dickinsonsetmessages: + msg409237
2021-12-23 14:29:12mark.dickinsonsetkeywords: + patch
stage: patch review
pull_requests: + pull_request28464
2021-12-23 14:16:56mark.dickinsonsetnosy: + mark.dickinson
2021-12-12 13:26:15xuxinhangsetmessages: + msg408385
2021-12-12 09:58:30serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg408372
2021-12-12 05:33:38xuxinhangcreate