From da9e9d02b83525428340097bc25592b6d23b1dfc Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sat, 14 Nov 2020 16:58:23 +0100 Subject: bitset: use ffsl to accelerate iterations over set bits Currently we iterate over words bit by bit. Instead, we should jump from set bit to set bit. Suggested by Bruno Haible. * modules/bitset: Depend upon ffsl. * lib/bitset/base.h (bitset_ffs, BITSET_FOR_EACH_BIT): New. * lib/bitset/array.c (abitset_list): Use BITSET_FOR_EACH_BIT. --- lib/bitset/array.c | 50 ++++++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 32 deletions(-) (limited to 'lib/bitset/array.c') diff --git a/lib/bitset/array.c b/lib/bitset/array.c index 1db5838914..6c5f7ed34f 100644 --- a/lib/bitset/array.c +++ b/lib/bitset/array.c @@ -227,18 +227,15 @@ abitset_list (bitset src, bitset_bindex *list, bitoff = windex * BITSET_WORD_BITS; bitset_word word = srcp[windex] >> bitno; - for (bitno = bitoff + bitno; word; bitno++) + bitno = bitoff + bitno; + BITSET_FOR_EACH_BIT (pos, word) { - if (word & 1) + list[count++] = bitno + pos; + if (count >= num) { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } + *next = bitno + pos + 1; + return count; } - word >>= 1; } windex++; } @@ -251,31 +248,20 @@ abitset_list (bitset src, bitset_bindex *list, if (!word) continue; + /* Is there enough room to avoid checking in each iteration? */ if ((count + BITSET_WORD_BITS) < num) - { - for (bitno = bitoff; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } + BITSET_FOR_EACH_BIT (pos, word) + list[count++] = bitoff + pos; else - { - for (bitno = bitoff; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - } + BITSET_FOR_EACH_BIT (pos, word) + { + list[count++] = bitoff + pos; + if (count >= num) + { + *next = bitoff + pos + 1; + return count; + } + } } *next = bitoff; -- cgit v1.2.1