bpo-29882: Add an efficient popcount method for integers#771

niklasf

https://bugs.python.org/issue29882

mention-bot

@niklasf, thanks for your PR! By analyzing the history of the files in this pull request, we identified @tim-one, @birkenfeld and @ncoghlan to be potential reviewers.

ilevkivskyi

Some compilers (gcc) provide hardware optimized __builtin_popcount function(s). Could these speed-up the implementation?

niklasf

@ilevkivskyi: Yes, using hardware popcnt makes this ever so slightly faster.

$ ./python -m timeit "bin(123456789).count('1')"  # equivalent
1000000 loops, best of 5: 286 nsec per loop
$ ./python -m timeit "(123456789).bit_count()"  # gnuc builtin
5000000 loops, best of 5: 44.8 nsec per loop
$ ./python -m timeit "(123456789).bit_count()"  # swar32
5000000 loops, best of 5: 46.3 nsec per loop

Previously I have submitted #594, but so far there is no consensus on wether or how to use these intrinsics. So I think it's best to consider this seperately.

Edit: I should also mention that there is a faster software implementation, using complete lookup tables for 16bit integers. This one is commonly used in chess engines if hardware popcnt is not available, but seems like a rather large overhead for a general purpose interpreter.

methane

Code looks OK.
But it seems no consensus about adding this method or not.

niklasf

Thanks for reviewing. All done, in case we do decide to add this.

mdickinson

@niklasf I'm interested in getting this updated and merged, for Python 3.10. May I merge master into this branch and make the appropriate fixes (changing the "whats new" entry from 3.8 to 3.10)? Or would you prefer to do that yourself?

niklasf

@mdickinson Of course, feel free to modify as needed.

mdickinson

LGTM. (Admittedly that's not entirely an independent judgement at this point, but I haven't changed any of the core code or tests.)

vstinner

LGTM.

LGTM: the implementation is correct. I'm not strongly excited by having this method since I never needed it, but it seems like some other people need it. So well, it looks reasonable to add it. Also, in general, I completely trust @mdickinson :-)

mdickinson

The current implementation of popcount_digit isn't quite as portable as it should be.

The fix should be trivial. I'll look into it.

bedevere-bot

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

mdickinson

Re-approving after fixing my own portability objection.

mdickinson

Merging. @niklasf: Thank you!

bedevere-bot

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

vstinner

OMG, I was merging the PR (I was editing the commit message) while @mdickinson merged it :-D Thanks @mdickinson ;-)

niklasf

Thanks for getting this over the finish line!

vstinner

PR created in 2017! It has an identifier lower than 1000 rather than the latest PR got the identifier 20517! Thanks @niklasf!

vstinner

I wrote PR #20518 which adds a _Py_popcount32() static inline function based on popcount_digit().

* 'master' of github.com:python/cpython: (497 commits) bpo-40061: Fix a possible refleak in _asynciomodule.c (pythonGH-19748) bpo-40798: Generate a different message for already removed elements (pythonGH-20483) closes bpo-29017: Update the bindings for Qt information with PySide2 (pythonGH-20149) bpo-39885: Make IDLE context menu cut and copy work again (pythonGH-18951) bpo-29882: Add an efficient popcount method for integers (python#771) Further de-linting of zoneinfo module (python#20499) bpo-40780: Fix failure of _Py_dg_dtoa to remove trailing zeros (pythonGH-20435) Indicate that abs() method accept argument that implement __abs__(), just like call() method in the docs (pythonGH-20509) bpo-39040: Fix parsing of email mime headers with whitespace between encoded-words. (pythongh-17620) bpo-40784: Fix sqlite3 deterministic test (pythonGH-20448) bpo-30064: Properly skip unstable loop.sock_connect() racing test (pythonGH-20494) Note the output ordering of combinatoric functions (pythonGH-19732) bpo-40474: Updated coverage.yml to better report coverage stats (python#19851) bpo-40806: Clarify that itertools.product immediately consumes its inpt (pythonGH-20492) bpo-1294959: Try to clarify the meaning of platlibdir (pythonGH-20332) bpo-37878: PyThreadState_DeleteCurrent() was not removed (pythonGH-20489) bpo-40777: Initialize PyDateTime_IsoCalendarDateType.tp_base at run-time (pythonGH-20493) bpo-40755: Add missing multiset operations to Counter() (pythonGH-20339) bpo-25920: Remove socket.getaddrinfo() lock on macOS (pythonGH-20177) bpo-40275: Fix test.support.threading_helper (pythonGH-20488) ...

HannesGitH

code

import random
import timeit

lens = range(1, 10000)
maxs = [2**i for i in lens]

# array with random numbers in [0, maxs[i]-1]
randos = [max + random.randrange(max) for max in maxs]

# time bin().count('1') vs bit_count() for each random number
bin_times = [timeit.timeit(lambda: bin(rando).count('1'), number=100) for rando in randos]
bit_count_times = [timeit.timeit(lambda: rando.bit_count(), number=100) for rando in randos]

# create plot
from matplotlib import pyplot as plt

plt.loglog(lens, bin_times, label='bin().count(\'1\')')
plt.loglog(lens, bit_count_times, label='bit_count()')
plt.legend()
plt.show()

mdickinson

@HannesGitH Why the comment? Is there some action that needs to be taken?

HannesGitH

@HannesGitH Why the comment? Is there some action that needs to be taken?

nope, all fine, sorry

just wanted to add the speedup graph for anyone who stumbles upon this and is curious

the-knights-who-say-ni added the label Mar 22, 2017

Mariatta added needs rebase and removed needs rebase labels Oct 9, 2017

brettcannon added the awaiting review label Feb 21, 2018

methane reviewed Jun 4, 2018

View reviewed changes

mdickinson reviewed Jun 1, 2019

View reviewed changes

niklasf force-pushed the bpo-29882-popcount branch from 1c6e9fa to b6e46da Compare June 2, 2019 09:21

bpo-29882: Add an efficient popcount method for integers

74e3ea6

niklasf force-pushed the bpo-29882-popcount branch from b6e46da to 74e3ea6 Compare June 2, 2019 09:33

hexchain mentioned this pull request May 21, 2020

ENH: Expose bit_count ufunc equivalent to the scalar methods numpy/numpy#16325

Closed

mdickinson reviewed May 25, 2020

View reviewed changes

mdickinson added 3 commits May 26, 2020 10:00

Merge remote-tracking branch 'upstream/master' into bpo-29882-popcount

16cc8e5

Update 'sign bit' and versionadded in docs

19da190

Add entry to whatsnew document

070ac45

mdickinson reviewed May 26, 2020

View reviewed changes

mdickinson approved these changes May 26, 2020

View reviewed changes

bedevere-bot added awaiting merge and removed awaiting review labels May 26, 2020

vstinner reviewed May 26, 2020

View reviewed changes

Doc: use positive example, mention population count

b87f162

vstinner approved these changes May 27, 2020

View reviewed changes

Merge remote-tracking branch 'upstream/master' into bpo-29882-popcount

46d8bc9

mdickinson suggested changes May 29, 2020

View reviewed changes

bedevere-bot removed the awaiting merge label May 29, 2020

bedevere-bot added the awaiting changes label May 29, 2020

Ensure popcount_digit is portable with 64-bit ints

3e8422b

mdickinson approved these changes May 29, 2020

View reviewed changes

bedevere-bot added awaiting merge and removed awaiting changes labels May 29, 2020

mdickinson merged commit 8bd216d into python:master May 29, 2020

bedevere-bot removed the awaiting merge label May 29, 2020

vstinner mentioned this pull request May 29, 2020

bpo-29882: Add _Py_popcount32() function #20518

Merged

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

vihan29 mentioned this pull request Oct 1, 2022

Gaussian Elimination brc7/caramel#4

Merged

niklasf mannequin mentioned this pull request Nov 13, 2022

Add an efficient popcount method for integers #74068

Closed

Conversation

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

Uh oh!

Uh oh!

mention-bot commented Mar 22, 2017

Uh oh!

ilevkivskyi commented Mar 22, 2017

Uh oh!

niklasf commented Mar 22, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

methane left a comment

Choose a reason for hiding this comment

Uh oh!

niklasf commented Jun 2, 2019

Uh oh!

mdickinson commented May 25, 2020

Uh oh!

niklasf commented May 25, 2020

Uh oh!

mdickinson left a comment

Choose a reason for hiding this comment

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

mdickinson left a comment

Choose a reason for hiding this comment

Uh oh!

bedevere-bot commented May 29, 2020

Uh oh!

mdickinson left a comment

Choose a reason for hiding this comment

Uh oh!

mdickinson commented May 29, 2020

Uh oh!

bedevere-bot commented May 29, 2020

Uh oh!

vstinner commented May 29, 2020

Uh oh!

niklasf commented May 29, 2020

Uh oh!

vstinner commented May 29, 2020

Uh oh!

vstinner commented May 29, 2020

Uh oh!

HannesGitH commented Jan 26, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mdickinson commented Jan 26, 2023

Uh oh!

HannesGitH commented Jan 26, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

12 participants

niklasf commented Mar 22, 2017 •

edited by bedevere-bot

Loading

niklasf commented Mar 22, 2017 •

edited

Loading

HannesGitH commented Jan 26, 2023 •

edited

Loading

HannesGitH commented Jan 26, 2023 •

edited

Loading