GeezerVison

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

GeezerVison is showing github.com — bpo-29782: Consolidate _Py_Bit_Length() by niklasf · Pull Request #20739 · python/cpython

Conversation

niklasf commented Jun 8, 2020 •

edited by bedevere-bot

Loading

Uh oh!

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

Copy link

Copy Markdown

Contributor

In GH-2866, _Py_Bit_Length() was added to pymath.h for lack of a better
location. GH-20518 added a more appropriate header file for bit utilities. It
also shows how to properly use intrinsics. This allows reconsidering bpo-29782.

Move the function to the new header.
Changed return type to match __builtin_clzl and reviewed usage.
Use intrinsics where available.
Pick a (mostly theoretical) fallback implementation suitable for
inlining.

https://bugs.python.org/issue29782

Sorry, something went wrong.

Uh oh!

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

All reactions

the-knights-who-say-ni added the CLA signed label

Jun 8, 2020

bedevere-bot added the awaiting review label

Jun 8, 2020

vstinner reviewed

Jun 8, 2020

View reviewed changes

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

Maybe add test_bit_length() to _testinternalcapi.c: see test_popcount().

Sorry, something went wrong.

Uh oh!

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

niklasf reacted with thumbs up emoji

All reactions

👍 1 reaction

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Modules/mathmodule.c Resolved

Uh oh!

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

vstinner commented Jun 8, 2020

Copy link

Copy Markdown

Member

Previous rejected attempt: PR #594.

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

vstinner commented Jun 8, 2020

Copy link

Copy Markdown

Member

cc @mdickinson

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner reviewed

Jun 8, 2020

View reviewed changes

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

I disliked PR #594 because it added #include <intrin.h> to a new *public header file: Include/pyintrinsics.h. This PR is different, all changes are made in the internal C API. We have way more freedom in the internal C API.

Sorry, something went wrong.

Uh oh!

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

All reactions

Comment thread

Modules/mathmodule.c Resolved

Uh oh!

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

vstinner commented Jun 8, 2020

Copy link

Copy Markdown

Member

The Windows build looks broken:

Run .\python.bat -m test.pythoninfo
Running Release|x64 interpreter...
##[error]Process completed with exit code 1.

All reactions

Sorry, something went wrong.

Uh oh!

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

mdickinson self-requested a review

June 8, 2020 18:26

niklasf added 4 commits

June 8, 2020 21:18


          bpo-29782: Consolidate _Py_Bit_Length()

281009c

In pythonGH-2866, _Py_Bit_Length() was added to pymath.h for lack of a better
location. pythonGH-20518 added a more appropriate header file for bit utilities. It
also shows how to properly use intrinsics. This allows reconsidering bpo-29782.

* Move the function to the new header.
* Changed return type to match __builtin_clzl and reviewed usage.
* Use intrinsics where available.
* Pick a (mostly theoretical) fallback implementation suitable for
  inlining.


          Specify required gcc version for __builtin_clzl

65abb83


          Fix _BitScanReverse usage

ce45ff2


          Document reason for include

6464ca6

niklasf force-pushed the bpo-29782-msb branch from 409d58c to e7992ad Compare

June 8, 2020 19:43


          Ensure future compatibility

0bd4265

niklasf force-pushed the bpo-29782-msb branch from e7992ad to 0bd4265 Compare

June 8, 2020 19:50

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Modules/mathmodule.c Resolved

Uh oh!

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

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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


          Do not try to support GCC < 3.4

fbaca66

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

niklasf and others added 2 commits

June 8, 2020 22:03


          Coding style

436f68b


          Fix comment indent

ac664bc

Co-authored-by: Victor Stinner <[email protected]>

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

vstinner reviewed

Jun 8, 2020

View reviewed changes

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

niklasf added 6 commits

June 8, 2020 22:21


          Do not factor out x != 0

3279d17


          Fix and move _Py_bit_length_digit()

525da3d


          Add unit test for _Py_bit_length()

e487622


          Remove useless cast in test

a338761


          Use original implementation as fallback

5a146f7


          Re-enable intrinsics

8e3ce66

niklasf commented Jun 8, 2020

Copy link

Copy Markdown

Contributor Author

Thanks for reviewing.

Also added unit tests as suggested (in addition to the existing test coverage). I briefly disabled the branch with clz (8e3ce66) to get a CI run with the fallback implementation. The current fallback is identical to the original (except for inlining).

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner reviewed

Jun 8, 2020

View reviewed changes

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

Thanks for the many updates! The code now looks better! New review.

Sorry, something went wrong.

Uh oh!

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

All reactions

Comment thread

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

Comment thread

Modules/_testinternalcapi.c Resolved

Uh oh!

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

Comment thread

Modules/_testinternalcapi.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

Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

niklasf and others added 7 commits

June 8, 2020 23:12


          Explicitly cast sizeof

86241f6

Co-authored-by: Victor Stinner <[email protected]>


          Better tests

c7ccbe2

Co-authored-by: Victor Stinner <[email protected]>


          Explain Py_BUILD_ASSERT(sizeof(unsigned long) <= 4)

dfceaf2


          Use volatile so test actually runs intrinsic

fbf01ae


          Remove trailing spaces

991622b


          _Py_bit_length_digit -> bit_length_digit

462d995


          Fixup test expectations

98fc7a8

vstinner commented Jun 8, 2020

Copy link

Copy Markdown

Member

Using gcc 10 -O3 -flto, I get the following machine code in test_bit_length():

# input = rax
# if (x != 0)
test   rax,rax
je     0x7fffeaa99978 <test_bit_length+504>

# return (int)sizeof(unsigned long) * 8 - __builtin_clzl(x);
# return 0x40 - bsr(rax) ^ 0x3f
bsr    rax,rax
mov    ecx,0x40
xor    rax,0x3f
mov    r9d,ecx
sub    r9d,eax
# result = r9d

x86 BSR (Bit Scan Reverse) instruction is used as expected.

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner added the skip news label

Jun 8, 2020

vstinner approved these changes

Jun 8, 2020

View reviewed changes

vstinner 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!

@mdickinson: Do you want to review this PR as well?

Sorry, something went wrong.

Uh oh!

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

All reactions

bedevere-bot added awaiting merge and removed awaiting review labels

Jun 8, 2020

mdickinson commented Jun 9, 2020

Copy link

Copy Markdown

Member

@mdickinson: Do you want to review this PR as well?

I'd very much like to take a look, but am short on available time. Can you give me until the weekend? If I've failed to review by the start of next week, go ahead and merge.

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner commented Jun 9, 2020

Copy link

Copy Markdown

Member

@mdickinson: this PR can wait one week :-)

All reactions

Sorry, something went wrong.

Uh oh!

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

mdickinson reviewed

Jun 14, 2020

View reviewed changes

Comment thread

Objects/longobject.c

		static int
		bit_length_digit(digit x)
		{
		Py_BUILD_ASSERT(PyLong_SHIFT <= sizeof(unsigned long) * 8);

mdickinson Jun 14, 2020

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 nice if C provided some standard way to get the width (in the sense of C99 §6.2.6.2p6) of an integer type, so that we didn't have to use sizeof(unsigned long) * 8, which could fail in the presence of padding bits. But as far as I know it doesn't. Related: https://stackoverflow.com/q/3957252/270986

Sorry, something went wrong.

Uh oh!

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

All reactions

mdickinson approved these changes

Jun 14, 2020

View reviewed changes

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!

Sorry, something went wrong.

Uh oh!

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

All reactions

vstinner merged commit 794e7d1 into python:master

Jun 15, 2020

bedevere-bot removed the awaiting merge label

Jun 15, 2020

vstinner commented Jun 15, 2020

Copy link

Copy Markdown

Member

Thanks @niklasf, I merged your PR.

I removed "(mostly theoretical)" from your commit message:

* Pick a (mostly theoretical) fallback implementation suitable for
  inlining.

We support other C compilers, like XLC.

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

Reviewers

vstinner

vstinner approved these changes

+1 more reviewer

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

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 01402520 — 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.

GeezerVison

Conversation

niklasf commented Jun 8, 2020 • edited by bedevere-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

vstinner commented Jun 8, 2020

Uh oh!

Uh oh!

vstinner commented Jun 8, 2020

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vstinner commented Jun 8, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

niklasf commented Jun 8, 2020

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

vstinner commented Jun 8, 2020

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

mdickinson commented Jun 9, 2020

Uh oh!

vstinner commented Jun 9, 2020

Uh oh!

mdickinson Jun 14, 2020

Choose a reason for hiding this comment

Uh oh!

mdickinson left a comment

Choose a reason for hiding this comment

Uh oh!

vstinner commented Jun 15, 2020

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

niklasf commented Jun 8, 2020 •

edited by bedevere-bot

Loading

Uh oh!

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