|  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #63772 Improve BitSet::length() performance
Submitted: 2012-12-14 20:07 UTC Modified: 2012-12-17 17:07 UTC
From: harroyo at hangar18 dot cc Assigned: willfitch (profile)
Status: Closed 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 this is not your bug, you can add a comment by following this link.
If this is your bug, but you forgot your password, you can retrieve your password here.
Bug Type:
From: harroyo at hangar18 dot cc
New email:
PHP Version: OS:


 [2012-12-14 20:07 UTC] harroyo at hangar18 dot cc
Currently it always traverses the bitset from bit 0 to the last one, but I think 
it could 
be rewritten to traverse the bitset backwards and stop and return the first bit 
set found 
from the end. Something like this:

PHP_METHOD(BitSet, length)
	php_bitset_object *intern;
	long highest_bit = -1, i = 0, total_bits = 0;

	intern = bitset_get_intern_object(getThis() TSRMLS_CC);
	total_bits = intern->bitset_len * CHAR_BIT;

        i = total_bits;

	while(i > 0)
		if (intern->bitset_val[i / CHAR_BIT] & (1 << (i % CHAR_BIT))) {
			highest_bit = i;

	RETURN_LONG(highest_bit + 1);

I think it could also be further optimized by checking if all bits are zero one 
word at a 
time. Changing the code inside the while loop to something like this?:


                if (intern->bitset_val[i / CHAR_BIT] == (unsigned char) 0x0) {
			i -= CHAR_BIT;

		if (intern->bitset_val[i / CHAR_BIT] & (1 << (i % CHAR_BIT))) {
			highest_bit = i;


Add a Patch

Pull Requests

Add a Pull Request