php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #63773 Improve BitSet::cardinality() performance
Submitted: 2012-12-14 20:18 UTC Modified: 2017-10-24 08:00 UTC
From: harroyo at hangar18 dot cc Assigned:
Status: Open Package: Bitset (PECL)
PHP Version: Irrelevant OS:
Private report: No CVE-ID: None
Welcome back! If you're the original bug submitter, here's where you can edit the bug or add additional notes.
If you forgot your password, you can retrieve your password here.
Password:
Status:
Package:
Bug Type:
Summary:
From: harroyo at hangar18 dot cc
New email:
PHP Version: OS:

 

 [2012-12-14 20:18 UTC] harroyo at hangar18 dot cc
Description:
------------
Current implementation of BitSet::cardinality() counts bits one at a time. This 
can be done a lot better using known fast methods for computing the "hamming 
weight". The easiest way (for Linux) would be to check if the compiler is GCC and 
use the __builtin_popcount() it provides, or use one of the implementations shown 
at http://en.wikipedia.org/wiki/Hamming_weight.

Probably it would also need to change the type of bitset_val on 
https://github.com/php/pecl-numbers-bitset/blob/master/php_bitset.h from unsigned 
char* to unsigned long* (or unsigned long long * etc, so 32/64 bits are handled 
at a time).


Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2012-12-14 20:28 UTC] willfitch@php.net
-Assigned To: +Assigned To: willfitch
 [2017-10-24 08:00 UTC] kalle@php.net
-Status: Assigned +Status: Open -Assigned To: willfitch +Assigned To:
 
PHP Copyright © 2001-2025 The PHP Group
All rights reserved.
Last updated: Tue Feb 18 00:01:30 2025 UTC