GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — bpo-44946: Streamline operators and creation of ints for common case of single 'digit'. by markshannon · Pull Request #27832 · python/cpython

Conversation

@markshannon

@markshannon markshannon commented Aug 19, 2021 •
edited by bedevere-bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

Modest speedup of 1%

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@markshannon
Streamline binary operations and creating new int objects for common …
da57f0b
…case of single 'digit'.
@markshannon markshannon added the skip news label Aug 19, 2021
@the-knights-who-say-ni the-knights-who-say-ni added the CLA signed label Aug 19, 2021
@bedevere-bot bedevere-bot added the awaiting core review label Aug 19, 2021
vstinner
vstinner reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

@markshannon
Make sure that all ints, even internal, temporary ones, have at least…
0533a9f
… one digit.
@mdickinson mdickinson self-assigned this Aug 19, 2021
@markshannon
Readability improvements as suggested by Victor Stinner.
9349daa
@mdickinson mdickinson removed their assignment Aug 19, 2021
@mdickinson
mdickinson self-requested a review August 19, 2021 14:33
@markshannon
Prefix private function name with _
96496e2
mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson reviewed Aug 19, 2021
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

markshannon added 2 commits August 19, 2021 21:16
@markshannon
Reduce the number of casts.
5e4aad5
@markshannon
Avoid casting away top bits.
59ba476
@mdickinson

mdickinson commented Aug 20, 2021

Copy link
Copy Markdown
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?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

markshannon added 2 commits August 20, 2021 11:04
@markshannon
Streamline integer negation and invert a bit. Suggested by Mark Dicki…
0d3ca1d
…nson.
@markshannon
Clarify comment and internal function name. Remove a bit of redundant…
c73333b
… code.
@markshannon

markshannon commented Aug 20, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

markshannon added 5 commits August 20, 2021 12:39
@markshannon
Remove two more narrowing casts.
16d3167
@markshannon
Change _PyLong_FromLarge to use correctly sized int.
f20a2a8
@markshannon
Avoid more narrowings.
ab2b908
@markshannon
Revert get_small_int to taking a sdigit. Place narrowing casts in cor…
e43060a
…rect places.
@markshannon
Use _PyLong_FromSTwoDigits not PyLong_FromLong in long_add.
ed2a430
@markshannon

markshannon commented Aug 20, 2021

Copy link
Copy Markdown
Member Author

@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 that digit op digit needs more than sdigit 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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mdickinson

mdickinson commented Aug 21, 2021

Copy link
Copy Markdown
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 types digit, sdigit, twodigits or stwodigits.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mdickinson
mdickinson self-requested a review August 21, 2021 10:54
mdickinson
mdickinson reviewed Aug 21, 2021
View reviewed changes

@mdickinson mdickinson left a comment

Copy link
Copy Markdown
Member

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 of PyLong_FromLong? As much as possible, I'd like to keep the digit-based logic (which should be using nothing other than digit, sdigit, twodigit and stwodigits 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.)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread 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)

@mdickinson mdickinson Aug 21, 2021

Copy link
Copy Markdown
Member

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@mdickinson mdickinson Aug 25, 2021

Copy link
Copy Markdown
Member

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 if x is large enough, leading to the possibility of false positives for IS_MEDIUM_INT. For example, that will happen on Windows with a large Py_ssize_t value and 15-bit digits - in that case, Py_ssize_t is much larger than unsigned long.

So there's some restriction on the value of x for which this test is valid. "Fits in stwodigits" would probably be enough, but I don't think we use this macro for values outside the range (-PyLong_BASE**2, PyLong_BASE**2).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@mdickinson mdickinson Aug 25, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

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 an unsigned long to a (signed!) int, since the integer promotions will promote the unsigned short PyLong_MASK to an int (though even that part is not guaranteed by the standard - there's nothing preventing short and int having the same precision, in which case PyLong_MASK will be promoted to unsigned int instead of int). So now we have to consult the rules for unsigned + signed addition in the "usual arithmetic conversions", which eventually say that because long has greater rank than int (even if it has the same precision), both operands will be treated as unsigned long for the addition.

The 2 * PyLong_MASK is another case that could end up being either signed or unsigned depending on ranks, types, etc; it's probably better spelled as 2U * 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 the x, in case someone tries to use IS_MEDIUM_INT on an expression more complicated than a single name.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@markshannon markshannon Aug 25, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

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 than stwodigits or sdigits, the caller is responsible.

static inline int is_medium_int(stwodigits x)
{
    /* We have to take care here to make sure that we are
     * comparing unsigned values. */
    twodigits x_plus_mask = ((twodigits)x) + PyLong_MASK;
    return x_plus_mask < ((twodigits)PyLong_MASK) + PyLong_BASE;
}

Does that seem sensible?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

@mdickinson

mdickinson commented Aug 21, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@markshannon
Implement PyLong_FromLong separately from _PyLong_FromSTwoDigits to a…
1f2d47c
…llow for 15 bit digits on 64 bit machines.
@markshannon

markshannon commented Aug 23, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

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

mdickinson reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mdickinson

mdickinson commented Aug 23, 2021

Copy link
Copy Markdown
Member

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mdickinson mdickinson added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Aug 23, 2021
@bedevere-bot

bedevere-bot commented Aug 23, 2021

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @mdickinson for commit 1f2d47c 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Aug 23, 2021
@markshannon
Don't overflow shift in PyLong_FromLong.
649c311
@markshannon markshannon added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Aug 23, 2021
@bedevere-bot

bedevere-bot commented Aug 23, 2021

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @markshannon for commit 649c311 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Aug 23, 2021
@markshannon

markshannon commented Aug 24, 2021

Copy link
Copy Markdown
Member Author

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

mdickinson
mdickinson approved these changes Aug 25, 2021
View reviewed changes

@mdickinson mdickinson left a comment

Copy link
Copy Markdown
Member

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 the IS_MEDIUM_INT definition changes (parentheses around the x, 2U in place of 2).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Objects/longobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot bedevere-bot added awaiting merge and removed awaiting core review labels Aug 25, 2021
markshannon added 2 commits August 25, 2021 12:05
@markshannon
Convert IS_MEDIUM_INT macro to inline function.
a69f420
@markshannon
Edit comment
47571ff
@markshannon
markshannon merged commit 15d50d7 into python:main Aug 25, 2021
@bedevere-bot bedevere-bot removed the awaiting merge label Aug 25, 2021
@markshannon
markshannon deleted the streamline-medium-ints branch September 15, 2021 11:51
@mdickinson mdickinson mentioned this pull request Dec 22, 2021
bpo-46055: Speed up binary shifting operators #30044
Merged
mdickinson
mdickinson reviewed Jan 7, 2022
View reviewed changes
Comment thread Objects/longobject.c
/* 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;

@mdickinson mdickinson Jan 7, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

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 an unsigned long fits in something of type twodigits. I'll open a bug report and make a PR when I get the chance.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@mdickinson mdickinson Jan 9, 2022

Copy link
Copy Markdown
Member

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 from longintrepr.h, twodigits has type either unsigned long or uint64_t (depending on PYLONG_BITS_IN_DIGIT), and no platform we currently care about has a long larger than uint64_t.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@mdickinson mdickinson mentioned this pull request Jan 9, 2022
bpo-46311: Clean up PyLong_FromLong and PyLong_FromLongLong #30496
Merged
@vstinner vstinner mentioned this pull request Dec 5, 2022
Drop support for platforms without two's complement integer representation: require two's complement to build Python #100008
Closed
@mdickinson mdickinson mentioned this pull request Jan 14, 2023
long_subtype_new underallocates for zero #101037
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@vstinner vstinner vstinner left review comments
+1 more reviewer
@mdickinson mdickinson mdickinson approved these changes
Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

5 participants

@markshannon @mdickinson @bedevere-bot @vstinner @the-knights-who-say-ni
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.