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.

Author Oren Milman
Recipients Oren Milman
Date 2016-05-28.15:58:35
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
------------ the current state ------------
>>> if is32BitCPython:
...   PyLong_SHIFT = 15
... elif is64BitCPython:
...   PyLong_SHIFT = 30
>>> ##### case A #####
>>> a = 2 ** PyLong_SHIFT - 1
>>> b = 2 ** PyLong_SHIFT - 2
>>> a - b
>>> a - b is 1
>>> a + (-b) is 1
>>> ##### case B #####
>>> a = 2 ** PyLong_SHIFT
>>> b = 2 ** PyLong_SHIFT - 1
>>> a - b
>>> a - b is 1
>>> a + (-b) is 1
>>> ##### case C #####
>>> a = 2 ** PyLong_SHIFT + 1
>>> b = 2 ** PyLong_SHIFT
>>> a - b
>>> a - b is 1
>>> a + (-b) is 1

This behavior is caused by the implementation of long_add and long_sub:
    Both long_add and long_sub check whether both a and b are single-digit ints, and then do (respectively):
        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
        return PyLong_FromLong(MEDIUM_VALUE(a) - MEDIUM_VALUE(b));
    Otherwise, long_add and long_sub call x_add or x_sub to do a calculation on the absolute values of a and b.
    At last, long_add and long_sub negate the result of the calculation, if needed, and return the final result. 

Where both a and b are single-digit ints (e.g. case A), the result of the calculation is passed to PyLong_FromLong, which uses CHECK_SMALL_INT, and so a reference to an element of small_ints is returned where appropriate.
Where a and/or b are not single-digit ints (e.g. cases B and C), x_add or x_sub is called. Both x_add and x_sub don't check whether the result is a small int (except for a case in x_sub where the result is zero), and so long_add and long_sub might return a new int, even where an element of small_ints could be reused.

Due to the way CPython uses them, the issue is relevant to x_sub and not to x_add, as the calculation the former performs might result in a small int, while that of the latter would always result in a multiple-digit int.
(Except for being called by long_add and long_sub, x_add might be called by k_mul, but in that case also the calculation would certainly result in a multiple-digit int.)

------------ Note ------------
I am not sure whether this is actually an issue that we want to fix.
It seems to me that my proposed changes introduce a slight performance gain (in terms of memory, and probably also speed), and a more consistent behavior of CPython.
The performance gain would probably be much more relevant if and when greater default values are chosen for NSMALLNEGINTS and NSMALLPOSINTS.

Anyway, I guess documenting the issue here, along with a proposal for a fix, is better than nothing.
(As far as I know, since the unification of int and long in revision 40626, this issue never came up.)

------------ the proposed changes ------------
All of the proposed changes are in Objects/longobject.c:
1. in x_sub:
    To make sure x_sub returns a small int where appropriate, I simply wrapped the return value of x_sub with the function maybe_small_long.

2. in long_sub:
    The previous patch alone would create a nasty bug.
    In case both a and b are negative, long_sub calls x_sub, and then negates the result in-place by doing 'Py_SIZE(z) = -(Py_SIZE(z));'.
    If x_sub returned a reference to a statically allocated small int (which is not zero), long_sub would actually change that statically allocated small int.

    To prevent that, I replaced that in-place negating with a call to _PyLong_Negate.

3. in _PyLong_Negate:
    The previous patches, along with (another issue I have opened recently), would cause long_sub to call _PyLong_Negate for a zero int, in case a and b are the same multiple-digit negative int. 
    Moreover, in the default CPython branch, in case long_mul receives a multiple-digit negative int and zero, long_mul would call _PyLong_Negate for a zero int.

    To prevent doing 'PyLong_FromLong(-MEDIUM_VALUE(x))' where x is a zero int, I have added a check before that (along with a little addition to the function comment), so that _PyLong_Negate would do nothing if x is a zero int. 
    It should be noted that MEDIUM_VALUE also checks whether x is a zero int (for its own reasons), so thanks to the wisdom of nowadays compilers, the check I propose to add shouldn't introduce a performance penalty.
    (Actually, when comparing the assembly of _PyLong_Negate (for win32) of the default CPython branch and the patched one, the latter looks simpler.)

    With regard to similar changes made in the past, _PyLong_Negate wasn't changed since it replaced the macro NEGATE in revision 84698.

4. in x_sub:
    The previous patches made it safe for x_sub to return a reference to a statically allocated small int, and thus made it possible to implement the following optimization.
    In case a and b have the same number of digits, x_sub finds the most significant digit where a and b differ. Then, if there is no such digit, it means a and b are equal, and so x_sub does 'return (PyLongObject *)PyLong_FromLong(0);'.
    I propose to add another check after that, to determine whether the least significant digit is the only digit where a and b differ. In that case, we can do something very similar to what long_add and long_sub do when they realize they are dealing with single-digit ints (as mentioned in 'the current state' section): 
        return (PyLongObject *)PyLong_FromLong((sdigit)a->ob_digit[0] - 

------------ alternative changes ------------
As an alternative to these 4 changes, I also thought of simply wrapping the return value of long_add and long_sub with the function maybe_small_long (i.e. change the last line of each of them to 'return (PyObject *)maybe_small_long(z);').

This change might be more simple, but I believe it would introduce a performance penalty, as it adds checks also to flows of long_add and long_sub that would never result in a small int.
Furthermore, this change won't save any allocations of small ints. For example, in case C (that was mentioned in 'the current state' section), both in (a - b) and in (a + (-b)):
    1. A new int of value 1 would be allocated by x_sub.
    2. In the end of long_add or long_sub, maybe_small_long would realize an element of small_ints could be used.
    3. maybe_small_long would use Py_DECREF on the new int of value 1, which would cause the deallocation of it.

In contrast, in case C, the 4th change (in the proposed changes section) would cause x_sub to realize in advance that the result is going to be a single-digit. Consequently, no new int would be futilely allocated in the process.

However, in case B (that was mentioned in 'the current state' section), both the alternative changes and the proposed changes (and also the default CPython branch), won't prevent x_sub from allocating a new int.

------------ micro-benchmarking ------------
    I did some micro-benchmarking:
    - subtraction of multiple-digit ints with the same number of digits, while the result fits in the small_ints array:
        python -m timeit "[i - (i + 1) for i in range(2 ** 67, 2 ** 67 + 1000)]" -> The patched CPython is approximately 8% faster.
    - subtraction of multiple-digit ints with the same number of digits, which differ only in the least significant digit (while the result doesn't fit in the small_ints array):
        python -m timeit "[i - (i + 6) for i in range(2 ** 67, 2 ** 67 + 1000)]" -> The patched CPython is approximately 3% faster.
    - subtraction of multiple-digit ints with the same number of digits, which differ (among others) in the most significant digit:
        python -m timeit "[i * 2 - i for i in range(2 ** 67, 2 ** 67 + 1000)]" -> The patched CPython is approximately 1% slower.
    - subtraction of multiple-digit ints with different number of digits:
        python -m timeit "[i ** 2 - i * 3 for i in range(2 ** 67, 2 ** 67 + 500)]" -> The patched CPython is approximately 2% faster. 
        I expected the patched CPython to be somewhat slower here. Either I have missed something, or some compiler optimization magic was used here.

------------ 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. 
Also, where cases B and C (that were mentioned in 'the current state' section) returned 'False', the patched CPython returned 'True', as expected.

In addition, I ran 'python_d.exe -m test' (on my 64-bit Windows 10) with and without the patches, and got quite the same output.
the outputs of both runs are attached.
Date User Action Args
2016-05-28 15:58:41Oren Milmansetrecipients: + Oren Milman
2016-05-28 15:58:37Oren Milmansetmessageid: <>
2016-05-28 15:58:37Oren Milmanlinkissue27145 messages
2016-05-28 15:58:36Oren Milmancreate