Title: redundant checks and a weird use of goto statements in long_rshift
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.7
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: Oren Milman, mark.dickinson, python-dev, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2016-06-04 19:54 by Oren Milman, last changed 2017-03-31 16:36 by dstufft. This issue is now closed.

File name Uploaded Description Edit
proposedPatches.diff Oren Milman, 2016-06-04 19:54 proposed patches diff file review
CPythonTestOutput.txt Oren Milman, 2016-06-04 19:54 test output of CPython without my patches (tested on my PC)
patchedCPythonTestOutput.txt Oren Milman, 2016-06-04 19:55 test output of CPython with my patches (tested on my PC)
Pull Requests
URL Status Linked Edit
PR 552 closed dstufft, 2017-03-31 16:36
Messages (4)
msg267308 - (view) Author: Oren Milman (Oren Milman) * Date: 2016-06-04 19:54
------------ current state ------------
1. long_rshift first checks whether a is a negative int. If it is, it does (edited for brevity) 'z = long_invert(long_rshift(long_invert(a), b));'.
Otherwise, it calculates the result of the shift and stores it in z. In this block, there is a check whether a is a negative int.

The second check was always there - since revision 443, in which long_rshift was first added. However, in revision 590, the first aforementioned check (whether a is a negative int), along with a (edited for brevity) 'return long_invert(long_rshift(long_invert(a), b));' were added, but the second check whether a is a negative int wasn't removed, and remained there to this day.

2. Ultimately, long_rshift does 'return (PyObject *) maybe_small_long(z);' for both cases (whether a is a negative int or not). 
Calling maybe_small_long in case a is a negative int is redundant, as long_invert returns (in case it doesn't fail) by either doing 'return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));' or 'return (PyObject *)maybe_small_long(x);'. In both cases, long_invert would return a reference to an element of small_ints if it should.

Calls to maybe_small_long were added both to long_rshift and long_invert in revision 48567, as part of an effort to wipe out different places in the code where small_ints could be used (to save up memory), but was not. I am not sure why maybe_small_long was added to long_rshift where it would be redundant in case a is a negative int.

3. In different cases of failure, long_rshift does 'goto rshift_error;'. 
The destination of these goto statements is actually a return statement that would also be reached in almost any case of success (except for a certain case in which the result of the shift is obviously zero).

That goto was added in revision 15725. Back then, CONVERT_BINOP was added, and calling it in long_rshift required calling Py_DECREF for a and b before returning.
Later on, in revision 43313, CONVERT_BINOP was removed, along with the calls to Py_DECREF it required, but the goto was left untouched, and remained there to this day.

------------ proposed changes ------------
All of the proposed changes are in Objects/longobject.c in long_rshift:
    1. Remove the check whether a is a negative int in the block that gets executed in case a is not a negative int.
    2. Move the call to maybe_small_long inside the block that runs in case a is not a negative int.

    3. Replace every 'goto rshift_error;' with a 'return NULL;', and remove the rshift_error label. 

    I could have kept the goto statements, with 'return (PyObject *)z;' as their destination, but I believe it would have been less clear. Also, there are many similar places in longobject.c where 'return NULL;' is done on failure.

------------ diff ------------
The proposed patches diff file is attached.

------------ tests ------------
I built the patched CPython for x86, and played with it a little. Everything seemed to work as usual. 
Specifically, I did:
    for i in range(10000):
        if not all(smallInt is ((smallInt << i) >> i) for (
                smallInt) in range(-5, 257)):
And indeed 9999 was printed.

In addition, I ran 'python_d.exe -m test -j3' (on my 64-bit Windows 10) with and without the patches, and got quite the same output.
the outputs of both runs are attached.
msg276290 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-09-13 15:21
Sorry, this fell off my list of things to look at.
msg276803 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-09-17 16:51
New changeset 21b70c835b5b by Mark Dickinson in branch 'default':
Issue #27222: various cleanups in long_rshift. Thanks Oren Milman.
msg276804 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-09-17 16:52
Thanks for the patch and the thorough analysis!
Date User Action Args
2017-03-31 16:36:33dstufftsetpull_requests: + pull_request1066
2016-09-17 16:52:03mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg276804

stage: patch review -> resolved
2016-09-17 16:51:10python-devsetnosy: + python-dev
messages: + msg276803
2016-09-13 15:21:49mark.dickinsonsetassignee: mark.dickinson
messages: + msg276290
2016-09-13 14:05:54Oren Milmansetversions: + Python 3.7, - Python 3.6
2016-06-04 20:35:46serhiy.storchakasetnosy: + mark.dickinson, serhiy.storchaka
stage: patch review

versions: + Python 3.6
2016-06-04 19:55:23Oren Milmansetfiles: + patchedCPythonTestOutput.txt
2016-06-04 19:55:00Oren Milmansetfiles: + CPythonTestOutput.txt
2016-06-04 19:54:27Oren Milmancreate