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