Repository navigation
Speed up binary shifting operators #90213
Description
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = None
created_at = <Date 2021-12-12.05:33:38.006>
labels = ['interpreter-core', '3.11', 'performance']
title = 'Speed up binary shifting operators'
updated_at = <Date 2021-12-27.22:15:42.571>
user = 'https://github.com/xuxinhang'bugs.python.org fields:
activity = <Date 2021-12-27.22:15:42.571>
actor = 'mark.dickinson'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2021-12-12.05:33:38.006>
creator = 'xuxinhang'
dependencies = []
files = []
hgrepos = []
issue_num = 46055
keywords = ['patch']
message_count = 6.0
messages = ['408362', '408372', '408385', '409237', '409239', '409240']
nosy_count = 3.0
nosy_names = ['mark.dickinson', 'serhiy.storchaka', 'xuxinhang']
pr_nums = ['30044', '30243', '30277']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue46055'
versions = ['Python 3.11']
Activity
xuxinhang commentedon Dec 12, 2021
See its PR.
---------
Inspired by bpo-44946, 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.
serhiy-storchaka commentedon Dec 12, 2021
Could you please show any microbenchmarking results?
xuxinhang commentedon Dec 12, 2021
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
mdickinson commentedon Dec 27, 2021
New changeset 360fedc by Mark Dickinson in branch 'main':
bpo-46055: Streamline inner loop for right shifts (bpo-30243)
360fedc
mdickinson commentedon Dec 27, 2021
New changeset 3581c7a by Xinhang Xu in branch 'main':
bpo-46055: Speed up binary shifting operators (GH-30044)
3581c7a
mdickinson commentedon Dec 27, 2021
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.
gh-90213: Speed up right shifts of negative integers (GH-30277)