Re: bitpack search in bitsets

[Bruno Haible]

Hi Akim,

> That doesn't ring any bell.  I don't remember I saw any feature in bitset
> that depends on consecutive set bits, and a quick search did not find
> anything.

OK.

> Conversely: couldn't ssfmalloc sit on top of bitset?

Well, in ssfmalloc it is important to use the available space well. When
I use a bitset of 256 bits in order to describe which of the 16-byte blocks
of a 4096-bytes page are free, this requires 8 32-bit words. Now adding
5 (32-bit or 64-bit) words as meta-information, as defined per these
type definitions:

typedef union bitset_union *bitset;

union bitset_union
{
  ...
  struct abitset_struct
  {
    struct bbitset_struct b;
    bitset_word words[1];               /* The array of bits.  */
  } a;
  ...
};

struct bbitset_struct
{
  const struct bitset_vtable *vtable;
  bitset_windex cindex;         /* Cache word index.  */
  bitset_windex csize;          /* Cache size in words.  */
  bitset_word *cdata;           /* Cache data pointer.  */
  bitset_bindex n_bits;         /* Number of bits.  */
  /* Perhaps we could sacrifice another word to indicate
     that the bitset is known to be zero, that a bit has been set
     in the cache, and that a bit has been cleared in the cache.
     This would speed up some of the searches but slightly slow down
     bit set/reset operations of cached bits.  */
};

is not really desirable. It would be only 1% waste, but the percents add up.

In other words, the 'bitset' module - while generally good for applications -
is one level too complex for this particular use-case.

Bruno