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-29782: Use __builtin_clzl for bits_in_digit if available by niklasf · Pull Request #594 · python/cpython

Conversation

@niklasf

@niklasf niklasf commented Mar 10, 2017

Copy link
Copy Markdown
Contributor

No description provided.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@the-knights-who-say-ni

the-knights-who-say-ni commented Mar 10, 2017

Copy link
Copy Markdown

Hello, and thanks for your contribution!

I'm a bot set up to make sure that the project can legally accept your contribution by verifying you have signed the PSF contributor agreement (CLA).

Unfortunately our records indicate you have not signed the CLA. For legal reasons we need you to sign this before we can look at your contribution. Please follow these steps to rectify the issue:

  1. Sign the PSF contributor agreement. The "bugs.python.org username" requested by the form is the "Login name" field in "Your Details" at b.p.o
  2. Wait at least one US business day and then check the "Contributor form received entry under "Your Details" on bugs.python.org to see if your account has been marked as having signed the CLA (the delay is due to a person having to manually check your signed CLA)
  3. Reply here saying you have completed the above steps

Thanks again to your contribution and we look forward to looking at it!
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@the-knights-who-say-ni the-knights-who-say-ni added the CLA not signed label Mar 10, 2017
@mention-bot

mention-bot commented Mar 10, 2017

Copy link
Copy Markdown

@niklasf, thanks for your PR! By analyzing the history of the files in this pull request, we identified @mdickinson, @serhiy-storchaka, @tim-one, @brettcannon and @benjaminp to be potential reviewers.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@serhiy-storchaka serhiy-storchaka assigned mdickinson Mar 10, 2017
@serhiy-storchaka serhiy-storchaka added the performance Performance or resource usage label Mar 10, 2017
mdickinson
mdickinson suggested changes Mar 10, 2017
View reviewed changes

@mdickinson mdickinson left a comment •
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.

Some comments left on the bpo issue. In brief:

  • configuration decisions (deciding whether __builtin_clz is available and does the right thing) should be moved into the configuration machinery.
  • the code currently assumes that digit is the same as unsigned long. That's not always the case.
  • once the above issues are addressed, we still need to weigh any speed advantage against the costs in terms of maintainability, portability, readability.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@mdickinson

mdickinson commented Mar 10, 2017

Copy link
Copy Markdown
Member

the code currently assumes that digit is the same as unsigned long

Ah, no. I see. This should work whenever digit is no larger than unsigned long, thanks to the implicit type conversion. However, that's probably wasteful in the majority of cases; on many (most?) machines, we should be able to use clz rather than clzl, and it may be faster. And while it's probably true that on all current platforms digit is no larger than unsigned long, that's not an assumption we should hardwire in unnecessarily.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@niklasf
niklasf force-pushed the bpo-29782-clzl branch from 4efa595 to bf26e37 Compare March 10, 2017 19:43
@the-knights-who-say-ni the-knights-who-say-ni added CLA signed and removed CLA not signed labels Mar 10, 2017
@niklasf
niklasf force-pushed the bpo-29782-clzl branch 2 times, most recently from 21c4a4b to bff329a Compare March 10, 2017 22:32
@niklasf

niklasf commented Mar 10, 2017 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Contributor Author
  • Making an extra version for 16bit ints does not seem to be worth it, so I settled for unsigned long.
  • Factored out so that mathmodule.c can also take advantage of the function.
  • I might need help with the configuration process. Checking __GNUC__ does not seem to be uncommon, but is this the place to do it? Note that __GNUC__ is also defined by clang.
    I created a new source/header pair which might not be the way to go. Should the header contents go to pyport.h as you suggested? Where to put the C fallback?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@niklasf
niklasf force-pushed the bpo-29782-clzl branch from bff329a to 3cbc250 Compare March 10, 2017 22:57
@niklasf niklasf mentioned this pull request Mar 22, 2017
bpo-29882: Add an efficient popcount method for integers #771
Merged
vstinner
vstinner requested changes Mar 27, 2017
View reviewed changes
Comment thread Python/pyintrinsics.c Outdated

@vstinner vstinner Mar 27, 2017

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.

Please rename the function to _Py_bit_length().

Why the result is signed? Why not unsigned int?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Include/pyintrinsics.h Outdated

@vstinner vstinner Mar 27, 2017

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.

Is the builtin available in old GCC versions? Any idea when the function was added?

Sorry, something went wrong.

Uh oh!

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

@niklasf niklasf Mar 28, 2017 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Contributor 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.

gcc 3.4. I made the guard more precise. It also works for clang.

Btw. while looking how this is usually done in Python I found a typo that would affect gcc 3.x: https://github.com/python/cpython/blob/master/Include/pymacro.h#L56 should say __GNU*C*_MINOR__. I'll make a seperate PR. #878.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Include/pyintrinsics.h Outdated

@vstinner vstinner Mar 27, 2017

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.

would it be possible to avoid the conditional code?

Sorry, something went wrong.

Uh oh!

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

@niklasf niklasf Mar 28, 2017

Copy link
Copy Markdown
Contributor 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.

Unfortunately I don't think so. __builtin_clzl(0) is undefined or rather has different behavior on various processors.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Include/pyintrinsics.h Outdated

@vstinner vstinner Mar 27, 2017

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.

Do we need the following pragma?
#pragma intrinsic(_BitScanReverse)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@niklasf
niklasf force-pushed the bpo-29782-clzl branch from 3cbc250 to 7365797 Compare March 28, 2017 15:53
@niklasf
bpo-29782: Use __builtin_clzl for bits_in_digit if available
f06f612
@niklasf
niklasf force-pushed the bpo-29782-clzl branch from 7365797 to f06f612 Compare March 28, 2017 16:06
@niklasf

niklasf commented Mar 28, 2017

Copy link
Copy Markdown
Contributor Author

@Haypo Thanks for the review. I updated the PR based on your comments.
All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner commented Apr 26, 2017

Copy link
Copy Markdown
Member

http://bugs.python.org/issue29782 has been closed as REJECTED.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vstinner vstinner closed this Apr 26, 2017
@vstinner vstinner mentioned this pull request Jan 16, 2020
bpo-31031: Unify duplicate bits_in_digit and bit_length #2866
Merged
@mdickinson mdickinson mentioned this pull request Apr 22, 2020
Count leading zero bits in one CPU tick #19633
Closed
@vstinner vstinner mentioned this pull request Jun 8, 2020
bpo-29782: Consolidate _Py_Bit_Length() #20739
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@vstinner vstinner vstinner requested changes
+1 more reviewer
@mdickinson mdickinson mdickinson requested changes
Reviewers whose approvals may not affect merge requirements

Uh oh!

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

Assignees

@mdickinson mdickinson

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

@niklasf @the-knights-who-say-ni @mention-bot @mdickinson @vstinner @serhiy-storchaka
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.