Speed up binary shifting operators

[xuxinhang]

BPO	46055
Nosy	@mdickinson, @serhiy-storchaka, @xuxinhang
PRs	bpo-46055: Speed up binary shifting operators #30044 bpo-46055: Streamline inner loop for right shifts #30243 gh-90213: Speed up right shifts of negative integers #30277

^{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']

[xuxinhang]

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]

Could you please show any microbenchmarking results?

[xuxinhang]

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]

New changeset 360fedc by Mark Dickinson in branch 'main':
bpo-46055: Streamline inner loop for right shifts (bpo-30243)
360fedc

[mdickinson]

New changeset 3581c7a by Xinhang Xu in branch 'main':
bpo-46055: Speed up binary shifting operators (GH-30044)
3581c7a

[mdickinson]

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.