Left shift of zero allocates memory

[AlexGroce]

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]

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]

(to clarify:

0 << N

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

[AlexGroce]

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]

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

[AlexGroce]

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]

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]

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]

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]

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]

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

[mdickinson]

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]

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

[serhiy-storchaka]

LGTM.