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

Speed up binary shifting operators #90213

Closed
xuxinhang mannequin opened this issue Dec 12, 2021 · 6 comments · Fixed by #30277
Closed

Speed up binary shifting operators #90213

xuxinhang mannequin opened this issue Dec 12, 2021 · 6 comments · Fixed by #30277
Labels
3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@xuxinhang
Copy link
Mannequin

xuxinhang mannequin commented Dec 12, 2021

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
    Copy link
    Mannequin Author

    xuxinhang mannequin commented 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.

    @xuxinhang xuxinhang mannequin added 3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Dec 12, 2021
    @serhiy-storchaka
    Copy link
    Member

    Could you please show any microbenchmarking results?

    @xuxinhang
    Copy link
    Mannequin Author

    xuxinhang mannequin commented 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
    Copy link
    Member

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

    @mdickinson
    Copy link
    Member

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

    @mdickinson
    Copy link
    Member

    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.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    @mdickinson mdickinson mentioned this issue Apr 12, 2022
    Merged
    markshannon pushed a commit that referenced this issue May 2, 2022
    @mdickinson
    gh-90213: Speed up right shifts of negative integers (GH-30277)
    0ed91a2
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Milestone
    No milestone
    Development

    Successfully merging a pull request may close this issue.

    gh-90213: Speed up right shifts of negative integers mdickinson/cpython
    2 participants
    @mdickinson @serhiy-storchaka