Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork32.1k
bpo-44946: Streamline operators and creation of ints for common case of single 'digit'.#27832
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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
…case of single 'digit'.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
@markshannon Sorry, I started reviewing while you were still committing; please could you ping me when the PR is stable and ready for review? |
markshannon commentedAug 20, 2021 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
@mdickinson All done and ready for review. |
@mdickinson All done and ready for review (for real this time). There were three things that conspired to make this rather more work than I had anticipated.
The end result was an infuriating amount of debugging via CI. |
Yes, we really shouldn't: everything that's working exclusively with PyLong digits should be using one of the dedicated types |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
A few comments. The main one: please can we restore the old version ofPyLong_FromLong
? As much as possible, I'd like to keep the digit-based logic (which should be using nothing other thandigit
,sdigit
,twodigit
andstwodigits
to represent values) separate from the logic that has to deal with arbitrary C types; tangling them up would make it harder to change the representation later. (E.g., if 128-bit integers become widely supported, it may still make sense to look into 60-bit digits at some point.)
Objects/longobject.c Outdated
#define IS_SMALL_INT(ival) (-NSMALLNEGINTS <= (ival) && (ival) < NSMALLPOSINTS) | ||
#define IS_SMALL_UINT(ival) ((ival) < NSMALLPOSINTS) | ||
#define IS_MEDIUM_INT(x) (((twodigits)x)+PyLong_MASK <= 2*PyLong_MASK) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
It would be useful to have a comment clarifying what range of values this macro can safely be used for. I'm assuming it should be enough that it's valid for values in the range(-PyLong_BASE**2, PyLong_BASE**2)
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Sorry, I think I was unclear. The(twodigits)x
cast potentially loses information ifx
is large enough, leading to the possibility of false positives forIS_MEDIUM_INT
. For example, that will happen on Windows with a largePy_ssize_t
value and 15-bit digits - in that case,Py_ssize_t
is much larger thanunsigned long
.
So there's some restriction on the value ofx
for which this test is valid. "Fits instwodigits
" would probably be enough, but I don't think we use this macro for values outside the range(-PyLong_BASE**2, PyLong_BASE**2)
.
mdickinsonAug 25, 2021 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
More generally, C's integer-handling rules make this sort of thing horribly messy to reason about: for example in the 15-bit digit case the addition is an addition of anunsigned long
to a (signed!)int
, since the integer promotions will promote theunsigned short
PyLong_MASK
to anint
(though even that part is not guaranteed by the standard - there's nothing preventingshort
andint
having the same precision, in which casePyLong_MASK
will be promoted tounsigned int
instead ofint
). So now we have to consult the rules for unsigned + signed addition in the "usual arithmetic conversions", which eventually say that becauselong
has greater rank thanint
(even if it has the same precision), both operands will be treated asunsigned long
for the addition.
The2 * PyLong_MASK
is another case that could end up being either signed or unsigned depending on ranks, types, etc; it's probably better spelled as2U * PyLong_MASK
; that way we can at least be sure that it's performed as an unsigned multiplication and that the final comparison is unsigned-to-unsigned.
I'd suggest the addition of an extra cast around the result of the addition, just to reduce the number of mental hoops one has to jump through to establish that this really does give the right result: that is,
((twodigits)((twodigits)(x)+PyLong_MASK) <= 2U*PyLong_MASK)
We should also add extra parentheses around thex
, in case someone tries to useIS_MEDIUM_INT
on an expression more complicated than a single name.
markshannonAug 25, 2021 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I wholeheartedly agree that C's integer handling is a pain to think about 😞
For clarity I think this is best to use an inline function that makes all casts super explicit.
That way that it makes the cast explicit (if called with something other thanstwodigits
orsdigits
, the caller is responsible.
staticinlineintis_medium_int(stwodigitsx){/* We have to take care here to make sure that we are * comparing unsigned values. */twodigitsx_plus_mask= ((twodigits)x)+PyLong_MASK;returnx_plus_mask< ((twodigits)PyLong_MASK)+PyLong_BASE;}
Does that seem sensible?
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
mdickinson commentedAug 21, 2021 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
One other thing: please could you post your benchmark methodology and results, either here or on the issue? (Probably more appropriate to post on the issue.) I'd like to see if I can reproduce the speedup you're reporting. |
…llow for 15 bit digits on 64 bit machines.
markshannon commentedAug 23, 2021 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Latest benchmarks |
Thanks for all the updates! I'll make another (final, I hope) review pass shortly. |
bedevere-bot commentedAug 23, 2021
🤖 New build scheduled with the buildbot fleet by@mdickinson for commit1f2d47c 🤖 If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again. |
bedevere-bot commentedAug 23, 2021
🤖 New build scheduled with the buildbot fleet by@markshannon for commit649c311 🤖 If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again. |
The failure on buildbot/AMD64 Arch Linux Asan Debug PR is unrelated. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
LGTM modulo theIS_MEDIUM_INT
definition changes (parentheses around thex
,2U
in place of2
).
Uh oh!
There was an error while loading.Please reload this page.
if (ival < 0) { | ||
/* negate: can't write this as abs_ival = -ival since that | ||
invokes undefined behaviour when ival is LONG_MIN */ | ||
abs_ival = 0U-(unsigned long)ival; | ||
abs_ival = 0U-(twodigits)ival; |
mdickinsonJan 7, 2022 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This should not have been changed. There's no guarantee that anunsigned long
fits in something of typetwodigits
. I'll open a bug report and make a PR when I get the chance.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Opened#30496. We seem to be okay on current platforms because fromlongintrepr.h
,twodigits
has type eitherunsigned long
oruint64_t
(depending onPYLONG_BITS_IN_DIGIT
), and no platform we currently care about has along
larger thanuint64_t
.
Uh oh!
There was an error while loading.Please reload this page.
Modest speedup of1%
The speedup is unexciting, although every little helps.
However, this will help with specialization of integer operations, as that will remove additional overhead.
The obvious other speedup of using a freelist is left for another PR, as we need to rationalize our use of freelists before adding more.
Skipping NEWS as there is no change to any APIs and the performance increase is marginal.
https://bugs.python.org/issue44946