ENH: Adding `bit_count` (popcount) #19355

ganesh-k13 · 2021-06-26T06:16:08Z

`bit_count` UFunc Implementation

Adding np.bit_count:

>>> a = np.int32(1023).bit_count()
10

ToDos:

Benchmarks:

bench_ufunc.UFunc.time_ufunc_types:

 
python3 runtests.py --bench bench_ufunc.UFunc.time_ufunc_types
Building, see build.log...                 
Build OK                                   
· Discovering benchmarks                   
· Running 1 total benchmarks (1 commits * 1 environments * 1 benchmarks)
[  0.00%] ·· Benchmarking existing-py_usr_bin_python3
[  0.00%] ··· Importing benchmark suite produced output:
[  0.00%] ···· NumPy CPU features: SSE SSE2 SSE3 SSSE3* SSE41* POPCNT* SSE42* AVX* F16C* FMA3* AVX2* AVX512F? AVX512CD? AVX512_KNL? AVX512_KNM? AVX512_SKX? AVX512_CLX? AVX512_CNL? AVX512_ICL?
[ 50.00%] ··· Running (bench_ufunc.UFunc.time_ufunc_types--).
[100.00%] ··· bench_ufunc.UFunc.time_ufunc_types                                                                                                                                                ok
[100.00%] ··· =============== =============
                   ufunc                   
              --------------- ------------- 
                 bit_count      62.9±0.5μs 
              =============== =============

Future Enhancements

Add SIMD implementations for popcount. Apparently, it's efficient.

resolves #16325

numpy/core/src/npymath/npy_math_internal.h.src

numpy/core/code_generators/ufunc_docstrings.py

BvB93

cosh: _UFunc_Nin1_Nout1[L['cosh'], L[8], None]
+ countbits: _UFunc_Nin1_Nout1[L['countbits'], L[5], None]
deg2rad: _UFunc_Nin1_Nout1[L['deg2rad'], L[5], None]

Can you add annotations for the new ufunc in numpy/__init__.pyi?
In case you're wondering, the three parameters are its __name__, ntypes and identity.

ganesh-k13 · 2021-06-26T11:12:04Z

Thanks @BvB93 , was just going to ask where to add annotations :)

mattip · 2021-06-26T21:24:00Z

Could you link to the discussion where the function was proposed on the mailing list or in an issue? This PR feels a bit disconnected from the desire to avoid adding any more functionality to NumPy's namespace, especially functions that do not appear in the array API spec. Maybe this should live somewhere in SciPy?

mattip · 2021-06-26T21:27:14Z

Ahh, I see there was a brief discussion in issue #16325. I will comment there.

numpy/core/src/npymath/npy_math_internal.h.src

numpy/core/code_generators/ufunc_docstrings.py

numpy/core/src/npymath/npy_math_internal.h.src

numpy/core/code_generators/ufunc_docstrings.py

numpy/core/src/npymath/npy_math_internal.h.src

numpy/core/tests/test_umath.py

numpy/__init__.pyi

ganesh-k13 · 2021-06-30T17:13:55Z

The test failed in my machine also. We are hitting some edge case for a 16bit, 9 1s bit combo. https://github.com/numpy/numpy/pull/19355/checks?check_run_id=2954162115#step:4:3482 . Will try to figureout why

[EDIT] It was a missing cast that was causing an unwanted upcast.

numpy/core/src/umath/funcs.inc.src

ganesh-k13 · 2021-07-02T16:37:40Z

I have added a native numpy.core._internal._bit_count(to use in object loops for Python < 3.10) which is basically a Python version of:
https://github.com/python/cpython/pull/771/files#diff-1a6e70e2beeecad88840c67284ac4d54a36998029244771fcc820e801390726aR5332

Please let me know if this approach is ok

[EDIT] Will add UT. I forgot

ganesh-k13 · 2021-07-06T17:08:35Z

Hi all, 234edfe is purely guesswork :). I did not have a reference PR like LCM/GCD. So apologies if it's super wrong :).
Summary of commit:

# This works now:
>>> np.int32(1023).bit_count()
10

[Edit] the parameters everywhere is a place holder, only dtype I have added for now

ganesh-k13 · 2021-07-10T11:53:01Z

It seems we do not have a Python 3.10 build test in the pipelines. Will it make sense to add one in another PR?

[EDIT] Mainly asking as to cover the code in object type, where we use a 3.10 builtin

numpy/core/_methods.py

ganesh-k13 · 2021-07-16T16:49:27Z

Hi all, apart from a few fixes from my side, is there anything major remaining? A review of the object loop and np.int*.bit_count will be helpful as they seem they could use a bit of review. Also, do we hit the mailing list, etc for a wider opinion?

numpy/core/tests/test_umath.py

numpy/core/_methods.py

numpy/core/code_generators/ufunc_docstrings.py

ganesh-k13 · 2021-11-02T03:20:34Z

Thanks Sebastian. I edited the title to avoid confusion.

Adding bitcount method to scalars, e.g.: a = np.int32(1023).bit_count() * ENH: Implementation of bit_count (popcount) * ENH: Add bit_count to integer scalar type * ENH: Annotations for bit_count * ENH, WIP: Documentation for bit_count * DOC: Added `bit_count` (numpy#19355) * BUG: Fixed windows 32 bit issue with no `__popcnt64` * DOC: Refined docstring for bit_count * TST: Tests for bit_count * ENH, MAINT: Changed return type to uint_8 | Removed extra braces and fixed typo * BUG: Fixed syntax of bit_count * DOC, BUG: Fixed bit_count example * DOC, BUG: (numpy#19355) Removed bit_count from routines.math.rst | Improved release notes * BUG: Added type suffix to magic constants * ENH: Handle 32 bit windows popcount | Refactored popcount implementation to new function * MAINT: Refactor type_methods, separate integer definitions * DOC: Added double-ticks

h-vetinari · 2021-11-23T22:40:45Z

Hey everyone, I've started building 1.22.0rc1 for conda-forge, and apparently, the include-guards here don't fully work on windows:

  numpy\core\src\npymath\npy_math_internal.h.src(894): error C3861: '__popcnt16': identifier not found
  numpy\core\src\npymath\npy_math_internal.h.src(890): error C3861: '__popcnt': identifier not found
  numpy\core\src\npymath\npy_math_internal.h.src(890): error C3861: '__popcnt': identifier not found
  numpy\core\src\npymath\npy_math_internal.h.src(900): error C3861: '__popcnt64': identifier not found

Do you want me to raise an issue for this?

PS. As a comparison, I looked up the guards used in the microsoft STL.

charris · 2021-11-23T23:52:11Z

Curious. The wheels compile and run OK on azure Windows. I wonder what the difference is.

h-vetinari · 2021-11-24T00:54:11Z

Curious. The wheels compile and run OK on azure Windows. I wonder what the difference is.

On a hunch (and because this PR was merged just after #20234), I tested it again with vs2019 (conda-forge still uses vs2017 by default), and things pass then.

Though I'm kind of surprised that the CI in this PR was passing before #20234...? 🤔

charris · 2021-11-24T01:10:38Z

We moved up to vs2019 on azure because "vs2017 will will be deprecated Nov 15 and removed next Mar". Azure was giving us pending deprecation notices. See #20234. That was 25 days ago, three days before this was merged.

EDIT: I don't recall if it was passing before that.

h-vetinari · 2021-11-24T01:16:32Z

We moved up to vs2019 on azure because "vs2017 will will be deprecated Nov 15 and removed next Mar".

Yes, I'm aware. I'm not suggesting to revert that. It may just be that conda-forge needs to follow suit here - there's no point (IMO) trying to bridge a gap that MSFT is intentionally creating (and in their defense, they've been extremely conservative with the ABI, so there shouldn't be an argument not to move to vs2019 for basically anyone).

I don't recall if it was passing before that.

Since the PR was not rebased, there are still CI results visible (cf. also the commits tab), and they all look green.

ENH, DOC: Added countbits (popcount) ENH: Popcount implementation ENH: Add popcount to umath ENH: Added countbits (popcount) to umath `__all__` ENH: Refined popcount logic DOC: Added `bit_count` Co-authored-by: Eric Wieser <wieser.eric@gmail.com> MAINT: Renamed `countbits` to `bit_count` MAINT: Fixed 4 1s magic number DOC: Added `popcount` to docstring ENH: Added bit_count annotations ENH: Added GNU/CLANG popcount DOC: Added `popcount` language example ENH, BUG: Moved `bitcount` to npy_math.h as `popcount` | Fixed final right shift ENH: Enable `popcount` for signed TST: Tests for `bit_count` BUG, DOC: (BUG) Added missing typecast causing an unwanted upcast (DOC) Added more details on `popcount` implementation MAINT, BUG: (MAINT) Refined `popcount` TC to use typecode (BUG) Fixed ufunc.ntypes to include signed ints ENH: Added windows builtin support ENH: Added `popcount` implementation for big python ints natively [1/2] `popcount` object loop changes ENH: Object loop for `bit_count` [2/2] `popcount` object loop changes TST: Refined `bit_count` tests and added object type ENH: Added `bit_count` to `np.int*` DOC: Added `np.bit_count` (numpy#19355) MAINT: Various linting and minor fixes: 1. Fixed passing all args to _internals umath bitcount. Note: We use kwargs here that might hinder performance 2. Fixed linting errors. 3. Improved verbosity of logs 4. Made a generic TO_BITS_LEN macro to accomdate more length based functions in future BENCH: Added bit_count (popcount) MAINT: Style nits | Added signed case DOC, MAINT: Improved example ENH: Added annotations for bit_count TST: Added annotations tests for bit_count MAINT: Fixed linting errors MAINT: Moved Magic constants to npy_math_internal MAINT: Remove python implementation | Added 3.10 check to tests DOC: Added abs value usage to doc MAINT: Resolved merge conflicts

vscodegithubby · 2024-01-25T09:43:54Z

Please, add
countl_zero
countl_one
countr_zero
countr_one
has_single_bit

h-vetinari · 2024-01-27T12:34:30Z

@vscodegithubby, please open a separate issue instead of commenting on >2yo merged PRs.

seberg · 2024-01-27T13:34:02Z

If you want to request a new feature and open a new issue, make sure to have more arguments of why it is important enough to be in NumPy and maybe consider starting on the mailing list.

Without that, an issue will hardly be useful unless you know you have strong maintainer (or similar) support. Since new features need champions who push them for a while and be convincing to the community.

github-actions bot added the 01 - Enhancement label Jun 26, 2021

eric-wieser reviewed Jun 26, 2021

View reviewed changes