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 2016-06-03 21:11 by python-dev. 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
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