a potential future bug and an optimization that mostly undermines performance in long_invert

[orenmn]

BPO	27214
Nosy	@mdickinson, @serhiy-storchaka, @orenmn
Files	proposedPatches.diff: proposed patches diff file CPythonTestOutput.txt: test output of CPython without my patches (tested on my PC) patchedCPythonTestOutput.txt: test output of CPython with my patches (tested on my PC)

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = <Date 2016-08-29.15:41:22.866>
created_at = <Date 2016-06-04.08:05:36.818>
labels = ['interpreter-core', 'performance']
title = 'a potential future bug and an optimization that mostly undermines performance in long_invert'
updated_at = <Date 2016-08-29.15:50:03.022>
user = 'https://github.com/orenmn'

bugs.python.org fields:

activity = <Date 2016-08-29.15:50:03.022>
actor = 'Oren Milman'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2016-08-29.15:41:22.866>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2016-06-04.08:05:36.818>
creator = 'Oren Milman'
dependencies = []
files = ['43186', '43187', '43188']
hgrepos = []
issue_num = 27214
keywords = ['patch']
message_count = 4.0
messages = ['267244', '273865', '273866', '273867']
nosy_count = 4.0
nosy_names = ['mark.dickinson', 'python-dev', 'serhiy.storchaka', 'Oren Milman']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue27214'
versions = ['Python 3.6']

[orenmn]

------------ 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.

[python-dev]

New changeset 6e1d38674b17 by Mark Dickinson in branch 'default':
Issue bpo-27214: Fix potential bug and remove useless optimization in long_invert. Thanks Oren Milman.
https://hg.python.org/cpython/rev/6e1d38674b17

[mdickinson]

Agreed with the analysis and proposed solution. Thanks!

[orenmn]

Thanks for the review, Mark :)