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

From: Karthik Nayak <karthik.188@gmail.com>
To: Aryan Gupta <garyan447@gmail.com>, git@vger.kernel.org
Subject: Re: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration
Date: Sun, 17 Mar 2024 20:08:41 -0700	[thread overview]
Message-ID: <CAOLa=ZSijjnfa8UEEWPi8Cb7Q1hLbgrez7VX-LxshmUhNM29DQ@mail.gmail.com> (raw)
In-Reply-To: <20240313223751.50816-1-garyan447@gmail.com>

[-- 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 --]