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-46406: Faster single digit int division. by gpshead · Pull Request #30626 · python/cpython

Conversation

@gpshead

@gpshead gpshead commented Jan 16, 2022 •
edited by bedevere-bot
Loading

Uh oh!

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

Copy link
Copy Markdown
Member

This expresses the algorithm in a more basic manner resulting in better
instruction generation by todays compilers.

See https://mail.python.org/archives/list/[email protected]/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5

https://bugs.python.org/issue46406

Sorry, something went wrong.

Uh oh!

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

All reactions
@gpshead
bpo-46406: Faster single digit int division.
660cc78
This expresses the algorithm in a more basic manner resulting in better
instruction generation by todays compilers.

See https://mail.python.org/archives/list/[email protected]/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5
@gpshead
gpshead requested a review from mdickinson January 16, 2022 23:45
@the-knights-who-say-ni the-knights-who-say-ni added the CLA signed label Jan 16, 2022
@bedevere-bot bedevere-bot added the awaiting core review label Jan 16, 2022
@gpshead
re-add the assert, reword news.
91b1050
@gpshead
gpshead marked this pull request as ready for review January 17, 2022 03:15
@gpshead gpshead added the performance Performance or resource usage label Jan 17, 2022
mdickinson
mdickinson reviewed Jan 22, 2022
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jan 22, 2022
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

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

mdickinson
mdickinson approved these changes Jan 22, 2022
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 a cast needed to silence the compiler on Windows.

Sorry, something went wrong.

Uh oh!

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

All reactions
@bedevere-bot bedevere-bot added awaiting merge and removed awaiting core review labels Jan 22, 2022
raghavthind2005
raghavthind2005 approved these changes Jan 22, 2022
View reviewed changes
gpshead and others added 2 commits January 22, 2022 10:37
@gpshead @mdickinson
Spell Mark's name properly.
d09f0c7
Co-authored-by: Mark Dickinson <[email protected]>
@gpshead @mdickinson
Add a cast to silence a compiler warning.
9902dc2
Co-authored-by: Mark Dickinson <[email protected]>
@mdickinson

mdickinson commented Jan 23, 2022

Copy link
Copy Markdown
Member

Still LGTM. Thank you!

All reactions

Sorry, something went wrong.

Uh oh!

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

@mdickinson
mdickinson merged commit c7f20f1 into python:main Jan 23, 2022
@bedevere-bot bedevere-bot removed the awaiting merge label Jan 23, 2022
@bedevere-bot

bedevere-bot commented Jan 23, 2022

Copy link
Copy Markdown

@mdickinson: Please replace # with GH- in the commit message next time. Thanks!

All reactions

Sorry, something went wrong.

Uh oh!

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

@gpshead
gpshead deleted the long-faster-divide branch January 23, 2022 10:02
tim-one
tim-one reviewed Jan 23, 2022
View reviewed changes
Comment thread Objects/longobject.c
PGO/FDO builds doing value specialization such as a fast path for //10. :)

Verify that 17 isn't specialized and this works as a quick test:
python -m timeit -s 'x = 10**1000; r=x//10; assert r == 10**999, r' 'x//17'

@tim-one tim-one Jan 23, 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.

Asserting that division by 10 "works" is irrelevant when the test is actually dividing by 17. But it's a timing statement, so asserting that the division works is beside the point anyway. The point is to get the timing, so

python -m timeit -s 'x = 10**1000' 'x//17'

would be best. And 17 isn't of real interest anyway. Use 10 instead. That's the value we've actually seen special-cased in PGO builds. 17 only came up when Mark temporarily fudged a PGO-build input test to pick on 17 instead of 10, just to see what would happen.

Sorry, something went wrong.

Uh oh!

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

All reactions

@gpshead gpshead Jan 24, 2022

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.

The command is just a paste of what i was using in my terminal as a quick unittest and microbenchmark. The assert in the setup code is a unittest. It's just easy to write a concise test using 10 and what value is used there isn't really relevant to what is used in the x//17 microbenchmark expression itself.

Sorry, something went wrong.

Uh oh!

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

All reactions
Comment thread Objects/longobject.c
remainder = dividend % n;
pout[size] = quotient;
}
return remainder;

@tim-one tim-one Jan 23, 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.

Patterns like *--pin and *--pout are ubiquitous in this file. so converting that style to pin[size] (etc) is jarring in context. The patch would be better if it stuck to changing what needed to be changed.

It would also be good to add a comment explaining why computing both "/" and "%" is faster on most boxes now than doing what the code originally did. "/" and "%" are both very expensive if they're done in isolation, which is presumably why the original code did a "*" and "-" instead of "%".

Sorry, something went wrong.

Uh oh!

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

All reactions

@gpshead gpshead Jan 24, 2022 •
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.

Feel free to add the missing comment to this effect while you're in this file in your #30856.

[] vs pointer arithmetic would make me want to rerun benchmarks and examine generated code out of curiosity so i'll leave that alone for now - it might be worth investigating and would be consistent. I just took what Mark had written on python-dev and ran with it.

Sorry, something went wrong.

Uh oh!

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

All reactions
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

3 more reviewers
@tim-one tim-one tim-one left review comments
@mdickinson mdickinson mdickinson approved these changes
@raghavthind2005 raghavthind2005 raghavthind2005 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

performance Performance or resource usage

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.

6 participants

@gpshead @mdickinson @bedevere-bot @tim-one @raghavthind2005 @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.