[PATCH 5/5] bitset: use ffsl to accelerate iterations over set bits

[Akim Demaille]

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  <akim@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