From: Aryan Gupta Date: Wed, 13 Mar 2024 22:37:51 GMT Subject: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration Message-ID: <20240313223751.50816-1-garyan447@gmail.com> In-Reply-To: <20240310162614.62691-1-garyan447@gmail.com> Signed-off-by: Aryan Gupta --- 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