Re: [GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Mar 11, 2024, 16:14 UTC
- Message-ID
- <xmqqzfv4u4nd.fsf@gitster.g>
- In-Reply-To
- <20240310162614.62691-2-garyan447@gmail.com>
Aryan Gupta <garyan447@gmail.com> writes:
Show 23 quoted lines
> 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?