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
Have you experienced this issue?
Rate the importance of this bug to you:

 [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

Add a Patch

Pull Requests

Add a Pull Request

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-2017 The PHP Group
All rights reserved.
Last updated: Sun Nov 19 01:31:42 2017 UTC