classification
Title: a potential future bug and an optimization that mostly undermines performance in long_invert
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.6
process
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 08:05 by Oren Milman, last changed 2016-08-29 15:50 by Oren Milman. This issue is now closed.

Files
File name Uploaded Description Edit
proposedPatches.diff Oren Milman, 2016-06-04 08:05 proposed patches diff file review
CPythonTestOutput.txt Oren Milman, 2016-06-04 08:05 test output of CPython without my patches (tested on my PC)
patchedCPythonTestOutput.txt Oren Milman, 2016-06-04 08:06 test output of CPython with my patches (tested on my PC)
Messages (4)
msg267244 - (view) Author: Oren Milman (Oren Milman) * Date: 2016-06-04 08:05
------------ the current state ------------
long_invert first checks whether v is a single-digit int. If it is, it simply does 'return PyLong_FromLong(-(MEDIUM_VALUE(v) + 1));'.
Otherwise, long_invert does (edited for brevity) 'x = long_add(v, PyLong_FromLong(1));', and then negates x in-place.

In other words, long_invert assumes long_add hasn't returned a reference to an element of small_ints.
However, if all of the following conditions are true:
    * NSMALLNEGINTS is maximized (i.e. NSMALLNEGINTS == 2 ** PyLong_SHIFT - 1).
    * long_add is changed in such a way that if someone does (in Python) '-2 ** PyLong_SHIFT + 1' while NSMALLNEGINTS is maximized, long_add would return a reference to an element of small_ints. (Actually, I have recently opened an issue that proposes such a change - http://bugs.python.org/issue27145.)
    * long_invert is called for (-2 ** PyLong_SHIFT).
Then long_invert would negate in-place an element of small_ints.

In addition, because long_invert first checks whether v is a single-digit int, calling maybe_small_long before returning would save up memory only in case both of the following conditions are true:
    * NSMALLPOSINTS is maximized (i.e. NSMALLPOSINTS == 2 ** PyLong_SHIFT).
    * long_invert is called for (-2 ** PyLong_SHIFT).
So the call to maybe_small_long introduces a performance penalty for every case where v is a multiple-digit int (and long_invert doesn't fail), while the only case where it actually saves up memory is the aforementioned corner case.


------------ the proposed changes ------------
Both of the proposed changes are in Objects/longobject.c in long_invert:
    1. Replace the in-place negation with a call to _PyLong_Negate, which safely negates an int. 
    
    2. Remove the call to maybe_small_long.

    maybe_small_long was added to long_invert in revision 48567, as part of an effort to wipe out different places in the code where small_ints could be used (and saved up memory), but was not. I am not sure why maybe_small_long was also added to long_invert back then, even though it mostly undermines performance.


------------ 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_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.
msg273865 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-08-29 15:40
New changeset 6e1d38674b17 by Mark Dickinson in branch 'default':
Issue #27214: Fix potential bug and remove useless optimization in long_invert. Thanks Oren Milman.
https://hg.python.org/cpython/rev/6e1d38674b17
msg273866 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-29 15:41
Agreed with the analysis and proposed solution. Thanks!
msg273867 - (view) Author: Oren Milman (Oren Milman) * Date: 2016-08-29 15:50
Thanks for the review, Mark :)
History
Date User Action Args
2016-08-29 15:50:03Oren Milmansetmessages: + msg273867
2016-08-29 15:41:22mark.dickinsonsetstatus: open -> closed
messages: + msg273866

assignee: mark.dickinson
resolution: fixed
stage: patch review -> resolved
2016-08-29 15:40:45python-devsetnosy: + python-dev
messages: + msg273865
2016-06-04 08:11:37serhiy.storchakasetnosy: + mark.dickinson, serhiy.storchaka
stage: patch review

versions: + Python 3.6
2016-06-04 08:06:49Oren Milmansetfiles: + patchedCPythonTestOutput.txt
2016-06-04 08:06:01Oren Milmansetfiles: + CPythonTestOutput.txt
2016-06-04 08:05:36Oren Milmancreate