Re: mention the 'bitset' module on planet.gnu.org?

[Akim Demaille]

Hi Bruno,

> Le 3 janv. 2021 à 03:19, Bruno Haible <bruno@clisp.org> a écrit :
> 
> Hi Akim,
> 
> You might have noticed that we are currently publishing a news item per week
> about Gnulib in https://savannah.gnu.org/news/?group=gnulib ; they get
> propagated to http://planet.gnu.org/ .
> 
> Would you want to write a short text about the 'bitset' module, for
> publication on 2021-01-06 or 2021-01-20?
> 
> The audience is someone who may have heard about Gnulib, but is not yet
> using it.

Here's my proposal.  Feel free to edit it at will.

Cheers!

# A set of bitset implementations

Gnulib features bitset, a module to support operations of lists of bits.

Its API is rich, and includes:
- all the expected operations on single bit (set, toggle, test, etc.);
- all the traditional binary bitwise operators (and, or, xor), often in two 
flavors (return new values, or perform in place);
- some useful ternary operations, such as ((a ∧ b) ∨ c), ((a ∧ ¬b) ∨ c), etc.  
Also in two flavors;
- many predicates (empty, equal, intersects, disjoint, subset and so forth);
- and of course, object creation, destruction, printing, iteration, reverse 
iteration, etc.

The following example, taken from Bison, shows the bitset module in action.  
It's a fix-point computation of `N`, a bitset of the "useful" symbols (a symbol 
is useful if it can actually correspond to a piece of text.  Think for instance 
to `a: a b; b: a;`, `a` and `b` are useless).

```
static void
useless_nonterminals (bitset N, bitset P)
{
  /* N is the bitset as built.  Np is set being built this iteration. 
     P is bitset of all productions which have a RHS all in N.  */
  bitset Np = bitset_create (nnterms, BITSET_FIXED);
  while (true)
    {
      bitset_copy (Np, N);
      for (rule_number r = 0; r < nrules; ++r)
        if (!bitset_test (P, r)
            && useful_production (r, N))
          {
            bitset_set (Np, rules[r].lhs->number);
            bitset_set (P, r);
          }
      if (bitset_equal_p (N, Np))
        break;
      bitset_swap (N, Np);
    }
  bitset_free (N);
  N = Np;
}
```

Like several other gnulib modules, bitset's API actually sits on top of several 
implementations, with different performance profiles.  Indeed bitsets can have 
a fixed size, or being resizable; they can be tailored for dense sets (think of 
an array of bits), or sparse (think of list of bits, or alternatively an table 
of segments of dense bits).  The module also includes a dedicated 
implementation for small bitsets, fitting in machine words, which is 
automatically selects when appropriate.  It even features another 
implementation, stats, which wraps a "genuine" implementation to gather 
statistical data about the use of the bitsets, to help you tune your use of 
bitset.

All this in a very transparent manner: an argument provided to the constructor 
(see `BITSET_FIXED` in the example above).

Gnulib hosts another module, bitsetv, which uses the bitset module to provide 
support for matrices of bits.

Both modules were crafted in 2002 by Michael Hayes for GCC 
(https://gcc.gnu.org/ml/gcc/2002-01/msg00825.html), but, to the best of our 
knowledge, it was never adopted there.  However, the Bison team imported into 
Bison and maintained it over the years, and later contributed it to gnulib.