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