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.

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

Left shift of zero allocates memory #72057

Closed
AlexGroce mannequin opened this issue Aug 26, 2016 · 18 comments
Closed

Left shift of zero allocates memory #72057

AlexGroce mannequin opened this issue Aug 26, 2016 · 18 comments
Assignees
@mdickinson
Labels
performance Performance or resource usage

Comments

@AlexGroce
Copy link
Mannequin

AlexGroce mannequin commented Aug 26, 2016

BPO 27870
Nosy @mdickinson, @bitdancer, @skrah, @serhiy-storchaka
Files
  • leftshiftalloc.py: Python file exhibiting the bug
  • lshift_zero.patch
  • lshift_zero_v2.patch
    		•

    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 = 'https://github.com/mdickinson'
closed_at = <Date 2016-08-29.18:39:57.725>
created_at = <Date 2016-08-26.19:12:23.598>
labels = ['performance']
title = 'Left shift of zero allocates memory'
updated_at = <Date 2016-12-05.08:49:29.483>
user = 'https://bugs.python.org/AlexGroce'

    bugs.python.org fields:

    activity = <Date 2016-12-05.08:49:29.483>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2016-08-29.18:39:57.725>
closer = 'mark.dickinson'
components = []
creation = <Date 2016-08-26.19:12:23.598>
creator = 'Alex Groce'
dependencies = []
files = ['44236', '44255', '44256']
hgrepos = []
issue_num = 27870
keywords = ['patch']
message_count = 18.0
messages = ['273717', '273725', '273726', '273727', '273729', '273730', '273731', '273739', '273740', '273861', '273862', '273863', '273873', '273877', '273878', '273879', '282293', '282400']
nosy_count = 6.0
nosy_names = ['mark.dickinson', 'r.david.murray', 'skrah', 'python-dev', 'serhiy.storchaka', 'Alex Groce']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue27870'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6']
    @AlexGroce
    Copy link
    Mannequin Author

    AlexGroce mannequin commented Aug 26, 2016

    Using a random testing system to compare Python long behavior to GMP (via gmpy2), I notice that in a low-memory situation (created by allocating many large integers in both Python and GMP), a left-shift of 0 by large number of bytes:

    • returns 0 via gmpy2
    • causes a memory error in Python, e.g.:

    ...
    val4 = val3 << val4
    val3: 0 (GMP) 0 (Python)
    val4: 1459166279268040830 (GMP) 1459166279268040830 (Python)
    [operation successful via GMP]
    Python(4463,0x7fff7152c300) malloc: *** mach_vm_map(size=194555503902408704) failed (error code=3)
    *** error: can't allocate region
    *** set a breakpoint in malloc_error_break to debug

    Auto-generated test is attached, though probably not needed to understand the issue. File is not minimized, since I suspect most of the code is just to choke memory, and you probably need the right memory config to replay, but it shows the basic idea.

    For more info, see https://github.com/agroce/tstl/tree/master/examples/gmpy2

    @AlexGroce AlexGroce mannequin added the performance Performance or resource usage label Aug 26, 2016
    @AlexGroce
    Copy link
    Mannequin Author

    AlexGroce mannequin commented Aug 26, 2016

    (to clarify:

    0 << N

    allocates memory (which can fail, raising MemoryError) based on N. GMP simply returns 0 for any N.

    @AlexGroce
    Copy link
    Mannequin Author

    AlexGroce mannequin commented Aug 26, 2016

    AND, right shift >> does not allocate memory, so there is a lack of symmetry that indicates the optimization might be desired.

    see

    https://github.com/agroce/tstl/tree/master/examples/gmpy2/leftshiftalloc.py
    vs.
    https://github.com/agroce/tstl/tree/master/examples/gmpy2/rightshiftalloc.py

    to compare behaviors, but these are depending on memory size, this was generated on MacBook Pro OS X Yosemite machine with 16GB)

    @bitdancer
    Copy link
    Member

    Are you saying that Python aborts, or that it raises a MemoryError?

    @AlexGroce
    Copy link
    Mannequin Author

    AlexGroce mannequin commented Aug 26, 2016

    Allocates, then fails to perform the operation (with MemoryError). Neither a crash nor resource allocation, precisely, just fails to carry out operation GMP integers can do under the same circumstances.

    @bitdancer
    Copy link
    Member

    If it raises a MemoryError, then it is working as designed. Returning 0 would be the wrong answer, so I don't understand why GMP would do that.

    @bitdancer
    Copy link
    Member

    Wait, when you talk about 'long', are you using that in the C sense? Because python long integers are size-limited only by the amount of memory.

    @AlexGroce
    Copy link
    Mannequin Author

    AlexGroce mannequin commented Aug 26, 2016

    I mean a Python long. GMP mpz (via gmpy2) is supposed to be "drop-in" replacement, but it's choice to handle 0 << N even if N is too large to allocate (since you get back a 1-bit number, 0) seems reasonable, if not required for correct behavior. If this is by design, it seems reasonable (if the zero check is considered too expensive, for example).

    @bitdancer
    Copy link
    Member

    Oh, my apologies. I was not reading your message with enough attention, you are only talking about the zero case. A check for zero would not be crazy, and I think there are enough operations involved in left shift that the performance impact would not be measurable. I'll leave that to the math experts, though.

    @mdickinson
    Copy link
    Member

    Also applies to 3.x. Working on a fix.

    @mdickinson mdickinson self-assigned this Aug 29, 2016
    @mdickinson
    Copy link
    Member

    Here's a patch against 3.6. I think this probably shouldn't be changed for 3.5, but it may be worth backporting the fix to 2.7.

    @mdickinson
    Copy link
    Member

    Updated patch, breaking out the implementation-specific tests into their own method. (Thanks, Serhiy!)

    @serhiy-storchaka
    Copy link
    Member

    LGTM.

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Aug 29, 2016

    New changeset 09fa42818cf8 by Mark Dickinson in branch 'default':
    Issue bpo-27870: A left shift of zero by a large integer no longer attempts to allocate large amounts of memory.
    https://hg.python.org/cpython/rev/09fa42818cf8

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Aug 29, 2016

    New changeset 58ea646ef657 by Mark Dickinson in branch '2.7':
    Issue bpo-27870: A left shift of zero by a large integer no longer attempts to allocate large amounts of memory.
    https://hg.python.org/cpython/rev/58ea646ef657

    @mdickinson
    Copy link
    Member

    Fixed for 2.7 and 3.6. Closing.

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Dec 3, 2016

    New changeset 2b190bfd9ab4 by Benjamin Peterson in branch '2.7':
    fix refleak in the shift-by-zero case (bpo-27870)
    https://hg.python.org/cpython/rev/2b190bfd9ab4

    @mdickinson
    Copy link
    Member

    Gah. Sorry about that. Thanks for the refleak fix, Benjamin.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees

    @mdickinson mdickinson

    Labels
    performance Performance or resource usage
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    3 participants
    @bitdancer @mdickinson @serhiy-storchaka