Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

Merged

Conversation

markshannon
Copy link
Member

@markshannonmarkshannon commentedAug 19, 2021
edited by bedevere-bot
Loading

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

@mdickinsonmdickinson self-assigned thisAug 19, 2021
@mdickinsonmdickinson removed their assignmentAug 19, 2021
@mdickinsonmdickinson self-requested a reviewAugust 19, 2021 14:33
@mdickinson
Copy link
Member

@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
Copy link
MemberAuthor

markshannon commentedAug 20, 2021
edited
Loading

@mdickinson All done and ready for review.
(Not quite, still need to fix some complaints from the MSVC compiler)

@markshannon
Copy link
MemberAuthor

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

  • We uselong everywhere, even though it differs in size between Windows and other 64 bit platforms.
  • That thesdigit type has two spare bits on 64 bit machines (32 to 30) but only one on 32 bit platforms meaning thatdigit op digit needs more thansdigit space on 32 bit machines, even though it is fine on 64 bit machines.
  • GCC does not give warnings for dubious implicit casts. Fortunately MSVC does.

The end result was an infuriating amount of debugging via CI.

@mdickinson
Copy link
Member

  • We uselong everywhere, even though it differs in size between Windows and other 64 bit platforms.

Yes, we really shouldn't: everything that's working exclusively with PyLong digits should be using one of the dedicated typesdigit,sdigit,twodigits orstwodigits.

@mdickinsonmdickinson self-requested a reviewAugust 21, 2021 10:54
Copy link
Member

@mdickinsonmdickinson left a 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.)


#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)
Copy link
Member

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

Copy link
Member

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

Copy link
Member

@mdickinsonmdickinsonAug 25, 2021
edited
Loading

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

Copy link
MemberAuthor

@markshannonmarkshannonAug 25, 2021
edited
Loading

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?

@mdickinson
Copy link
Member

mdickinson commentedAug 21, 2021
edited
Loading

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.

@markshannon
Copy link
MemberAuthor

markshannon commentedAug 23, 2021
edited
Loading

Latest benchmarks
Using full release builds (PGO and LTO).

mdickinson reacted with thumbs up emoji

@mdickinson
Copy link
Member

Thanks for all the updates! I'll make another (final, I hope) review pass shortly.

@mdickinsonmdickinson added the 🔨 test-with-buildbotsTest PR w/ buildbots; report in status section labelAug 23, 2021
@bedevere-bot
Copy link

🤖 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-botbedevere-bot removed the 🔨 test-with-buildbotsTest PR w/ buildbots; report in status section labelAug 23, 2021
@markshannonmarkshannon added the 🔨 test-with-buildbotsTest PR w/ buildbots; report in status section labelAug 23, 2021
@bedevere-bot
Copy link

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

@bedevere-botbedevere-bot removed the 🔨 test-with-buildbotsTest PR w/ buildbots; report in status section labelAug 23, 2021
@markshannon
Copy link
MemberAuthor

The failure on buildbot/AMD64 Arch Linux Asan Debug PR is unrelated.

Copy link
Member

@mdickinsonmdickinson left a 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).

@markshannonmarkshannon merged commit15d50d7 intopython:mainAug 25, 2021
@markshannonmarkshannon deleted the streamline-medium-ints branchSeptember 15, 2021 11:51
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;
Copy link
Member

@mdickinsonmdickinsonJan 7, 2022
edited
Loading

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.

Copy link
Member

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.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@vstinnervstinnervstinner left review comments

@mdickinsonmdickinsonmdickinson approved these changes

Assignees
No one assigned
Labels
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

5 participants
@markshannon@mdickinson@bedevere-bot@vstinner@the-knights-who-say-ni

[8]ページ先頭

©2009-2025 Movatter.jp