[GSoC,1/1] add zero count optimization in ewah_bitmap.c

Commit Message

Aryan Gupta March 10, 2024, 4:26 p.m. UTC

Signed-off-by: Aryan Gupta <[e-mail]>
---
 ewah/ewah_bitmap.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

Comments

Junio C Hamano March 11, 2024, 4:14 p.m. UTC | #1

Aryan Gupta <[e-mail]> writes:

> Signed-off-by: Aryan Gupta <[e-mail]>
> ---
>  ewah/ewah_bitmap.c | 9 +++++----
>  1 file changed, 5 insertions(+), 4 deletions(-)
>
> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
> index 8785cbc54a..9056829572 100644
> --- a/ewah/ewah_bitmap.c
> +++ b/ewah/ewah_bitmap.c
> @@ -257,10 +257,11 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo
>  		for (k = 0; k < rlw_get_literal_words(word); ++k) {
>  			int c;
>  
> -			/* todo: zero count optimization */
> -			for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
> -				if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
> -					callback(pos, payload);
> +			if(self->buffer[pointer]) {
> +				for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
> +					if (((eword_t)1 << c) != 0)
> +						callback(pos, payload);
> +				}
>  			}

When self->buffer[pointer] (let's call it the eword) is zero, both
your rewritten version and the original version does the same thing
and will not call the callback at all, but in all other cases,
doesn't your rewrite change the behavior?

Imagine the eword is 01.  The original starts the loop with c==0,
notices that the LSB is on by masking the eword in the bitmap with
((eword_t)1<<c), and calls the callback function.  Your version
notices that the eword is not zero and enters the loop.  Because
((eword_t)1<<c) for all values of c between 0 and BITS_IN_EWORD are
by definition not zero, you end up calling the callback function for
every bit in the word, whether it is on in the eword, no?

Patch

diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
index 8785cbc54a..9056829572 100644
--- a/ewah/ewah_bitmap.c
+++ b/ewah/ewah_bitmap.c
@@ -257,10 +257,11 @@  void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo
 		for (k = 0; k < rlw_get_literal_words(word); ++k) {
 			int c;
 
-			/* todo: zero count optimization */
-			for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
-				if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
-					callback(pos, payload);
+			if(self->buffer[pointer]) {
+				for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
+					if (((eword_t)1 << c) != 0)
+						callback(pos, payload);
+				}
 			}
 
 			++pointer;