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-29882: Add _Py_popcount32() function by vstinner · Pull Request #20518 · python/cpython

Conversation

@vstinner

@vstinner vstinner commented May 29, 2020 •
edited by bedevere-bot
Loading

Uh oh!

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

Copy link
Copy Markdown
Member
  • Rename pycore_byteswap.h to pycore_bitutils.h.
  • Move popcount_digit() to pycore_bitutils.h as _Py_popcount32().
  • _Py_popcount32() uses GCC and clang builtin function if available.
  • Add unit tests to _Py_popcount32().

https://bugs.python.org/issue29882

Sorry, something went wrong.

Uh oh!

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

All reactions
@vstinner
vstinner requested review from a team, 1st1, rhettinger and tiran as code owners May 29, 2020 17:14
@the-knights-who-say-ni the-knights-who-say-ni added the CLA signed label May 29, 2020
@bedevere-bot bedevere-bot added the awaiting core review label May 29, 2020
@vstinner

vstinner commented May 29, 2020 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Member Author

@mdickinson: here you have.

cc @pablogsal @1st1

All reactions

Sorry, something went wrong.

Uh oh!

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

@vstinner

vstinner commented May 29, 2020

Copy link
Copy Markdown
Member Author

On my x86-64 Fedora 32 with GCC 10.1.1, __builtin_popcount() becomes a call to __popcountdi2() function:

(gdb) disassemble __popcountdi2 
Dump of assembler code for function __popcountdi2:
   0x00007fffeaa997c0 <+0>:	endbr64 
   0x00007fffeaa997c4 <+4>:	movabs rdx,0x5555555555555555
   0x00007fffeaa997ce <+14>:	mov    rax,rdi
   0x00007fffeaa997d1 <+17>:	shr    rax,1
   0x00007fffeaa997d4 <+20>:	and    rax,rdx
   0x00007fffeaa997d7 <+23>:	movabs rdx,0x3333333333333333
   0x00007fffeaa997e1 <+33>:	sub    rdi,rax
   0x00007fffeaa997e4 <+36>:	mov    rax,rdi
   0x00007fffeaa997e7 <+39>:	shr    rdi,0x2
   0x00007fffeaa997eb <+43>:	and    rax,rdx
   0x00007fffeaa997ee <+46>:	and    rdi,rdx
   0x00007fffeaa997f1 <+49>:	add    rdi,rax
   0x00007fffeaa997f4 <+52>:	mov    rax,rdi
   0x00007fffeaa997f7 <+55>:	shr    rax,0x4
   0x00007fffeaa997fb <+59>:	add    rax,rdi
   0x00007fffeaa997fe <+62>:	movabs rdi,0xf0f0f0f0f0f0f0f
   0x00007fffeaa99808 <+72>:	and    rax,rdi
   0x00007fffeaa9980b <+75>:	movabs rdi,0x101010101010101
   0x00007fffeaa99815 <+85>:	imul   rax,rdi
   0x00007fffeaa99819 <+89>:	shr    rax,0x38
   0x00007fffeaa9981d <+93>:	ret    
End of assembler dump.

It looks like the SWAR popcount.

Using -march=native, I get the expected native x86 POPCNT instruction:

popcnt ecx,ecx
All reactions

Sorry, something went wrong.

Uh oh!

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

@vstinner vstinner added the skip news label May 29, 2020
@vstinner

vstinner commented May 29, 2020

Copy link
Copy Markdown
Member Author

I wrote this PR to factorize duplicate function:

  • hamt_bitcount() in hamt.c
  • popcount_digit() in Objects/longobject.c

I also added __builtin_popcount() to address the first paragraph of hamt.c comment:

    /* We could use native popcount instruction but that would
       require to either add configure flags to enable SSE4.2
       support or to detect it dynamically.  Otherwise, we have
       a risk of CPython not working properly on older hardware.

       In practice, there's no observable difference in
       performance between using a popcount instruction or the
       following fallback code.

       The algorithm is copied from:
       https://graphics.stanford.edu/~seander/bithacks.html
    */
All reactions

Sorry, something went wrong.

Uh oh!

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

@vstinner

vstinner commented May 29, 2020

Copy link
Copy Markdown
Member Author

This PR is a follow-up of PR #771 which added int.bit_count() Python function and popcount_digit() C function.

All reactions

Sorry, something went wrong.

Uh oh!

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

@vstinner vstinner mentioned this pull request May 29, 2020
bpo-29882: Add an efficient popcount method for integers #771
Merged
mdickinson
mdickinson reviewed May 30, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed May 30, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed May 30, 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

vstinner commented Jun 2, 2020

Copy link
Copy Markdown
Member Author

@mdickinson: I updated the PR. Would you mind to review it?

All reactions

Sorry, something went wrong.

Uh oh!

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

@mdickinson
mdickinson self-requested a review June 5, 2020 07:55
@mdickinson

mdickinson commented Jun 5, 2020

Copy link
Copy Markdown
Member

Would you mind to review it?

Will do, but not before the weekend.

All reactions

Sorry, something went wrong.

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Include/internal/pycore_bitutils.h Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Modules/_testinternalcapi.c Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Modules/_testinternalcapi.c Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
View reviewed changes
Comment thread Objects/longobject.c Resolved

Uh oh!

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

mdickinson
mdickinson reviewed Jun 6, 2020
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.

I left a few comments; mostly nitpicks, but there are some bits I don't understand (like the SIZEOF_INT == 8 branch).

Sorry, something went wrong.

Uh oh!

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

All reactions
@vstinner

vstinner commented Jun 7, 2020

Copy link
Copy Markdown
Member Author

Oh, 45af786 is good example of why I'm mentioning one used function on an include :-)

All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner added 3 commits June 7, 2020 23:19
@vstinner
bpo-29882: Add _Py_popcount32() function
8daa537
* Rename pycore_byteswap.h to pycore_bitutils.h.
* Move popcount_digit() to pycore_bitutils.h as _Py_popcount32().
* _Py_popcount32() uses GCC and clang builtin function if available.
* Add unit tests to _Py_popcount32().
@vstinner
Enhance unit test
9e813d1
@vstinner
Use constants
b793ff8
vstinner added 3 commits June 7, 2020 23:19
@vstinner
Add implementation note on SSE4a
585f906
@vstinner
hamt.c: cast result explicitly
48df7e3
@vstinner
Address Mark's review
5838d27
* Remove UINT32_C()
* Fix #ifdef to decide if builtin functions are used of not:
  use SIZEOF_INT >= 4. Always use __builtin_popcountl() otherwise.
* popcount_digit(): check PyLong_SHIFT rather than sizeof(digit).
* Fix also two comments
@vstinner

vstinner commented Jun 7, 2020

Copy link
Copy Markdown
Member Author

@mdickinson: PR updated to address your latest review.

PR rebased to fix a merge conflict with 45af786

All reactions

Sorry, something went wrong.

Uh oh!

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

mdickinson
mdickinson approved these changes Jun 8, 2020
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

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 Jun 8, 2020
@vstinner
vstinner merged commit c6b292c into python:master Jun 8, 2020
@bedevere-bot bedevere-bot removed the awaiting merge label Jun 8, 2020
@vstinner
vstinner deleted the bitutils branch June 8, 2020 14:30
@vstinner

vstinner commented Jun 8, 2020

Copy link
Copy Markdown
Member Author

Thanks @mdickinson for the reviews!

All reactions

Sorry, something went wrong.

Uh oh!

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

@niklasf niklasf mentioned this pull request Jun 8, 2020
bpo-29782: Consolidate _Py_Bit_Length() #20739
Merged
niklasf added a commit to niklasf/cpython that referenced this pull request Jun 8, 2020
@niklasf
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.
vstinner pushed a commit that referenced this pull request Jun 15, 2020
@niklasf
bpo-29782: Consolidate _Py_Bit_Length() (GH-20739)
794e7d1
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 fallback implementation suitable for inlining.
This was referenced Jan 22, 2022
bpo-29882: _Py_popcount32() doesn't need 64x64 multiply #30774
Merged
bpo-29882: Fix portability bug introduced in GH-30774 #30794
Merged
@niklasf niklasf mannequin mentioned this pull request Nov 13, 2022
Add an efficient popcount method for integers #74068
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@1st1 1st1 Awaiting requested review from 1st1
@rhettinger rhettinger Awaiting requested review from rhettinger
@tiran tiran Awaiting requested review from tiran
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.

4 participants

@vstinner @mdickinson @the-knights-who-say-ni @bedevere-bot
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.