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

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

[Bruno Haible]

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.

Bruno

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.

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

[Bruno Haible]

Hi Akim,

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

Looks good to me. Except that I would change the title to mention Gnulib.

> # A set of bitset implementations

How about:
  # Gnulib provides versatile bit-set implementations

?

Then please go ahead and post it from https://savannah.gnu.org/projects/gnulib
-> News > Submit.

Bruno