[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: bitpack search in bitsets

From: Bruno Haible
Subject: Re: bitpack search in bitsets
Date: Wed, 18 Nov 2020 10:53:28 +0100
User-agent: KMail/5.1.3 (Linux/4.4.0-193-generic; KDE/5.18.0; x86_64; ; )

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.


> 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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]