classification
Title: Left shift of zero allocates memory
Type: resource usage Stage: resolved
Components: Versions: Python 3.6, Python 3.5, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: Alex Groce, mark.dickinson, python-dev, r.david.murray, serhiy.storchaka, skrah
Priority: normal Keywords: patch

Created on 2016-08-26 19:12 by Alex Groce, last changed 2016-12-05 08:49 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
leftshiftalloc.py Alex Groce, 2016-08-26 19:12 Python file exhibiting the bug
lshift_zero.patch mark.dickinson, 2016-08-29 14:15 review
lshift_zero_v2.patch mark.dickinson, 2016-08-29 14:40 review
Messages (18)
msg273717 - (view) Author: Alex Groce (Alex Groce) * Date: 2016-08-26 19:12
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
msg273725 - (view) Author: Alex Groce (Alex Groce) * Date: 2016-08-26 20:37
(to clarify:

0 << N

allocates memory (which can fail, raising MemoryError) based on N.  GMP simply returns 0 for any N.
msg273726 - (view) Author: Alex Groce (Alex Groce) * Date: 2016-08-26 20:40
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)
msg273727 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-26 21:34
Are you saying that Python aborts, or that it raises a MemoryError?
msg273729 - (view) Author: Alex Groce (Alex Groce) * Date: 2016-08-26 21:36
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.
msg273730 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-26 21:38
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.
msg273731 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-26 21:41
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.
msg273739 - (view) Author: Alex Groce (Alex Groce) * Date: 2016-08-26 21:54
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).
msg273740 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-26 22:07
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.
msg273861 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-29 14:02
Also applies to 3.x. Working on a fix.
msg273862 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-29 14:15
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.
msg273863 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-29 14:40
Updated patch, breaking out the implementation-specific tests into their own method. (Thanks, Serhiy!)
msg273873 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-08-29 17:25
LGTM.
msg273877 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-08-29 18:27
New changeset 09fa42818cf8 by Mark Dickinson in branch 'default':
Issue #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
msg273878 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-08-29 18:38
New changeset 58ea646ef657 by Mark Dickinson in branch '2.7':
Issue #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
msg273879 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-29 18:39
Fixed for 2.7 and 3.6. Closing.
msg282293 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-12-03 19:04
New changeset 2b190bfd9ab4 by Benjamin Peterson in branch '2.7':
fix refleak in the shift-by-zero case (#27870)
https://hg.python.org/cpython/rev/2b190bfd9ab4
msg282400 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-12-05 08:49
Gah. Sorry about that. Thanks for the refleak fix, Benjamin.
History
Date User Action Args
2016-12-05 08:49:29mark.dickinsonsetmessages: + msg282400
2016-12-03 19:04:03python-devsetmessages: + msg282293
2016-08-29 18:39:57mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg273879

stage: commit review -> resolved
2016-08-29 18:38:25python-devsetmessages: + msg273878
2016-08-29 18:27:57python-devsetnosy: + python-dev
messages: + msg273877
2016-08-29 17:25:36serhiy.storchakasetmessages: + msg273873
stage: commit review
2016-08-29 14:40:25mark.dickinsonsetfiles: + lshift_zero_v2.patch

messages: + msg273863
2016-08-29 14:22:17serhiy.storchakasetnosy: + serhiy.storchaka
2016-08-29 14:15:12mark.dickinsonsetfiles: + lshift_zero.patch
keywords: + patch
messages: + msg273862
2016-08-29 14:02:53mark.dickinsonsetassignee: mark.dickinson
messages: + msg273861
versions: + Python 3.5, Python 3.6
2016-08-27 00:49:46rhettingersetnosy: + skrah
2016-08-26 22:07:57r.david.murraysetnosy: + mark.dickinson
messages: + msg273740
2016-08-26 21:54:46Alex Grocesetmessages: + msg273739
2016-08-26 21:41:47r.david.murraysetmessages: + msg273731
2016-08-26 21:38:51r.david.murraysetmessages: + msg273730
2016-08-26 21:36:29Alex Grocesetmessages: + msg273729
2016-08-26 21:34:29r.david.murraysetnosy: + r.david.murray
messages: + msg273727
2016-08-26 20:40:21Alex Grocesetmessages: + msg273726
2016-08-26 20:37:28Alex Grocesetmessages: + msg273725
2016-08-26 19:12:23Alex Grocecreate