php.net |  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
 [2012-12-14 20:07 UTC] harroyo at hangar18 dot cc
Description:
------------
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)
        {
                i--;
		if (intern->bitset_val[i / CHAR_BIT] & (1 << (i % CHAR_BIT))) {
			highest_bit = i;
                        break;
		}
	}

	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?:

                i--;

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

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


Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2012-12-14 20:28 UTC] willfitch@php.net
-Assigned To: +Assigned To: willfitch
 [2012-12-17 17:07 UTC] willfitch@php.net
-Status: Assigned +Status: Closed
 [2012-12-17 17:07 UTC] willfitch@php.net
The fix for this bug has been committed.

Snapshots of the sources are packaged every three hours; this change
will be in the next snapshot. You can grab the snapshot at
http://snaps.php.net/.

 For Windows:

http://windows.php.net/snapshots/
 
Thank you for the report, and for helping us make PHP better.


 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Dec 26 10:01:29 2024 UTC