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

From: Junio C Hamano <gitster@pobox.com>
To: Aryan Gupta <garyan447@gmail.com>
Cc: git@vger.kernel.org
Subject: Re: [GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c
Date: Mon, 11 Mar 2024 09:14:46 -0700	[thread overview]
Message-ID: <xmqqzfv4u4nd.fsf@gitster.g> (raw)
In-Reply-To: <20240310162614.62691-2-garyan447@gmail.com> (Aryan Gupta's message of "Sun, 10 Mar 2024 17:26:14 +0100")

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?