homepage

This issue tracker has been migrated to GitHub , and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: redundant checks in long_add and long_sub
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Oren Milman, mark.dickinson, python-dev, serhiy.storchaka, vstinner, yselivanov
Priority: normal Keywords: patch

Created on 2016年05月21日 07:41 by Oren Milman, last changed 2022年04月11日 14:58 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
issue.diff Oren Milman, 2016年05月21日 07:41 proposed patches diff file review
CPythonTestOutput.txt Oren Milman, 2016年05月21日 07:42 test output of CPython without my patches (tested on my PC)
patchedCPythonTestOutput.txt Oren Milman, 2016年05月21日 07:42 test output of CPython with my patches (tested on my PC)
issue27073.diff Oren Milman, 2016年05月21日 15:07 proporsed patches diff file update1 review
issue27073.diff Oren Milman, 2016年05月28日 16:50 proporsed patches diff file update2 review
issue27073.diff Oren Milman, 2016年05月28日 17:09 proporsed patches diff file update3 review
issue27073.diff Oren Milman, 2016年06月03日 13:44 proporsed patches diff file update4 review
patchedCPythonTestOutput2.txt Oren Milman, 2016年06月03日 13:45 test output of CPython with the updated patches (tested on my PC)
issue27073.diff Oren Milman, 2016年06月03日 19:54 proposed patches diff file update5 review
patchedCPythonTestOutput.txt Oren Milman, 2016年06月03日 19:54 test output of CPython with the updated patches (tested on my PC) 2
Messages (14)
msg265989 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年05月21日 07:41
------------ the proposed changes ------------
I believe the following checks are redundant:
 1. in Objects/longobject.c in long_add:
 In case both a and b are negative, their absolute values are added using x_add, with the result stored in z.
 If (z != NULL), it must be that x_add succeeded, and also it must be that (Py_SIZE(z) > 0), as it is guaranteed that the absolute values of a and b are both bigger than zero.
 Thus, the check (Py_SIZE(z) != 0) here is redundant.
 2. in Objects/longobject.c in long_sub:
 In case a is negative, the absolute values of a and b are subtracted or added using x_sub or x_add, with the result stored in z.
 Later on, if (z != NULL && Py_SIZE(z) != 0), then Py_SIZE(z) is negated. However, even though it might be that Py_SIZE(z) == 0, it doesn't really matter.
 doing 'Py_SIZE(z) = -(Py_SIZE(z));' in that case would do nothing.
 Thus, the check (Py_SIZE(z) != 0) here is redundant.
 The original versions of both of these checks were added in revision 443 (November 1991!). Back then, ob_size's was implemented using one's complement, and negating it was actually doing 'z->ob_size = ~z->ob_size;'. 
 Of course, in that case the check (z->ob_size != 0) was necessary, but then, in revision 590, ob_size was changed to use two's complement, and the check (z->ob_size != 0) was left untouched, and remained there to this day.
------------ diff ------------
The patches diff is attached.
------------ tests ------------
I built the patched CPython for x86, and played with it a little. Everything seemed to work as usual.
In addition, I ran 'python -m test' (on my 64-bit Windows 10) before and after applying the patch, and got quite the same output.
the outputs of both runs are attached.
msg266001 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016年05月21日 14:01
Your analysis and patch look good to me.
msg266002 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016年05月21日 14:48
Sorry, I didn't check if the change is valid or not, but:
> issue.diff 
Please keep the check but as an assertion (Put it in the if block).
msg266004 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年05月21日 15:07
Thanks for the reviews!
I added an assert in long_add (in long_sub it might be that the result is 0).
The updated diff file is attached.
msg266560 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年05月28日 16:50
After giving it some more thought (while working on another, somewhat related issue - http://bugs.python.org/issue27145), I realized that that assert in long_add could further verify that the int x_add returned is a multiple-digit int (as x_add had received two multiple-digit ints to begin with).
The important thing about this updated assert is that it verifies that x_add didn't return a reference to an element in small_ints (as small ints must be single-digit ints), so negating it in-place is safe.
I have updated the assert and added an appropriate comment. The updated diff file is attached.
msg266562 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年05月28日 17:09
And after quadruple checking myself, I found a foolish mistake - in that flow, x_add received at least one multiple-digit int (not necessarily two :().
I fixed that mistake in the comment. The updated diff file is attached.
msg266563 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016年05月28日 17:14
I don't think this assert is needed. Nothing bad happens if the asserted condition is false. On other side, additional assert can slow down debug build (that is already slower than release build).
msg266612 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年05月29日 18:48
I agree. This assert only indirectly verifies that something bad doesn't happen. 
The bad thing that might happen is an in-place negating of an element of small_ints, so the most direct assert should be 'assert(Py_REFCNT(z) == 1);'.
This is exactly what Victor did in long_lshift back in revision 84698...
What do you think?
msg267093 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016年06月03日 12:06
It would be nice.
msg267098 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年06月03日 13:44
All right. The updated diff file is attached.
I compiled and ran the tests again. They are quite the same. The test output is attached.
msg267125 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016年06月03日 18:12
Maybe add an assert for the second size negation?
msg267152 - (view) Author: Oren Milman (Oren Milman) * Date: 2016年06月03日 19:54
I considered doing that, but I had already opened another issue (http://bugs.python.org/issue27145) in which I had proposed to replace that in-place negate in long_sub with a call to _PyLong_Negate.
But I guess I shouldn't worry about my patches colliding.
Anyway, the second assert would be 'assert(Py_SIZE(z) == 0 || Py_REFCNT(z) == 1);', because if someone does (in Python) 'x = (-2 ** PyLong_SHIFT) - (-2 ** PyLong_SHIFT)', x_sub would do 'return (PyLongObject *)PyLong_FromLong(0);'.
The updated diff file and the new test output are attached.
(No idea why test_netrc failed there. I ran it specifically five times right after that, and it passed all of them. Maybe some race condition? (To run the tests, I do 'python_d.exe -m test -j3'.)
Anyway, here is the relevant output (I am not sure the last line is relevant):
Warning -- files was modified by test_netrc
test test_netrc failed -- Traceback (most recent call last):
 File "C:\Users\orenmn\cpython\lib\test\test_netrc.py", line 52, in test_password_with_trailing_hash
 """, 'pass#')
 File "C:\Users\orenmn\cpython\lib\test\test_netrc.py", line 41, in _test_passwords
 nrc = self.make_nrc(nrc)
 File "C:\Users\orenmn\cpython\lib\test\test_netrc.py", line 13, in make_nrc
 with open(temp_filename, mode) as fp:
PermissionError: [Errno 13] Permission denied: '@test_3652_tmp'
minkernel\crts\ucrt\src\appcrt\lowio\write.cpp(49) : Assertion failed: (_osfile(fh) & FOPEN)
)
msg267164 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016年06月03日 21:08
LGTM (except a trailing space in a comment). Thank you for your contribution Oren.
msg267165 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016年06月03日 21:11
New changeset c21bf38a9d07 by Serhiy Storchaka in branch 'default':
Issue #27073: Removed redundant checks in long_add and long_sub.
https://hg.python.org/cpython/rev/c21bf38a9d07 
History
Date User Action Args
2022年04月11日 14:58:31adminsetgithub: 71260
2016年06月03日 21:11:56python-devsetnosy: + python-dev
messages: + msg267165
2016年06月03日 21:08:57serhiy.storchakasettype: behavior -> performance
2016年06月03日 21:08:30serhiy.storchakasetstatus: open -> closed
resolution: fixed
messages: + msg267164

stage: patch review -> resolved
2016年06月03日 19:54:57Oren Milmansetfiles: + patchedCPythonTestOutput.txt
2016年06月03日 19:54:25Oren Milmansetfiles: + issue27073.diff

messages: + msg267152
2016年06月03日 18:12:58serhiy.storchakasetmessages: + msg267125
2016年06月03日 13:45:13Oren Milmansetfiles: + patchedCPythonTestOutput2.txt
2016年06月03日 13:44:30Oren Milmansetfiles: + issue27073.diff

messages: + msg267098
2016年06月03日 12:06:15serhiy.storchakasetmessages: + msg267093
2016年05月29日 18:48:29Oren Milmansetmessages: + msg266612
2016年05月28日 17:14:15serhiy.storchakasetmessages: + msg266563
2016年05月28日 17:09:12Oren Milmansetfiles: + issue27073.diff

messages: + msg266562
2016年05月28日 16:50:21Oren Milmansetfiles: + issue27073.diff

messages: + msg266560
2016年05月21日 15:07:58Oren Milmansetfiles: + issue27073.diff

messages: + msg266004
2016年05月21日 14:48:25vstinnersetmessages: + msg266002
2016年05月21日 14:01:52mark.dickinsonsetnosy: + mark.dickinson
messages: + msg266001
2016年05月21日 08:08:08SilentGhostsetnosy: + vstinner, serhiy.storchaka, yselivanov
stage: patch review
type: behavior

versions: + Python 3.6
2016年05月21日 07:43:00Oren Milmansetfiles: + patchedCPythonTestOutput.txt
2016年05月21日 07:42:24Oren Milmansetfiles: + CPythonTestOutput.txt
2016年05月21日 07:41:40Oren Milmancreate

AltStyle によって変換されたページ (->オリジナル) /