threads / patch / 61085
Subject: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c
Aryan GuptaHey 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
Aryan Gupta[GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c
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
Junio C HamanoRe: [GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c
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?
Junio C HamanoRe: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c
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.
Aryan GuptaRe: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c
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.
Aryan Gupta[GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration
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
Karthik NayakRe: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration
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.
Junio C HamanoRe: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration
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.