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

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

[Aryan Gupta]

Hey everyone

I hope you are doing great. I came across a "todo" in the code base 
which was based on zero count optimization. I tried to fix do it but
I am not sure if this was the required this or not. I would love your 
guidance on this. 

Thank you. Have a nice day!

Regards
Aryan Gupta


Aryan Gupta (1):
  add zero count optimization in ewah_bitmap.c

 ewah/ewah_bitmap.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

-- 
2.25.1

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

[Aryan Gupta]

Signed-off-by: Aryan Gupta <garyan447@gmail.com>
---
 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);
+				}
 			}
 
 			++pointer;
-- 
2.25.1

Re: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c

[Junio C Hamano]

Aryan Gupta <garyan447@gmail.com> writes:

> Hey everyone
>
> I hope you are doing great. I came across a "todo" in the code base 
> which was based on zero count optimization. I tried to fix do it but
> I am not sure if this was the required this or not.

Do you mean that you are not sure if the improvement you made is
what Vicent Marti meant by "zero count optimization" when e1273106
(ewah: compressed bitmap implementation, 2013-11-14) was written?

Unfortunatelly, "what is "zero count optimization" in computer
programming?" does not produce great hits, and you are probably
better off to ask who wrote that comment (Cc'ed).

A few general pieces of advice:

 * We usually don't do a cover letter for a single patch (instead we
   write extra explanation after the three-dash line).

 * An optimization patch usually is expected to come with
   performance measurement, just like a bugfix patch is expected to
   come with tests that show existing breakages that change the
   behaviour for the better with the fix.

 * Pay attention to coding style, as deviating from existing style
   distracts reviewers and causes them to miss obvious bugs.

Thanks.

Re: [GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c

[Junio C Hamano]

Aryan Gupta <garyan447@gmail.com> writes:

> Signed-off-by: Aryan Gupta <garyan447@gmail.com>
> ---
>  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?

Re: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c

[Aryan Gupta]

On Mon, Mar 11, 2024 at 5:08 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> Aryan Gupta <garyan447@gmail.com> writes:
>
> > Hey everyone
> >
> > I hope you are doing great. I came across a "todo" in the code base
> > which was based on zero count optimization. I tried to fix do it but
> > I am not sure if this was the required this or not.
>
> Do you mean that you are not sure if the improvement you made is
> what Vicent Marti meant by "zero count optimization" when e1273106
> (ewah: compressed bitmap implementation, 2013-11-14) was written?
>
Yes.
> Unfortunatelly, "what is "zero count optimization" in computer
> programming?" does not produce great hits, and you are probably
> better off to ask who wrote that comment (Cc'ed).
>
Sure.
> A few general pieces of advice:
>
>  * We usually don't do a cover letter for a single patch (instead we
>    write extra explanation after the three-dash line).
>
>  * An optimization patch usually is expected to come with
>    performance measurement, just like a bugfix patch is expected to
>    come with tests that show existing breakages that change the
>    behaviour for the better with the fix.
>
>  * Pay attention to coding style, as deviating from existing style
>    distracts reviewers and causes them to miss obvious bugs.
>
> Thanks.

Okay will take care of this. Thanks a lot.

[GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration

[Aryan Gupta]

Signed-off-by: Aryan Gupta <garyan447@gmail.com>
---

Thank you Vicent for the guidance. I am still not sure how 
to do the performance measurement for this improvement. Any 
guidance would be appreciated. 

 ewah/ewah_bitmap.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
index 8785cbc54a..1a75f50682 100644
--- a/ewah/ewah_bitmap.c
+++ b/ewah/ewah_bitmap.c
@@ -257,12 +257,15 @@ 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);
+			eword_t bitset = self->buffer[pointer]; 
+			while(bitset != 0) {
+				eword_t t = bitset & -bitset; 
+				int r = __builtin_ctzl(bitset); 
+				bitset ^= t; 
+				callback(pos+r, payload);
 			}
-
+			
+			pos += BITS_IN_EWORD;
 			++pointer;
 		}
 	}
-- 
2.25.1

Re: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration

[Karthik Nayak]

[-- Attachment #1: Type: text/plain, Size: 1710 bytes --]

Aryan Gupta <garyan447@gmail.com> writes:

Hello,

> Signed-off-by: Aryan Gupta <garyan447@gmail.com>
> ---
>
> Thank you Vicent for the guidance. I am still not sure how
> to do the performance measurement for this improvement. Any
> guidance would be appreciated.
>

I guess there is some off-list discussion here. That along with the fact
that the commit message is missing makes it really hard to understand
how this is better than what was here already.

The guidelines ('Documentation/SubmittingPatches') also state how to
draft the commit message. This patch only seems to have a title, it is
recommend to add a description as to why this change is being made.

>
>  ewah/ewah_bitmap.c | 13 ++++++++-----
>  1 file changed, 8 insertions(+), 5 deletions(-)
>
> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
> index 8785cbc54a..1a75f50682 100644
> --- a/ewah/ewah_bitmap.c
> +++ b/ewah/ewah_bitmap.c
> @@ -257,12 +257,15 @@ 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);
> +			eword_t bitset = self->buffer[pointer];
> +			while(bitset != 0) {
> +				eword_t t = bitset & -bitset;
> +				int r = __builtin_ctzl(bitset);
> +				bitset ^= t;
> +				callback(pos+r, payload);
>  			}
> -
> +			
> +			pos += BITS_IN_EWORD;
>  			++pointer;
>  		}
>  	}

The bit manipulation done here is slightly hard to comprehend, it would
be nice if you could also add some comments as to what is being done
here and why.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]

Re: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration

[Junio C Hamano]

Karthik Nayak <karthik.188@gmail.com> writes:

> Aryan Gupta <garyan447@gmail.com> writes:
>
> Hello,
>
>> Signed-off-by: Aryan Gupta <garyan447@gmail.com>
>> ---
>>
>> Thank you Vicent for the guidance. I am still not sure how
>> to do the performance measurement for this improvement. Any
>> guidance would be appreciated.
>>
>
> I guess there is some off-list discussion here. That along with the fact
> that the commit message is missing makes it really hard to understand
> how this is better than what was here already.
>
> The guidelines ('Documentation/SubmittingPatches') also state how to
> draft the commit message. This patch only seems to have a title, it is
> recommend to add a description as to why this change is being made.

Yes.

>> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
>> index 8785cbc54a..1a75f50682 100644
>> --- a/ewah/ewah_bitmap.c
>> +++ b/ewah/ewah_bitmap.c
>> @@ -257,12 +257,15 @@ 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);
>> +			eword_t bitset = self->buffer[pointer];
>> +			while(bitset != 0) {
>> +				eword_t t = bitset & -bitset;
>> +				int r = __builtin_ctzl(bitset);
>> +				bitset ^= t;
>> +				callback(pos+r, payload);
>>  			}
>> -
>> +			
>> +			pos += BITS_IN_EWORD;
>>  			++pointer;
>>  		}
>>  	}
>
> The bit manipulation done here is slightly hard to comprehend, it would
> be nice if you could also add some comments as to what is being done
> here and why.

In addition, this patch assumes that __builtin_ctzl() function is
always available no matter what environment the code is built on,
which I am not sure is a safe.  Quite honestory, I suspect that the
whole of "todo" is to seamlessly detect the presense of the builtin
support to count the top zero bit, use it only when it is there, and
giving a fallback implementation when it does not exist.  The code
itself to use the builtin is only 20% of that effort ;-)

And of course, there is benchmark.  To show how much better
performance gets for people with that function, and more importantly
to show that the performance does not degrade for those who are
without.

Thanks.