-
-
Notifications
You must be signed in to change notification settings - Fork 29.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
long_add and long_sub might return a new int where &small_ints[x] could be returned #71332
Comments
------------ 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
1
>>> a - b is 1
True
>>> a + (-b) is 1
True
>>>
>>> ##### case B #####
>>> a = 2 ** PyLong_SHIFT
>>> b = 2 ** PyLong_SHIFT - 1
>>> a - b
1
>>> a - b is 1
False
>>> a + (-b) is 1
False
>>>
>>> ##### case C #####
>>> a = 2 ** PyLong_SHIFT + 1
>>> b = 2 ** PyLong_SHIFT
>>> a - b
1
>>> a - b is 1
False
>>> a + (-b) is 1
False
>>> This behavior is caused by the implementation of long_add and long_sub: 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. 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. ------------ Note ------------ Anyway, I guess documenting the issue here, along with a proposal for a fix, is better than nothing. ------------ the proposed changes ------------
------------ alternative changes ------------ 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. 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 ------------ ------------ diff ------------ ------------ tests ------------ 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. |
I just realized I had forgotten to check for a failure after using _PyLong_Negate. The updated diff file is attached. |
After giving it some more thought, I feel somewhat uncertain about that check for a failure after using _PyLong_Negate. At first I noticed that after every call to _PyLong_Negate there is such a check. But then I realized that in my patch, and also in long_mul (in the default branch of CPython), the check is unnecessary, as z is just returned after the call to _PyLong_Negate. Is adding such a check anyway (e.g. in long_mul) a convention? Or should such checks be removed? |
It seems like there are a few corner cases where long integers are not normalized: But the initial issue described here has been fixed, so it's better to keep this issue closed. If someone wants to cover more cases (to normalize), please open a separated issue. Thanks HongWeipeng for the fix and Oren Milman for the original bug report and original patches! |
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:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: