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

From: Aryan Gupta <[email-masked]>
Date: Wed, 13 Mar 2024 23:37:51 +0100

Signed-off-by: Aryan Gupta <[email-masked]>
---

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