[New-bugs-announce] [issue27298] redundant iteration over digits in _PyLong_AsUnsignedLongMask

[Oren Milman]

New submission from Oren Milman:

------------ current state ------------
1. In Objects/longobject.c in _PyLong_AsUnsignedLongMask, in case v is a multiple-digit int, _PyLong_AsUnsignedLongMask iterates over all of its digits (going from the most to the least significant digit) and does (for each digit) 'x = (x << PyLong_SHIFT) | v->ob_digit[i];'.
However, iterating over digits other than the 'ceil(sizeof(x) * 8.0 / PyLong_SHIFT)' least significant digits is redundant, because their bits would be shifted out of x anyway.

With regard to relevant changes made in the past, the iteration over all of the digits of a multiple-digit v remained quite the same since _PyLong_AsUnsignedLongMask was added, in revision 28652.

2. In Modules/_testcapimodule.c, the function comment of test_k_code, and an error string inside that function, contain mistakes.

With regard to relevant changes made in the past, these mistakes were there since test_k_code was added, in revision 28652.


------------ proposed changes ------------
1. In _PyLong_AsUnsignedLongMask, in case v is a multiple-digit int, iterate only over the 'Py_MIN(i, sizeof(x) * 8 / PyLong_SHIFT + 1)' least significant digits.

Obviously, 'sizeof(x) * 8 / PyLong_SHIFT + 1' might be off by one in case CPython is compiled with a PyLong_SHIFT other than 15 or 30. I suspect it's an overkill, but I added an assert, just in case.

2. Fix the function comment of test_k_code, and an error string inside that function.


------------ alternative changes ------------
1. I have also considered iterating only over the 'Py_MIN(i, (Py_ssize_t)ceil(sizeof(x) * 8.0 / PyLong_SHIFT))' least significant digits. 
Even though this number of digits is guaranteed to be accurate, it cannot be calculated at compile time, so it would probably cause the optimization to overall introduce a performance penalty.


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

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.

----------
components: Interpreter Core
files: proposedPatches.diff
keywords: patch
messages: 268274
nosy: Oren Milman
priority: normal
severity: normal
status: open
title: redundant iteration over digits in _PyLong_AsUnsignedLongMask
type: performance
Added file: http://bugs.python.org/file43346/proposedPatches.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue27298>
_______________________________________