Add an efficient popcount method for integers

[niklasf]

BPO	29882
Nosy	@tim-one, @rhettinger, @mdickinson, @vstinner, @njsmith, @markshannon, @serhiy-storchaka, @vedgar, @DimitrisJim, @niklasf, @gbtami
PRs	bpo-29882: Add an efficient popcount method for integers #771 bpo-29882: Add _Py_popcount32() function #20518 bpo-29882: _Py_popcount32() doesn't need 64x64 multiply #30774 bpo-29882: Fix portability bug introduced in GH-30774 #30794

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2020-05-29.16:28:39.179>
created_at = <Date 2017-03-22.17:30:42.549>
labels = ['interpreter-core', 'type-feature', '3.10']
title = 'Add an efficient popcount method for integers'
updated_at = <Date 2022-01-23.09:59:43.073>
user = 'https://github.com/niklasf'

bugs.python.org fields:

activity = <Date 2022-01-23.09:59:43.073>
actor = 'mark.dickinson'
assignee = 'none'
closed = True
closed_date = <Date 2020-05-29.16:28:39.179>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2017-03-22.17:30:42.549>
creator = 'niklasf'
dependencies = []
files = []
hgrepos = []
issue_num = 29882
keywords = []
message_count = 26.0
messages = ['290003', '290013', '290014', '290015', '290016', '290017', '290073', '344215', '344216', '344223', '344224', '344225', '369860', '369878', '369879', '369881', '369887', '369966', '370323', '370423', '370447', '370456', '370987', '372497', '411211', '411357']
nosy_count = 12.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'vstinner', 'casevh', 'njs', 'Mark.Shannon', 'serhiy.storchaka', 'veky', 'Jim Fasarakis-Hilliard', 'niklasf', 'gbtami']
pr_nums = ['771', '20518', '30774', '30794']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue29882'
versions = ['Python 3.10']

[niklasf]

An efficient popcount (something equivalent to bin(a).count("1")) would
be useful for numerics, parsing binary formats, scientific applications
and others.

DESIGN DECISIONS

• Is a popcount method useful enough?
• How to handle negative values?
• How should the method be named?

SURVEY

gmpy calls the operation popcount and returns -1/None for negative values:

>>> import gmpy2
>>> gmpy2.popcount(-10)
-1

>> import gmpy
>> gmpy.popcount(-10)

From the documentation [1]:

If x < 0, the number of bits with value 1 is infinite
so -1 is returned in that case.

(I am not a fan of the arbitrary return value).

The bitarray module has a count(value=True) method:

>>> from bitarray import bitarray
>>> bitarray(bin(123456789).strip("0b")).count()
16

Bitsets [2] exposes __len__.

There is an SSE4 POPCNT instruction. C compilers call the corresponding
intrinsic popcnt or popcount (with some prefix and suffix) and they
accept unsigned arguments.

Rust calls the operation count_ones [3]. Ones are counted in the binary
representation of the *absolute* value. (I propose to do the same).

Introducing popcount was previously considered here but closed for lack
of a PEP or patch: http://bugs.python.org/issue722647

Sensible names could be bit_count along the lines of the existing
bit_length or popcount for gmpy compability and to distinguish it more.

PERFORMANCE

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

[1] https://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions
[2] https://pypi.python.org/pypi/bitsets/0.7.9
[3] https://doc.rust-lang.org/std/primitive.i64.html#method.count_ones

[mdickinson]

Can you give some examples of concrete use-cases? I've spent the last six years or so writing scientific applications and parsing all sorts of odd binary formats, and haven't needed or wanted a popcount yet.

(I am not a fan of the arbitrary return value).

Agreed: if this were implemented, I think raising ValueError would be the most appropriate thing to do for negative inputs.

[niklasf]

Searching popcount in Python files on GitHub yields
a considerable number of examples:

https://github.com/search?utf8=%E2%9C%93&q=popcount+extension%3Apy&type=Code

Perhaps intresting:

• In CPython itself: See count_set_bits in
  Modules/mathmodule.c

• Domain specific applications: Bitboards in Chess,
  fairly shuffling cards in Poker, comparing molecules

• Size of bitsets (see bitarray and bitsets I listed above).
  Probably for this reason also as a first class citizen
  in Redis: https://redis.io/commands/bitcount.

Probably most important:

• As the Hamming Distance:
  https://en.wikipedia.org/wiki/Hamming_distance#History_and_applications

---

Btw. not a concrete application. I just stumbled upon this.
popcnt was considered important enough to be included in the
rather limited WebAssembly instruction set:
https://github.com/WebAssembly/spec/raw/master/papers/pldi2017.pdf

[mdickinson]

Many of those applications are really for bitstrings (chess bitboards, hamming distance), which aren't really the same thing as integers.

Nice find for the mathmodule.c case. I'd forgotten about that one (though according to git blame, apparently I'm responsible for checking it in). It's a fairly obscure corner case, though.

Overall, I'm -1 on adding this: I don't think it meets the bar of being useful enough to justify the extra method. I'd suggest that people needing this kind of efficient bitstring operation use a 3rd-party bitstring library instead.

[serhiy-storchaka]

I think that adding bitarray or bitset (or both) in the stdlib would better satisfy the needs. There are open issues for adding ability to read or set selected bits or range of bits in int or for bitwise operations on bytes. I think that bitarray and bitset would provide better interface for these operations.

[tim-one]

See also:

https://en.wikipedia.org/wiki/Hamming_weight

As that says, there are a number of languages and processors with first class support for a popcount function. I've frequently implemented it in Python when using integers as integer bitsets (i is in the set if and only if bit 2**i is set in the integer), which often - except for finding the cardinality - runs much faster than using general Python sets.

[casevh]

I like the name bit_count and I'll gladly add it to gmpy2 with the appropriate changes to exceptions, etc.

[rhettinger]

Is everyone comfortable with how negative numbers are handled by this patch? It might be better to limit the domain and raise a ValueError rather than make a presumption about what the user intends.

[serhiy-storchaka]

I am going to add the imath module. If we decide to add popcount(), it may be better to add it in this module instead of int class.

[mdickinson]

Is everyone comfortable with how negative numbers are handled by this patch?

Not entirely, but it's not terribly wrong and it's consistent with how int.bit_length works. (I'm also a bit uncomfortable about int.bit_lengths behaviour on negative numbers, but it is the way it is.)

[tim-one]

I prefer that a negative int raise ValueError, but am OK with it using the absolute value instead (i.e., what it does now).

[mdickinson]

I am going to add the imath module.

Aimed at 3.8, or 3.9? This seems somewhat rushed for 3.8.