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.
---
ChangeLog | 6 ++++++
lib/bitset/array.c | 50 +++++++++++++++++-----------------------------
lib/bitset/base.h | 17 ++++++++++++++++
modules/bitset | 1 +
4 files changed, 42 insertions(+), 32 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 713206bcf..d2f104af3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2020-11-15 Akim Demaille <a...@lrde.epita.fr>
+ bitset: use ffsl to accelerate iterations over set bits
+ 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.
+
bitset: more tests
* tests/test-bitset.c (compare): Make it clear that the random values
should not be modified.
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 1db583891..6c5f7ed34 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;
diff --git a/lib/bitset/base.h b/lib/bitset/base.h
index 2ae7b2080..50569a0fc 100644
--- a/lib/bitset/base.h
+++ b/lib/bitset/base.h
@@ -24,6 +24,7 @@
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
+#include <string.h> /* ffsl */
#include "attribute.h"
#include "xalloc.h"
@@ -52,6 +53,14 @@ extern const char * const bitset_type_names[];
typedef unsigned long bitset_word;
#define BITSET_WORD_BITS ((unsigned) (CHAR_BIT * sizeof (bitset_word)))
+/* Iterate over each set bit of WORD.
+ Each iteration sets POS to the 0-based index of the next set bit in WORD.
+ Repeatedly resets bits in WORD in place until it's null. */
+#define BITSET_FOR_EACH_BIT(Pos, Word) \
+ for (int Pos = bitset_ffs (Word); \
+ 0 <= Pos; \
+ Word ^= 1UL << Pos, Pos = bitset_ffs (Word))
+
/* Bit index. In theory we might need a type wider than size_t, but
in practice we lose at most a factor of CHAR_BIT by going with
size_t, and that is good enough. If this type is changed to be
@@ -60,6 +69,14 @@ typedef unsigned long bitset_word;
The bit and word index types must be unsigned. */
typedef size_t bitset_bindex;
+/* First first set bit in WORD.
+ Indexes start at 0, return -1 if WORD is null. */
+static inline
+int bitset_ffs (bitset_word word)
+{
+ return ffsl ((long) word) - 1;
+}
+
/* Word index. */
typedef size_t bitset_windex;
diff --git a/modules/bitset b/modules/bitset
index 21cde24ac..c65471a02 100644
--- a/modules/bitset
+++ b/modules/bitset
@@ -20,6 +20,7 @@ Depends-on:
attribute
c99
fopen-gnu
+fssl
gettext-h
obstack
xalloc
--
2.29.2
